Closest Pair Algorithm I want to find the most optimal algorithm for finding closest ordered pairs and link them.

For example:
Go thru the vector, one by one

For each one set the next according to a set of various conditions

For example, something like:

A B X C Y Z D

First we will link A to B
Then when we have a look at B,
we will link B to C
Next when we consider X,
we will link X to Y
Next when we consider C,
we will link C to D   ... and so on

Currently someone has completed this task with some nested loops that are genuinely sub-par and it completes in O(n^2) time.  Not to mention it doesn't work.  What might be a better algorithm?

Here is what the current algorithm is: 

for(i in list)
  while (i and j) is not linked 
     increment j
  if j is not the end
     while ++j is not the end  
       if link exists (i and j)
       break
     end while
     set link i to j
  end if
end for


I was going to write my own but I have a feeling I've seen this problem before at university and there was a simple solution to it..?  Can anyone point me in the right direction please?
An alternative approach could be


Scan the vector and insert all elements into a self-balancing BST (AVL or Red-Black Tree etc etc, your pick) along with its index in the vector. $Node := (Value,VectorIndex)$
Then you have two choices


Scan the vector again, and for each element, search for it in the BST, and find its successor. Link the element and its successor in the vector.
Do an inorder traversal of the BST and for every pair of consecutive nodes visited in the BST, link their corresponding elements in the vector.



Either way, step 1 and 2 each take $O(n\space log \space n)$, hence the total algorithm ends up with a time complexity of $O(n \space log \space n)$ and space complexity of $O(n)$.