Doubly-Linked Lists in Java

Question

I am a freshman in IT and we did a quiz about linked lists and one of the questions was:

Linked List. Show the resulting list (redraw) after the following statements are executed.

So we have a doubly linked list list with each node having a character of the word "algorithm" (9 nodes), and where p1 references the node with value "l", p2 references the node with "i", and p3` the node with "t".

The statements to execute on this list are:

p2.next.prev = p2.prev;   // (a)
p2.prev.next = p2.next;   // (b)
p2.next = p3.next;        // (c)
p3.next.prev = p2;        // (d)
p3.next = p2;             // (e)
p2.prev = p3;             // (f)
list.next.next = p1.next; // (g)
p1.next.prev = list.next; // (h)
p1 = null;                // (i)
System.gc();              // (j)

The answer I got was 'agortihm', but it was considered incorrect. The picture of the question indicates the correct answer.

I have been at it for 2 hours now, but I still can't get how they arrived at that correct answer. I keep arriving at 'agortihm' as an answer. Any help would be much appreciated thank you!

Answer 1

You correctly identified that the first six statements move the node "i" after node "t". We start with:

               p1                          p2     p3
               ↓                           ↓      ↓
      ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐
list─►││a│┼─►││l│┼─►││g│┼─►││o│┼─►││r│┼─►││i│┼─►││t│┼─►││h│┼─►││m│┼─►Ω
   Ω◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││
      └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘

After (a) p2.next.prev = p2.prev;:

               p1                          p2     p3
               ↓                           ↓      ↓
      ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐
list─►││a│┼─►││l│┼─►││g│┼─►││o│┼─►││r│┼─►││i│┼─►││t│┼─►││h│┼─►││m│┼─►Ω
   Ω◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││ ┌┼│ ││◄─┼│ ││◄─┼│ ││
      └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘ │└┴─┴┘  └┴─┴┘  └┴─┴┘
                                    ▲          │
                                    └──────────┘  

After (b) p2.prev.next = p2.next;:

                                           p2     p3
               p1                      ┌──────────┐
               ↓                       │   ↓      ▼
      ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐│ ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐
list─►││a│┼─►││l│┼─►││g│┼─►││o│┼─►││r│┼┘ ││i│┼─►││t│┼─►││h│┼─►││m│┼─►Ω
   Ω◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││ ┌┼│ ││◄─┼│ ││◄─┼│ ││
      └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘ │└┴─┴┘  └┴─┴┘  └┴─┴┘
                                    ▲          │
                                    └──────────┘  

After (c) p2.next = p3.next;:

                                                  p3
                                       ┌──────────┐
               p1                      │   p2 ┌───│──────┐
               ↓                       │   ↓  │   ▼      ▼
      ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐│ ┌┬─┬┐│ ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐
list─►││a│┼─►││l│┼─►││g│┼─►││o│┼─►││r│┼┘ ││i│┼┘ ││t│┼─►││h│┼─►││m│┼─►Ω
   Ω◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││ ┌┼│ ││◄─┼│ ││◄─┼│ ││
      └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘ │└┴─┴┘  └┴─┴┘  └┴─┴┘
                                    ▲          │
                                    └──────────┘  

After (d) p3.next.prev = p2;:

                                                  p3
                                       ┌──────────┐
               p1                      │   p2 ┌───│──────┐
               ↓                       │   ↓  │   ▼      ▼
      ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐│ ┌┬─┬┐│ ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐
list─►││a│┼─►││l│┼─►││g│┼─►││o│┼─►││r│┼┘ ││i│┼┘ ││t│┼─►││h│┼─►││m│┼─►Ω
   Ω◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││ ┌┼│ ││ ┌┼│ ││◄─┼│ ││
      └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘ │└┴─┴┘ │└┴─┴┘  └┴─┴┘
                                    ▲      ▲   │      │
                                    │      └───│──────┘
                                    └──────────┘  

After (e) p3.next = p2;:

                                           p2     p3
                                           ┌─────────┐
                                       ┌──────────┐  │
               p1                      │   │  ┌───│──────┐
               ↓                       │   ▼  │   ▼  │   ▼
      ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐│ ┌┬─┬┐│ ┌┬─┬┐│ ┌┬─┬┐  ┌┬─┬┐
list─►││a│┼─►││l│┼─►││g│┼─►││o│┼─►││r│┼┘ ││i│┼┘ ││t│┼┘ ││h│┼─►││m│┼─►Ω
   Ω◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││ ┌┼│ ││ ┌┼│ ││◄─┼│ ││
      └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘ │└┴─┴┘ │└┴─┴┘  └┴─┴┘
                                    ▲      ▲   │      │
                                    │      └───│──────┘
                                    └──────────┘  

After (f) p2.prev = p3;:

                                           p2     p3
                                           ┌─────────┐
                                       ┌──────────┐  │
               p1                      │   │  ┌───│──────┐
               ↓                       │   ▼  │   ▼  │   ▼
      ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐│ ┌┬─┬┐│ ┌┬─┬┐│ ┌┬─┬┐  ┌┬─┬┐
list─►││a│┼─►││l│┼─►││g│┼─►││o│┼─►││r│┼┘ ││i│┼┘ ││t│┼┘ ││h│┼─►││m│┼─►Ω
   Ω◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││ ┌┼│ ││ ┌┼│ ││ ┌┼│ ││◄─┼│ ││
      └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘ │└┴─┴┘ │└┴─┴┘ │└┴─┴┘  └┴─┴┘
                                    ▲   │  ▲   │  ▲   │
                                    │   │  └───│──│───┘
                                    └───│──────┘  │
                                        └─────────┘

The move of the node "i" has been completed. We can simplify the above drawing when we picture node "i" at the right of node "t". As these nodes are referenced by p2 and p3, also those move along:

               p1                          p3     p2
               ↓                           ↓      ↓
      ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐
list─►││a│┼─►││l│┼─►││g│┼─►││o│┼─►││r│┼─►││t│┼─►││i│┼─►││h│┼─►││m│┼─►Ω
   Ω◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││
      └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘

Where you went wrong

The next statements don't change anything, as they assign references that the target properties already have before the assignment takes place:

list.next.next = p1.next;
p1.next.prev = list.next;

And the last assignment p1 = null; only affects a variable, and not the list:

               p1→Ω                        p3     p2
                                           ↓      ↓
      ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐  ┌┬─┬┐
list─►││a│┼─►││l│┼─►││g│┼─►││o│┼─►││r│┼─►││t│┼─►││i│┼─►││h│┼─►││m│┼─►Ω
   Ω◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││◄─┼│ ││
      └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘  └┴─┴┘

And so the result is: "algortihm".

Note that the answer drawn on the image is not correct. For instance, it claims that the node "o" is followed by node "t". But none of the instructions mutates the node with "o", so its successor must be "r" as in the original list -- that next reference never changed.

Verification

We could just write code to actually execute those statements and see what we get. Although your question is for Java, I choose here to add a runnable snippet (JavaScript) that executes the given statements:

// Definition of class and functions needed to execute the main program
class Node {
    constructor(letter) {
        this.letter = letter;
        this.next = this.prev = null;
    }
}

function stringToList(str) { 
    if (str.length == 0) return null;
    const head = new Node(str.charAt(0)); 
    for (let i = 1, node = head; i < str.length; i++) {
        node.next = new Node(str.charAt(i));
        node.next.prev = node;
        node = node.next;
    }
    return head;
}

function listToString(head) { 
    let s = "";
    while (head != null) {
        s += head.letter; 
        head = head.next;
    }
    return s;
}

// Prepare the input: the list and the node references:
let list = stringToList("algorithm");
let p1 = list.next;
let p2 = p1.next.next.next.next;
let p3 = p2.next;
// Verify that the p-variables reference the intended nodes:
console.assert(p1.letter == 'l' && p2.letter == 'i' && p3.letter == 't');
// Execute the given assignments
p2.next.prev = p2.prev;   // (a)
p2.prev.next = p2.next;   // (b)
p2.next = p3.next;        // (c)
p3.next.prev = p2;        // (d)
p3.next = p2;             // (e)
p2.prev = p3;             // (f)
list.next.next = p1.next; // (g)
p1.next.prev = list.next; // (h)
p1 = null;                // (i)
// What is the result?
console.log(listToString(list));  // algortihm