DoublyLinkedList混淆

Question

我对下面的片段代码有点困惑，假设我们已经有了一个双链接列表头->尾；

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:头->节点；头->尾(原始列表)

line2:头->节点->尾；头->尾(原始列表)

line3：？

line4：？

我无法理解第3行和第4行，在执行第1行和第2行之后，有两个双链接列表(一个是原始的双链接列表，另一个是新创建的链接列表)？第3行指的是哪个头？

Answer 1

假设头和尾最初是双链接列表中唯一的两个节点，下面是发生的情况.在艺术上！

打电话之前：

                  +--------+
                  |    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     | <-+
|   +--------+        +--------+        +--------+   |
|                                                    |
+----------------------------------------------------+

Answer 2

第3行的意思是，列表中的第一项应该具有以前新的最后一项的值。

第4行表示，旧的最后一项现在应该有一个指向新头的下一个值。

Answer 3

第3行修改旧的第二个节点(现在是第三个节点)。它将新的第二个节点设置为它的前一个节点。

第4行修改头，将新节点设置为第二个节点。