双链表混淆

Question

我对以下段代码有点困惑，假设我们已经有一个双 linked 列表 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->node;头->尾（原列表）

第2行：头部->节点->尾部；头->尾（原列表）

第 3 行：????

第 4 行：????

第3行和第4行看不懂，执行第1行和第2行后，有两个double linked list（一个是原来的double link list，一个是新建的一）？第 3 行指的是哪个头？

Answer 1

第 3 行表示列表中的第一项应该具有新的最后一项的先前值。

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

Answer 2

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

第 4 行修改 head 以将新节点设置为第 2 个节点。

Answer 3

假设 head 和 tail 最初是双向链表中仅有的两个节点，以下是发生的情况...在 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     | <-+
|   +--------+        +--------+        +--------+   |
|                                                    |
+----------------------------------------------------+

Answer 4

双向链表的初始状态;

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

在这种情况下，考虑 head.post 是任意节点，新节点将位于（插入）在 head[ 之后=50=]，以及 head.post.

之前
head、head.post、node的引用状态逐渐变化如下；

第一行

node.pre=头；

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

第二行

node.post = head.post;

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

第三行

head.post.pre = node;

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

第四行

head.post = 节点；

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

希望对您有所帮助。

双链表混淆

DoublyLinkedList Confusion

java

list

linked-list

nodes

doubly-linked-list

第一行

第二行

第三行

第四行