DoublyLinkedList Confusion

I am a little bit confused about the following segment codes, suppose we already have a double linked list head->tail;

class DLinkedNode {
  int key;
  int value;
  DLinkedNode pre;
  DLinkedNode post;
}

/**
 *  Always add the new node right after head;
 */
private void addNode(DLinkedNode node){
  node.pre = head;       // line 1
  node.post = head.post; // line 2
  head.post.pre = node;  // line 3
  head.post = node;      // line 4
}

I trying tracing the code

line1: head->node; head->tail(original list)

line2: head->node->tail; head->tail(original list)

line3: ????

line4: ????

I cannot understand line 3 and line 4, after executing line 1 and line 2, there are two double linked list (one is original double link list and another is the newly created one)? which head is line 3 is referring to?

Upvotes: 2

Answers (4)

Levent Divilioglu

Reputation: 11602

Initial state of the doubly linked list;

head -----------------> head.post

In this case, consider that head.post is an arbitrary node and the new node is going to be located (inserted) after head, and before the head.post.

The states of the references of head, head.post and node is changed gradually as below;

First Line

node.pre = head;

head <----------------> head.post
head <----------------- node

Second Line

node.post = head.post;

head <----------------> head.post
head <----- node -----> head.post

Third Line

head.post.pre = node;

head <----- node <----> head.post

Fourth Line

head.post = node;

head <----> node <----> head.post

Hope that it helps.

Upvotes: 1

Jonathan Ellithorpe

Reputation: 564

Assuming that head and tail are the only two nodes in the doubly linked list initially, the following is what happens... in ascii art!

Before the call:

                  +--------+
                  |    post|
                  |  node  |
                  |pre     |
                  +--------+

+-------------------------------------------+
|                                           |
|                                           |
|   +--------+                 +--------+   |
+-> |    post+---------------> |    post+---+
    |  head  |                 |  tail  |
+---+pre     | <---------------+pre     | <-+
|   +--------+                 +--------+   |
|                                           |
+-------------------------------------------+

Line 1:

                  +--------+
                  |    post|
                  |  node  |
       +----------+pre     |
       |          +--------+
       |
+------|------------------------------------+
|      |                                    |
|      v                                    |
|   +--+-----+                 +--------+   |
+-> |    post+---------------> |    post+---+
    |  head  |                 |  tail  |
+---+pre     | <---------------+pre     | <-+
|   +--------+                 +--------+   |
|                                           |
+-------------------------------------------+

Line 2:

                  +--------+
                  |    post+---------+
                  |  node  |         |
       +----------+pre     |         |
       |          +--------+         |
       |                             |
+------|-----------------------------|------+
|      |                             |      |
|      v                             v      |
|   +--+-----+                 +-----+--+   |
+-> |    post+---------------> |    post+---+
    |  head  |                 |  tail  |
+---+pre     | <---------------+pre     | <-+
|   +--------+                 +--------+   |
|                                           |
+-------------------------------------------+

Line 3:

                  +--------+
                  |    post+---------+
                  |  node  |         |
       +----------+pre     |         |
       |          +------+-+         |
       |                 ^           |
+------|-----------------|-----------|------+
|      |                 |           |      |
|      v                 |           v      |
|   +--+-----+           |     +-----+--+   |
+-> |    post+---------------> |    post+---+
    |  head  |           |     |  tail  |
+---+pre     |           +-----+pre     | <-+
|   +--------+                 +--------+   |
|                                           |
+-------------------------------------------+

Line 4:

                  +--------+
                  |    post+---------+
                  |  node  |         |
       +----------+pre     |         |
       |          +-+----+-+         |
       |            ^    ^           |
+------|------------|----|-----------|------+
|      |            |    |           |      |
|      v            |    |           v      |
|   +--+-----+      |    |     +-----+--+   |
+-> |    post+------+    |     |    post+---+
    |  head  |           |     |  tail  |
+---+pre     |           +-----+pre     | <-+
|   +--------+                 +--------+   |
|                                           |
+-------------------------------------------+

Final result:

+----------------------------------------------------+
|                                                    |
|                                                    |
|   +--------+        +--------+        +--------+   |
+-> |    post+-------->    post+-------->    post+---+
    |  head  |        |  node  |        |  tail  |
+---+pre     <--------+pre     <--------+pre     | <-+
|   +--------+        +--------+        +--------+   |
|                                                    |
+----------------------------------------------------+

Upvotes: 4