doubly linked list illustration

Question

I'm trying to illustrate a doubly linked list problem. this is from an old test i've been studying lately.

The question is as follows:

draw what the final linked after this code:

ListNode n1 = new ListNode();
ListNode n2 = new ListNode();
ListNode n3 = n1;
n1.next = n2;
n3.prev = n1;
n1.next.prev = n3.next;

Where I get lost is the final line of code.

n1.next.prev = n3.next;

here's the solution:

http://www.imagechicken.com/viewpic.php?p=1242322384048558300&x=jpg

can anyone walk me through this one or lead me in a good direction?

Answer 1

I would try drawing three boxes. Divide each box into thirds - one third for the label, one third for "prev", and one third for "next". Then draw connecting lines from all the "prev" and "next" to the appropriate label to see how things are linked.

A picture can be worth a thousand words.

Answer 2

The key to this one is that n1 and n3 point to the same ListNode.

Here are the states after each of the 3 operations:

n1.next = n2;
// n1.prev = null;
// n1.next = n2;
// n2.prev = null;
// n2.next = null;
// n3.prev = null;
// n3.next = n2;

n3.prev = n1;
// n1.prev = n1;
// n1.next = n2;
// n2.prev = null;
// n2.next = null;
// n3.prev = n1;
// n3.next = n2;

n1.next.prev = n3.next;
// n1.prev = n1;
// n1.next = n2;
// n2.prev = n2;
// n2.next = null;
// n3.prev = n1;
// n3.next = n2;

So in that last statement, n3.next is the same as n1.next, which is n2. Thus, the last statement is equivalent to settings n2.prev = n2.

Answer 3

This sort of thing gets confusing, until you realize that there are only two INSTANCES of ListNode; n1, n2, and n3 are all referring to those instances. And in particular, the values of n1, n2, and n3 are only set once; since the value of n3 is set to n1, you could just as easily replace n3 with n1 in this code, and it would work the same.

Answer 4

Sorry -- could not make heads or tails out of the picture.

n1.next = n2. Therefor, n1.next.prev evaluates to n2.prev

n3 = n1. Therefore, n3.next evaluates to n1.next.

You are setting n2.prev to n1.next.

Answer 5

Step one: Two nodes, not linked. n1 is also known as n3.

      +-------+next        +-------+next
      |       +---->       |       +---->
  prev|   n1  |        prev|   n2  |    
 <----+   n3  |       <----+       |   
      +-------+            +-------+   

Step two: n1.next = n2;

      +-------+next        +-------+next
      |       +----------->|       +---->
  prev|   n1  |        prev|   n2  |    
 <----+   n3  |       <----+       |   
      +-------+            +-------+   

Step three: n3.prev = n1;
Since n3 is n1, this turns the arrow around.

      +-------+next        +-------+next
      |       +----------->|       +---->
  prev|   n1  |        prev|   n2  |    
 /----+   n3  |       <----+       |   
 \--->+-------+            +-------+   

Step four: n1.next.prev = n3.next;
Remember that n1.next is n2, and n3 is n1. Follow the arrows:

      +-------+next        +-------+next
      |       +----------->|       +---->
  prev|   n1  |        prev|   n2  |    
 /----+   n3  |       /----+       |   
 \--->+-------+       \--->+-------+   

So the prev pointers of n1 and n2 both end up pointing to themselves.