How do I implement a sort of a head to tail list?

Question

Given the following inputs: (note: this is not a linked list, it's all one string output from a web app that I don't have control over)

DAVSCAF1WD6-11 ==> MOTENVF1WD6-11 
MOTENVF1WD6-11 ==> WNDVUTF1WD4-11 
TPKAKSF1WD6-11 ==> KSCYMOF1WD6-11
WNDVUTF1WD3-11 ==> WGTNUTF1WD2-11
DNVRCOF1WD7-11 ==> BELTKSF1WD3-11 
SNFCCAF1WD6-16 ==> DAVSCAF1WD5-16
WGTNUTF1WD2-11 ==> DTSRCOF1WD3-11
DTSRCOF1WD3-11 ==> DNVRCOF1WD6-11 
BELTKSF1WD3-11 ==> TPKAKSF1WD6-11

I need to produce the following results:

SNFCCAF1WD6-16 ==> DAVSCAF1WD5-16 
DAVSCAF1WD6-11 ==> MOTENVF1WD6-11 
MOTENVF1WD6-11 ==> WNDVUTF1WD4-11 
WNDVUTF1WD3-11 ==> WGTNUTF1WD2-11 
WGTNUTF1WD2-11 ==> DTSRCOF1WD3-11
DTSRCOF1WD3-11 ==> DNVRCOF1WD6-11 
DNVRCOF1WD7-11 ==> BELTKSF1WD3-11 
BELTKSF1WD3-11 ==> TPKAKSF1WD6-11 
TPKAKSF1WD6-11 ==> KSCYMOF1WD6-11

This is a list where each tail points to the head of the next item in line (ex. SNFCCAF ==> DAVSCAF ==> DAVSCAF ==> MOTENVF ==> MOTENVF ==> WNDVUTF ==> etc. ) Only the leading alpha charaters are significant in this case.

How can I accomplish this as elegantly as possible? The language this is being implemented in is Java.

Answer 1

If you aren't going to have duplicates, then maybe the easiest way to do this is with a Map. Put each head-tail pair in as the key and value. Then you can traverse the list with Map.get() by using the previous tail as the next head.

On the other hand, you're then stuck with the problem of finding the first item in the list: That would be a head which never appears as a tail. For that, I guess you could setwise subtract values() from keySet(). Assuming that you really have a chain, the result will be the singleton set containing the first element in the list.