java - 双链表困惑

Question

我对下面的段代码有点困惑，假设我们已经有一个双链表 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
}

我正在尝试跟踪代码

line1:头->节点； head->tail(原始列表)

第2行:头->节点->尾； head->tail(原始列表)

第 3 行:？？？

第 4 行:？？？

我看不懂第3行和第4行，执行第1行和第2行后，有两个双链表(一个是原来的双链表，另一个是新创建的)？第 3 行指的是哪个头？

Answer 1

假设头和尾最初是双向链表中仅有的两个节点，以下是发生的情况......在ascii艺术中!

通话前:

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

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

第 1 行:

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

第 2 行:

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

第 3 行:

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

第 4 行:

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

最终结果:

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