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

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
WNDVUTF1WD开发者_JAVA百科3-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.

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.

I am late to this but FWIW I have used the Google Collections for a similar problem where I have a list that contains records that have a variable number of lines. To manage it more easily I decided to create head / tail style functions like this:

public class MyListUtils {

    public static <T> List<T> getHeadSubList(List<T> list, Predicate<T> predicate) {
        int firstItem = indexOf(list, predicate);

        if (firstItem < 0)
            return new ArrayList<T>(); // return empty list if none found

        if (firstItem == list.size() - 1)   // It's the last element of the list
            return list.subList(firstItem, list.size());

        List<T> rest = list.subList(firstItem + 1, list.size());
        int nextItem = indexOf(rest, predicate);

        if (nextItem < 0)
            return list;
        else
            return list.subList(firstItem, nextItem + 1);
    }

    public static <T> List<T> getTailSubList(List<T> list, Predicate<T> predicate) {
        List<T> head = getHeadSubList(list, predicate);

        if (head.isEmpty() || head.size() == list.size())
            return new ArrayList<T>(); // return empty list if none found

        return list.subList(head.size(), list.size());
    }
}