Recreating LinkedList of pointers from list of pointers

user_14521531 0
Viewed 77

I have a list of random "pointers"

  • "A,B,C,D,E,F"

They belong into N different linked lists

  • "A->C->D", "B->E", "F"

The only information I can get from the pointers is that the "child" knows the "parent" but not the other way around.

My current implementation to sort them into their own respective linked list is as below.

Would appreciate if i can get some pointers on optimizing the code below or if my approach to it is wrong.

        for (Pointer i: listOfPointers) {
            if (!i.hasParent())
                // no parent, its a root node
                rootNodes.add(i.getId());
            else {
                // parent -> child
                parentChild.put(i.getParent().getId(),i.getId());
            }
        }
        // iterate through the head/roots
        for (String i : rootNodes) {
            LinkedList<String> templist = new LinkedList<>();
            LinkedList<Map<String,String>> temp = new LinkedList<>();
            String tempnow = i;
            //construct our linked list, start by the head and getting the child until we have nothing left
            do{
                if (templist.size() == 0)
                    System.out.println("Parent - " + tempnow);
                else
                    System.out.println("Child - " + tempnow);
                templist.add(tempnow);
                if (parentChild.containsKey(tempnow))
                    tempnow = parentChild.get(tempnow);
                else
                    break;
            }while(true);
            linkedListHashMap.put(i, templist);
        }
pointers java
2 Answers

I would create a Map which maps each Pointer by its parent (effectively a Map of edges), except the root nodes which need to be stored separately. Afterwards, you can reconstruct the List by repeatetly traversing the graph until no further mapping is found.

public Collection<List<Pointer>> group(Collection<Pointer> pointers) {
    if(pointers.isEmpty()) {
        return Collections.emptyList();
    }

    List<Pointer> roots = new ArrayList<>();
    Map<Pointer, Pointer> parents = new HashMap<>(pointers.size());

    for(Pointer pointer : pointers) {
        if(pointer.hasParent()) {
            parents.put(pointer.getParent(), pointer);
        } else {
            roots.add(pointer);
        }
    }

    List<List<Pointer>> results = new ArrayList<>(roots.size());

    for(Pointer root : roots) {
        List<Pointer> list = new LinkedList<>();
        list.add(root);

        Pointer current = parents.get(root);
        while(current != null) {
            list.add(current);
            current = parents.get(current);
        }

        results.add(list);
    }

    return results;
}

For you given input:

Pointer a = new Pointer("A");
Pointer c = new Pointer("C", a);
Pointer d = new Pointer("D", c);

Pointer b = new Pointer("B");
Pointer e = new Pointer("E", b);

Pointer f = new Pointer("F");

Collection<Pointer> pointers = Arrays.asList(a, b, c, d, e, f);
Collection<List<Pointer>> grouped = group(pointers);
// result: A -> C-> D ; B -> E ; F
user_60153390

While there are straightforward solutions that build additional data structures on the top of original list, I think it would be interesting to find a solution that requires constant amount of additional memory, like this one:

boolean sorted = false;
while (!sorted) {
  sorted = true;
  for (Element element: elements) {
    Element parent = element.parent;
    if (parent != null) {
      Element grandParent = parent.parent;
      if (grandParent != null && parent.value > grandParent.value) {
        element.parent = grandParent;
        parent.parent = grandParent.parent;
        grandParent.parent = parent;
        sorted = false;
      }
    }
  }
}

// Now the tails of all lists are sorted, only the heads
// (first elements) may be misplaced

for (Element element : elements) {
  Element parent = element.parent;
  Element child = null;
  while (parent != null && element.value > parent.value) {
    if (child != null)
      child.parent = parent;
    element.parent = parent.parent;
    parent.parent = element;
    child = parent;
    parent = element.parent;
  }
}

The idea is that when all lists are sorted, each element may not be greater than its parent. So if we see A->B->C->... and B > C, then we rearrange this fragment as A->C->B->.... We do this until there are no such fragments to rearrange, which means that the tails of all lists are sorted and only the heads (first elements) may be misplaced.

Now we look for fragments looking like A->B->... where A > B. As only the heads may be misplaced, and A is obviously misplaced, then A is a head, i.e. there are no children of A. So we may iterate through the list starting at A, find where in this list A should be placed, and move A there, without necessity to update the children of A as A guaranteed to have no children.

Here is an example run on random data:

Original:
78->77->2->39->67->78->98->
86->30->71->90->86->97->98->30->88->31->67->19->36->5->57->16->
7->16->19->12->74->98->55->60->38->25->2->37->45->92->3->52->24->43->41->84->95->73->77->19->91->15->29->60->
17->94->25->
34->80->
51->
68->23->1->89->5->17->67->35->97->26->57->38->
89->84->
58->
8->5->87->43->8->
72->60->
41->49->28->92->84->
41->33->15->8->55->40->16->58->13->86->35->16->77->71->
53->13->

After the first loop:
78->2->39->67->77->78->98->
86->5->16->19->30->30->31->36->57->67->71->86->88->90->97->98->
7->2->3->12->15->16->19->19->24->25->29->37->38->41->43->45->52->55->60->60->73->74->77->84->91->92->95->98->
17->25->94->
34->80->
51->
68->1->5->17->23->26->35->38->57->67->89->97->
89->84->
58->
8->5->8->43->87->
72->60->
41->28->49->84->92->
41->8->13->15->16->16->33->35->40->55->58->71->77->86->
53->13->

After the second loop:
84->89->
5->8->8->43->87->
2->39->67->77->78->78->98->
13->53->
17->25->94->
28->41->49->84->92->
8->13->15->16->16->33->35->40->41->55->58->71->77->86->
60->72->
34->80->
51->
5->16->19->30->30->31->36->57->67->71->86->86->88->90->97->98->
58->
1->5->17->23->26->35->38->57->67->68->89->97->
2->3->7->12->15->16->19->19->24->25->29->37->38->41->43->45->52->55->60->60->73->74->77->84->91->92->95->98->
user_20387680
Related