Q: sorting a list of road junctions I have an object
class Junction {
   private String name;
   private String previous;
   private String next;
}

Now these junctions have the following format
Junction[name="T1H", previous="T0F", next="T345"]
Junction[name="K109", previous="TRH", next="JHD"]
Junction[name="LM89", previous="T1H", next="D679"]
Junction[name="TRH", previous="LM89", next="T345"]

The above would be ordered like so:
T1H->LM89->TRH->K109

But if i had an unordered list, How could i sort this? Whats the best algorithm in java to do this. Quick sort wont work because the concept of pivot and higher and lower don't really apply. you cannot work out if something is higher as Junctions are all linked.
Bubble sort seems like the logical one.
Any Ideas? 

A: You can use a hash map to store the successor to each junction, using those junctions previous attribute. using None, null, or any other special value if the "previous" junction is not in the list. This assumes that all junctions are direct successors or some other junction and no two junctions have the same "previous" junction. Complexity will be O(n) for n junctions.
from collections import namedtuple
Junction = namedtuple("Junction", "name previous next")
junctions = [
    Junction(name="T1H", previous="T0F", next="T345"),
    Junction(name="K109", previous="TRH", next="JHD"),
    Junction(name="LM89", previous="T1H", next="D679"),
    Junction(name="TRH", previous="LM89", next="T345")
]

d = {j.name: j for j in junctions}  # map names to junctions
succ = {j: None for j in junctions} # map previous to successor
for j in junctions:
    p = d.get(j.previous, None)
    succ[p] = j

Then, starting with the junction that is the successor to None, iterate all the junctions:
j = succ[None]
while j:
    print(j)
    j = succ[j]

Output:
Junction(name='T1H', previous='T0F', next='T345')
Junction(name='LM89', previous='T1H', next='D679')
Junction(name='TRH', previous='LM89', next='T345')
Junction(name='K109', previous='TRH', next='JHD')

(Using Python here, since you did not ask specifically for a Java solution, but of course the same can easily be done in Java.)
