↓跳到主要内容

双向链表与双向循环链表

·14067 字·29 分钟
DS
目录

双向链表

单向链表中一个结点的特点是指向下一个结点，双向链表中的特点顾名思义就是一个结点指向两个方向，一个是前一个结点，一个是后一个结点，一个结点的核心结构图示如下：

doubly_linked_list_01.drawio.svg

  • 假设0是目前结点要存储的整数数据，当然这个数据是可自定义的

  • pre指向的是当前结点的前一个结点

  • next指向的是当前结点的后一个结点

  • 且主要特征对比单向链表除了多了一个前向指针之外，尾结点的next指针域的值还是nullptr。

在当前双向链表中，还是和单向链表和单向循环链表一样，定义一个头结点，这个头结点特点如下：

doubly_linked_list_02.drawio.svg

头结点初始化的时候，前后指针的值都是nullptr，中间的数据域的值可随机，这里假设是整数0。

数据结构

定义一个DoublyLinkedList类，内部包含一个结点Node类型，用于初始化头结点和插入新结点。数据成员分别是指向前后结点的指针

  1. Node* pre_;

  2. Node* next_;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>
#include <random>

class DoublyLinkedList {
    struct Node {
        Node(int data = 0)
            : data_{data},
              pre_{nullptr},
              next_{nullptr} {}
        int data_;    // 数据域
        Node* pre_;   // 指向前一个结点的指针
        Node* next_;  // 指向后一个结点的指针
    };

public:
    // 构造函数
    DoublyLinkedList()
        : head_{new Node{0}} {}
    // 析构函数
    ~DoublyLinkedList() {
        Node* p = head_;

        while (p != nullptr) {
            head_ = head_->next_;
            delete p;
            p = head_;
        }
    }

private:
    Node* head_;  // 指向头结点的指针
};

构造函数

主要构建头结点，将头结点的前后指针都赋值为nullptr，数据域为0，并使得head_的值为头结点的地址。

1
2

DoublyLinkedList()
    : head_{new Node{0}} {}

析构函数

双向链表虽然比单向链表多了一个pre_指针，但它还是有next_指针的，依然可以按照单向链表的那种方式删除链表中每一个有效结点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// 析构函数
~DoublyLinkedList() {
    Node* p = head_;

    while (p != nullptr) {
        head_ = head_->next_;
        delete p;
        p = head_;
    }
}

  1. 定义指针p指向要删除的结点，p初始化为head_的值，代表从头结点开始删除

  2. 通过更改head_的指向，使得未被删除的结点能够被找到，保持链表完整

  3. p的值随着head的改变而改变，直到p的值为nullptr，也就是head_的值为nullptr，此时链表为空

双向链表的头插法O(1)

从单向链表和单向循环链表的经验来看，头插法主要考虑两个情况：

  1. 链表中无有效结点，只有一个头结点

  2. 链表中除了头结点之外，至少有一个有效结点

增加头结点的主要目的就是减少分支判断，若是没有减少分支判断，那就得不偿失了。

先看一下第二种情况，双向链表是如何执行头插法的，看一下至少有一个有效结点的双向链表的图示：

doubly_linked_list_03.svg

图示中显示，head_指向的是头结点，它的next_指向下一个有效结点，pre_指向nullptr；而第一个有效结点(这里假设叫A结点)的pre_指向头结点，next_指向nullptr。头插法的目的就是将下一个即将插入的结点插入到第一个有效位置成为新的第一个有效结点，那么A结点就会成为第二个有效结点，A结点与这个新的结点也要建立链接，头结点也要与这个新结点建立链接，但是这两个操作是需要先后顺序的，因为你若是先头结点与新结点建立链接，更改头结点的next_指向，那么当新结点与A结点进行链接的时候，此时已经不知道A结点的地址了，因为原先保存A结点地址的是头结点中的next_，但是现在先保存新结点的地址了，所以，我使用的是先将新结点new_node的两个指针域赋值好，分别指向头结点与结点A，再后续讨论头结点的next与结点A的pre。

  1. 构建一个新的结点new_node

  2. 先将新结点new_node的next_和pre_指针赋值好，这不会影响其他结点的指向，更不会丢失结点信息。

  3. 那么剩下的，是先重新赋值结点A的pre_还是头结点中的next_呢？也就是先执行head→next = new_node;还是head→next→pre = new_node;呢？一开始的思路是先执行head→next→pre = new_node会丢失结点A的地址信息，但是并不是的，因为此时还有一个结点的next_保存着结点A的地址信息，那就是new_node→next。所以，我的想法是先执行head→next = new_node，这与后面说的另外一种情况有关，将条件判断留给新构建的结点逻辑更清晰更容易理解。

  4. 最后new_node→next→pre = new_node;

看一下图示：

doubly_linked_list_04.svg

根据上述的图示，查看一下当双向链表中无有效结点时，这个顺序是否合法？

这个顺序的大致代码是：

  1. new_node→next_ = head_→next;

  2. new_node→pre_ = head_;

  3. head_→next_ = new_node;

  4. new_node→next→pre_ = new_node;

当双向链表中无有效结点的时候，头结点也是尾结点，head_→next = nullptr;head_→pre = nullptr;

按照上述的顺序，看是否可以将一个新的结点插入到无有效结点的链表的头部，且保证各个数据成员值的正确性，不会引发段错误

  1. new_node→next_ = head_→next_;此时head_→next = nullptr;插入的新结点是第一个有效结点，也是尾结点，new_node_→next = nullptr;是正确的。

  2. new_node→pre = head; 这也是正确的

  3. head→next = new_node;这也是正确的

  4. new_node→next→pre = new_node;这是错误的，因为new_node→next的值是等于nullptr的，这是因为当前链表无有效结点，头结点的next也就是head→next是nullptr，而在第一步的时候，new_node→next的值就是被head→next赋值的，因此也是nullptr。对一个空指针解引用是会产生段错误的。

因此，前三步都是一样的，但是在第四步的时候，需要一个判断，判断条件就是此时的new_node→next是否是nullptr，因为这个值在之前就是head→next赋予的，由于head→next被重新赋值了新值，所以需要new_node→next来去判断，当它是nullptr的时候，就代表之前无有效当前，当前的new_node是第一个有效结点。若不是nullptr，代表之前至少有一个有效结点，则执行new_node→next→pre = new_node;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

 // 头插法
void insertHead(int val) {
    // 构建新的结点
    Node* new_node = new Node{val};

    // 更新new_node的next与pre
    new_node->next_ = head_->next_;
    new_node->pre_ = head_;

    // 更新head的指向
    head_->next_ = new_node;

    // 判断new_node->next是否为nullptr
    if (new_node->next_ != nullptr) {
        new_node->next_->pre_ = new_node;
    }
}

测试头插法

在DoublyLinkedList类中重载«运算符，使其输出链表中的数据，代码写的有些乱，但是能够查看数据即可，先不在意是否美观

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

std::ostream& operator<<(std::ostream& os, const DoublyLinkedList& dll) {
    DoublyLinkedList::Node* p = dll.head_->next_;

    os << "head node: " << "\n";
    os << "ptr: " << dll.head_ << "\n";
    os << "pre_: " << dll.head_->pre_ << "\n";
    os << "next_: " << dll.head_->next_ << "\n";
    os << "\n";

    int count = 1;
    while (p != nullptr) {
        os << "node " << count << ": \n";
        os << "ptr: " << p << "\n";
        os << "data: " << p->data_ << "\n";
        os << "pre_: " << p->pre_ << "\n";
        os << "next_: " << p->next_ << "\n";
        os << "\n";
        p = p->next_;
        ++count;
    }

    return os;
}

查看输出结果：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

head node:
ptr: 0x600001ebd1e0
pre_: 0x0
next_: 0x600001ebd280

node 1:
ptr: 0x600001ebd280
data: 82
pre_: 0x600001ebd1e0
next_: 0x600001ebd260

node 2:
ptr: 0x600001ebd260
data: 9
pre_: 0x600001ebd280
next_: 0x600001ebd240

node 3:
ptr: 0x600001ebd240
data: 56
pre_: 0x600001ebd260
next_: 0x600001ebd220

node 4:
ptr: 0x600001ebd220
data: 50
pre_: 0x600001ebd240
next_: 0x600001ebd200

node 5:
ptr: 0x600001ebd200
data: 23
pre_: 0x600001ebd220
next_: 0x0

可以看出，总共插入5个结点，每个结点的pre和next的数据都是正确的

双向链表的尾插法O(n)

尾插法与头插法最大的不同就是新插入的结点一直都是尾结点，而头插法则一直都是第一个有效结点。因此，对于双向链表来说，我们需要先找到当前链表的最后一个结点在哪里，才能在其后插入新的结点，那么与单向链表一样，在没有尾指针的情况下， 需要遍历找到尾结点。但是我们还是要先分析，分析一下当前链表无有效结点且有头结点与至少一个有效结点的情况，若两者代码逻辑相同，则不需要进行分支判断。

  1. 链表中无有效结点，只有一个头结点

  2. 链表中除头结点以外，至少一个有效结点

与头插法一样，先看第二种情况，再使用第二种情况的逻辑去分析第一种。看以下图示，链表中除了头结点还有一个新的Node A，还有一个待插入的新结点new_node。

doubly_linked_list_05.svg

从图中可以看出，new_node结点是需要插入到Node A后面的，但是此时我们只知道头结点的地址，因此我们需要先找到Node A的地址，也就是尾结点的地址

  1. 尾结点在双向链表的特征是什么？next指针域的值为nullptr。所以，我们定义Node*类型的指针p，初始化为head，从头结点开始，循环判断p→next的值是否为nullptr，若是nullptr，则退出循环，执行插入，假设此时已经找到

  2. 构建新结点new_node。此时p指向尾结点，也就是图中的Node A，那么只需要将Node A的next指针域赋值为new_node的地址，将new_node的pre指针域赋值为Node A的地址即可。

按照上述的逻辑来看的话，代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void inserTail(int val)  {
  // 1. 定义新的指针p，循环找到尾结点
  Node* p = head;
  while(p->next != nullptr) {
    p = p->next;
  }
  
  //2. 构建新结点new_node，并插入
  Node* new_node = new Node{val};
  p->next = new_node;
  new_node->pre = p;
}

看一下插入图示：

doubly_linked_list_06.svg

按照上述逻辑分析去分析第一种情况，当前链表无有效结点，只有一个头结点，那么此时head→next = nullptr;head→pre = nullptr。查看以上代码是否合法？

  1. 定义一个新的指针p，合法

  2. while循环的代码，合法，当前p的值就是head，p→next就是head→next，此时head→next为nullptr，所以不进入循环，此时p就是尾结点，对吗？完全可以这样理解呀，头结点在此时不就是头结点，又是尾结点

  3. 构建新的结点，执行插入，完全没问题，其实与单向链表的逻辑是一样的，只不过多了一个pre需要赋值，但不影响整体逻辑

所以尾插法的两种情况可用一套代码逻辑，不需要进行分支判断，完整代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// 尾插法
void insertTail(int val) {
    // 1. 定义寻找尾结点的指针p
    Node* p = head_;
    while (p->next_ != nullptr) {
        p = p->next_;
    }

    // 2. 构建新的结点new_node
    Node* new_node = new Node{val};

    // 3. 执行插入
    p->next_ = new_node;
    new_node->pre_ = p;
}

测试尾插法

生成若干个随机素，使用尾插法进行插入，观察每个结点的pre与next的值的情况，是否前后相链接

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// 测试尾插法
void test_insert_tail() {
    DoublyLinkedList dll;

    std::random_device rd;

    std::mt19937 gen{rd()};

    std::uniform_int_distribution<> distrib(1, 100);

    for (int i = 0; i < 5; ++i) {
        dll.insertTail(distrib(gen));
    }

    std::cout << dll << "\n";
}

查看输出结果，观察每个结点pre的值是否等于前一个结点的地址，每个结点的next是否是下一个结点的地址，头结点的pre为nullptr，尾结点的next为nullptr。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

head node:
ptr: 0x600000b58040
pre_: 0x0
next_: 0x600000b58060

node 1:
ptr: 0x600000b58060
data: 80
pre_: 0x600000b58040
next_: 0x600000b58080

node 2:
ptr: 0x600000b58080
data: 13
pre_: 0x600000b58060
next_: 0x600000b580a0

node 3:
ptr: 0x600000b580a0
data: 31
pre_: 0x600000b58080
next_: 0x600000b580c0

node 4:
ptr: 0x600000b580c0
data: 72
pre_: 0x600000b580a0
next_: 0x600000b580e0

node 5:
ptr: 0x600000b580e0
data: 68
pre_: 0x600000b580c0
next_: 0x0

嗯，还不错

双向链表的按值删除(单个结点)O(n)

删除之前，判断链表中是否有有效结点，若无，则直接退出。

单向链表与单向循环链表删除一个结点需要有额外的一个指针，指向被删除结点的前一个结点，才可执行正确的删除。但是对于双向链表来说，结点比单向链表与单向循环链表多了一个pre指针域，通过这个pre指针域可以找到前一个结点。

  1. 定义新的指针p指向第一个有效结点

  2. 使用循环找到要删除的结点，循环条件为p ≠ nullptr，因为要删除一定是有效结点，当其为nullptr的时候，退出循环

  3. 当前p指向了要删除了结点，那么要删除这个结点，就需要先将前一个结点的next域指向这个删除结点的后一个结点，也就是删除结点的next域，伪代码就是p→pre→next = p→next;

  4. 因为多了一个pre域，因此删除这个结点的下一个结点的pre域还需要指向删除结点的上一个结点，伪代码就是p→next→pre = p→pre;

  5. 最后可执行删除这个结点，delete p

看一下图示：

doubly_linked_list_07.svg

实际代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 按值删除单个结点
void remove(int val) {
    // 若链表为空，则直接退出
    if (head_->next_ == nullptr){
        return;
    }
    // 定义一个新的指针p
    Node* p = head_->next_;

    // 循环找到要删除的结点
    while (p != nullptr) {
        // 判断当前结点的数据域是否与val相等，若相等则执行删除
        if (p->data_ == val) {
            p->pre_->next_ = p->next_;
            p->next_->pre_ = p->pre_;

            delete p;
            break;
        } else {
            p = p->next_;
        }
    }
}

更改：

若是删除的是最后一个结点，上述代码是不符合的，p→pre→next = p→next;由于p→next的值为nullptr，所以将这个结点删除之后，它的上一个结点的next也是nullptr。但是p→next→pre = p→pre;就不对了，因为p→next的为nullptr，利用空指针去→pre，是会出现段错误的，所以这里要讨论一下情况：

  1. 要删除的结点是尾结点

  2. 要删除的结点不是尾结点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// 按值删除单个结点
void remove(int val) {
    // 若链表无有效结点
    if (head_->next_ == nullptr) {
        return;
    }
    // 定义一个新的指针p
    Node* p = head_->next_;

    // 循环找到要删除的结点
    while (p != nullptr) {
        // 判断当前结点的数据域是否与val相等，若相等则执行删除
        if (p->data_ == val) {
            p->pre_->next_ = p->next_;
            // 若删除的结点不是尾结点
            if (p->next_ != nullptr) {
                p->next_->pre_ = p->pre_;
            }

            delete p;
            break;
        } else {
            p = p->next_;
        }
    }
}

测试按值删除单个结点

删除之前，查看整个链表的结点信息

1
2
3
4
5
6
7
8

void test_remove() {
    DoublyLinkedList dll;

    dll.insertTail(10);
    dll.insertTail(20);
    dll.insertTail(50);
    std::cout << dll << std::endl;
}

输出结果：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

head node:
ptr: 0x6000035011e0
pre_: 0x0
next_: 0x600003501200

node 1:
ptr: 0x600003501200
data: 10
pre_: 0x6000035011e0
next_: 0x600003501220

node 2:
ptr: 0x600003501220
data: 20
pre_: 0x600003501200
next_: 0x600003501240

node 3:
ptr: 0x600003501240
data: 50
pre_: 0x600003501220
next_: 0x0

假设删除值为20的结点，代码如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void test_remove() {
    DoublyLinkedList dll;

    dll.insertTail(10);
    dll.insertTail(20);
    dll.insertTail(50);

    dll.remove(50);
    std::cout << dll << std::endl;
}

查看输出结果：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

head node:
ptr: 0x603000001ba0
pre_: 0x0
next_: 0x603000001bd0

node 1:
ptr: 0x603000001bd0
data: 10
pre_: 0x603000001ba0
next_: 0x603000001c00

node 2:
ptr: 0x603000001c00
data: 20
pre_: 0x603000001bd0
next_: 0x0

此时值为10的结点的next域指向了值为50的结点，值为50的结点的pre域指向了值为10的结点。

双向链表的按值删除多个结点O(n)

删除之前，判断链表中是否有有效结点，若无，则直接退出。

删除结点的思想是一致的，最主要的是p找到了被删除结点且被删除之后，p的值需要重置为下一个有效结点继续寻找，那么此时的代码需要更改一下，在delete之前保存p→next的值，delete之后，将其重新赋值给p，进行下下一次循环寻找下一个值为val的结点，看一下实际的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// 按值删除多个结点
void remove_all(int val) {
    // 若链表无有效结点
    if (head_->next_ == nullptr) {
        return;
    }
    // 定义一个新的指针p
    Node* p = head_->next_;

    // 循环找到要删除的结点
    while (p != nullptr) {
        // 判断当前结点的数据域是否与val相等，若相等则执行删除
        if (p->data_ == val) {
            p->pre_->next_ = p->next_;
            p->next_->pre_ = p->pre_;

            Node* q = p->next_;
            delete p;
            p = q;
        } else {
            p = p->next_;
        }
    }
}

更改：

这也是要讨论删除的结点是否有尾结点的，修改后的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// 按值删除多个结点
void remove_all(int val) {
    // 若链表无有效结点
    if (head_->next_ == nullptr) {
        return;
    }
    // 定义一个新的指针p
    Node* p = head_->next_;

    // 循环找到要删除的结点
    while (p != nullptr) {
        // 判断当前结点的数据域是否与val相等，若相等则执行删除
        if (p->data_ == val) {
            p->pre_->next_ = p->next_;
            // 若删除的结点不是尾结点
            if (p->next_ != nullptr) {
                p->next_->pre_ = p->pre_;
                Node* q = p->next_;
                delete p;
                p = q;
            } else {// 若是尾结点
                delete p;
                break;
            }

        } else {
            p = p->next_;
        }
    }
}

更改：

  1. 指针q保存的是p→next的值，那么若p→next的值为nullptr，那么p指向的结点就是尾结点，q的值也为nullptr，删除p，将q的值赋值给p，此时p为nullptr，while的循环条件终止，循环结束

  2. 若p→next的值不为nullptr，则指向的不是尾结点，那么q的值为后一个结点的地址，删除p，将q的值赋值给p，p指向下一个结点，重新循环删除，也正确

因此，代码可以合并为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// 按值删除多个结点
void remove_all(int val) {
    // 若链表无有效结点
    if (head_->next_ == nullptr) {
        return;
    }
    // 定义一个新的指针p
    Node* p = head_->next_;

    // 循环找到要删除的结点
    while (p != nullptr) {
        // 判断当前结点的数据域是否与val相等，若相等则执行删除
        if (p->data_ == val) {
            p->pre_->next_ = p->next_;
   
            if (p->next_ != nullptr) {
                p->next_->pre_ = p->pre_;
            }
            Node* q = p->next_;
            delete p;
            p = q;
        } else {
            p = p->next_;
        }
    }
}

测试双向链表的按值删除多个结点

删除之前，插入值为20的多个结点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// 测试按值删除多个结点
void test_remove_all() {
    DoublyLinkedList dll;

    dll.insertTail(10);
    dll.insertTail(20);
    dll.insertTail(50);
    dll.insertTail(20);

    dll.insertTail(20);

    std::cout << dll << std::endl;
}

查看输出结果：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

head node:
ptr: 0x603000001ba0
pre_: 0x0
next_: 0x603000001bd0

node 1:
ptr: 0x603000001bd0
data: 10
pre_: 0x603000001ba0
next_: 0x603000001c00

node 2:
ptr: 0x603000001c00
data: 20
pre_: 0x603000001bd0
next_: 0x603000001c30

node 3:
ptr: 0x603000001c30
data: 50
pre_: 0x603000001c00
next_: 0x603000001c60

node 4:
ptr: 0x603000001c60
data: 20
pre_: 0x603000001c30
next_: 0x603000001c90

node 5:
ptr: 0x603000001c90
data: 20
pre_: 0x603000001c60
next_: 0x0

删除值为20的结点，再次查看输出结果：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// 测试按值删除多个结点
void test_remove_all() {
    DoublyLinkedList dll;

    dll.insertTail(10);
    dll.insertTail(20);
    dll.insertTail(50);
    dll.insertTail(20);

    dll.insertTail(20);

    dll.remove_all(20);

    std::cout << dll << std::endl;
}

查看输出结果：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

head node:
ptr: 0x603000001ba0
pre_: 0x0
next_: 0x603000001bd0

node 1:
ptr: 0x603000001bd0
data: 10
pre_: 0x603000001ba0
next_: 0x603000001c30

node 2:
ptr: 0x603000001c30
data: 50
pre_: 0x603000001bd0
next_: 0x0

值为20的结点全部被删除：

  1. 值为10的结点的next域指向值为50的结点，值为50的结点的pre域指向值为10的结点。

  2. 值为50的结点成为尾结点，其next域为nullptr

双向循环链表

双向循环链表与双向链表的不同对比单向链表对比单向循环链表不同是不一样的，单向链表与单向循环链表不同的是尾结点的next域，前者是nullptr，后者是指向了头结点(若无头结点，则指向第一个有效结点)。而双向链表与双向循环链表不同是，尾结点的next域指向了头结点，而头结点的pre域指向了尾结点，这增加了复杂性。

主要的结点结构与上述双向链表相同，最核心特征是：

  1. 尾结点的next域指向了头结点

  2. 头结点的pre域指向了尾结点

数据结构

定义了一个DoublyCircleLinkedList类，内部有一个Node类型，这是一个链表中的结点类型。数据成员分别是：

  1. Node* next_;

  2. Node* pre_;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class DoublyCircleLinkedList {
    struct Node {
        Node(int data = 0)
            : data_{data},
              next_{nullptr},
              pre_{nullptr} {}
        int data_;
        Node* next_;
        Node* pre_;
    };
  
public:
    DoublyCircleLinkedList();
    ~DoublyCircleLinkedList();

private:
    Node* head_;
};

构造函数

主要做的就是初始化头结点，但与双向链表，将其pre_与next_域初始化为nullptr不同，在双向循环链表中，头结点同样也是尾结点，那么它的next_指向自己，pre_也指向自己

1
2
3
4
5
6

DoublyCircleLinkedList()
    : head_{new Node{0}} {
    // 头结点也是尾结点
    head_->next_ = head_;
    head_->pre_ = head_;
}

当构建一个双向循环链表之后，结构如下：

doubly_linked_list_08.svg

析构函数

析构函数的主要作用就是释放申请的每个结点，包括头结点，以免内存泄露。但是双向循环链表中尾结点的特征是next域指向head，因此，删除结点的步骤分为两个：

  1. 删除链表中除头结点之外的所有有效结点。定义新的指针指向第一个有效结点，循环删除每一个有效结点，删除之前，保存要删除结点的下一个结点的地址，删除之后，将原先保存的下一个结点的地址重新赋值给p

  2. 最后删除头结点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

 ~DoublyCircleLinkedList() {
    // 退化为单向循环链表的析构 
    // 1. 定义新的指针指向要被删除的结点
    Node* p = head_->next_;

    // 2. 先循环删除链表中所有有效结点(不包括头结点)
    while (p != head_) {
        head_->next_ = p->next_;
        delete p;
        p = head_->next_;
    }

    // 3. 删除头结点
    delete head_;
    head_ = nullptr;
}

运算符«重载函数

主要用于输出链表每个结点的信息，用于测试查看。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

std::ostream& operator<<(std::ostream& os, const DoublyCircleLinkedList& dcll) {
    DoublyCircleLinkedList::Node* p = dcll.head_->next_;

    os << "head node: " << "\n";
    os << "ptr: " << dcll.head_ << "\n";
    os << "pre_: " << dcll.head_->pre_ << "\n";
    os << "next_: " << dcll.head_->next_ << "\n";
    os << "\n";

    int count = 1;
    while (p != dcll.head_) {
        os << "node " << count << ": \n";
        os << "ptr: " << p << "\n";
        os << "data: " << p->data_ << "\n";
        os << "pre_: " << p->pre_ << "\n";
        os << "next_: " << p->next_ << "\n";
        os << "\n";
        p = p->next_;
        ++count;
    }

    return os;
}

输出一下此时链表为空时，头结点的next域和pre域的值都是什么，是否都指向head。

1
2
3
4
5

// 测试头结点
void test_head() {
    DoublyCircleLinkedList dcll;
    std::cout << dcll << std::endl;
}

查看输出结果：

1
2
3
4

head node:
ptr: 0x603000001ba0
pre_: 0x603000001ba0
next_: 0x603000001ba0

可以看到，结果是正确的

双向循环链表的头插法O(1)

还是老套路，先进行分析。还是两种情况：

  1. 当前链表中无有效结点，只有一个头结点

  2. 当前链表中除了头结点以外，至少还有一个有效结点

依然先看第二种情况，再使用第二种情况的代码逻辑去分析第一种情况，若需要判断再进行判断。看以下图示：

doubly_linked_list_09.svg

从当前图示可以看出，head指向的是头结点，head→next指向的是Node A，Node A的pre指向的是head。而Node A的next域指向了head，head→pre指向了Node A。根据双向链表的头插法得出一些想法，我们可以先将新结点new_node先插入到第一个位置，先不关心head的pre域和Node A的next域。因为只要保证new_node插入成功，无论是head的pre还是Node A的next都可以被安全的赋值。

  1. 先执行新结点的插入(其实就是双向链表的头插法，还是先看第二种情况，先不判断)

    • 构建新结点new_node

    • new_node→next = head→next;new_node→pre = head;

    • head→next = new_node

    • new_node→next→pre = new_node;

  2. 更新head中pre和Node A也就是尾结点中next的值(当前只有一个有效结点插入新结点的情况)

    • head→pre = new_node→next;

    • new_node→next→next = head;

看一下插入的图示：

doubly_linked_list_10.svg

OK，根据上述的逻辑分析和代码，包括上述的图示，来分析双向循环链表第一种情况的时候是否也可以适用第二种情况，是否需要加上分支判断。还是分为两个比较大的步骤：

  1. 完成新结点的插入(可观察构造函数的图示，这里不放图示)

    • 构建新结点，正确

    • new_node→next = head→next;正确的，因为链表中无有效结点的时候，头结点也是尾结点，那么head→next还是head，所以此时new_node→next指向了头结点

    • new_node→pre = head;正确的，此时的new_node是链表中第一个有效结点，它的pre结点就是head。

    • head→next = new_node;正确的

    • 在双向链表中，由于head→next = nullptr，所以第一种情况不可以直接new_node→next→pre = new_node;因此new_node→next == nullptr了，但是在双向循环链表中，head→next它一开始是等于head的，而此时它的值在一开始就赋值给了new_node→next，因此，new_node→next→pre = new_node也是正确的，只不过new_node→next是head，head→pre指向了new_node。

    忍不住画图，看一下无有效结点插入之前的结点的值：

    doubly_linked_list_11.svg

    head→next指向自己，head→pre指向自己

    插入之后，在观察一下图示：

    doubly_linked_list_12.svg

    注意看，第四步的时候，在双向链表中是需要判断new_node→next是否为nullptr的，但现在new_node→next它是指向head的，不为nullptr，因此new_node→next→pre是正确的

  2. 更新head中的pre和尾结点(在这里其实就是new_node)的next

    还需要更新吗？经过上述情况的讨论，我发现第二种情况讨论更新head中的pre和尾结点的next是错误的，因为如果按照第二种情况的那种讨论，代码如下：

    • head→pre = new_node→next;

    • new_node→next→next = head;

    那么在插入第三个结点的时候呢？这样去执行代码，head→pre = new_node→next指向的是尾结点吗？不是的，指向的是第二个结点，而new_node→next→next = head，是第二个结点的next指向了head，也不是尾结点。

所以，经过分析了第一种情况之后，之前不是分为两个大的步骤吗？现在不需要第二个步骤了，因为你在执行头插法的时候，第一次插入的结点它永远都是尾结点，后续插入的结点都是第一个有效结点，所以在第一种情况插入头结点的时候，尾结点的next和head的pre就已经被确认了。在这之后插入新的结点，也就是第二种情况，无需进行head→pre与尾结点的next的更新了。算是自己分析之后，明白的点，在之前是分析错了，不过这也带来了正确的答案。最核心的点其实就是在双向链表执行头插法的时候，在第一种情况下需要注意new_node→next的值是否为nullptr，而双向循环链表的第一种情况则不需要判断，因为按照自己的插入顺序，new_node→next的值不为nullptr，而为head。

核心代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// 头插法
void insertHead(int val) {
    // 构建新的结点
    Node* new_node = new Node{val};

    // 更新new_node的next与pre
    new_node->next_ = head_->next_;
    new_node->pre_ = head_;

    // 头结点的next指向new_node
    head_->next_ = new_node;

    // new_node的next的pre指向自己
    new_node->next_->pre_ = new_node;
}

上述的分析权当自己的思考过程了，这次按照代码，对第一种情况和第二种情况再次分析，以免出错：

  1. 第一种情况，链表中除了头结点以外无有效结点。此时头结点head→next = head;head→pre = head;

    • 构建新的结点，正确

    • 更新new_node的next与pre，正确，此时new_node作为第一个有效结点，同时也是尾结点。尾结点的特征就是new_node→nex指向head;而上述的代码new_node→next = head→next种，head→next就是head，所以，new_node已经指向了head。head→pre = head;也是正确操作

    • head→next = new_node;使其作为第一个有效结点，也是正确的。

    • new_node→next→pre = new_node;此时不需要判断new_node→next的值，它在之前就被head→next赋值，此时它的值是head。所以head→pre是new_node。正确

    这样一来，在c、d两个步骤内，就将head→pre和尾结点的next确定下来的，在后续的头插新的结点的时候，就无需更新它们的值了。

  2. 第二种情况，链表中除了头结点以外，至少还有一个有效结点。此时head→pre与此时链表中的尾结点的next已经确认了

    • 构建新的结点，正确

    • 更新new_node的pre和next。正确。new_node→next = head→next;此时head→next指向的是原来的第一个有效结点，而新结点要插入，新结点的next肯定是指向原来的第一个有效结点的，正确指向。而new_node→pre = head;新结点要插入进来，是成为新的第一个有效结点，它的前一个结点绝对是head，也是正确的。

    • head→next = new_node;新结点要插入进来，是成为新的第一个有效结点，head的next也一定指向他，正确

    • new_node→next→pre = new_node;新结点成为第一个有效结点之后，原来的第一个有效结点成为了第二个，那么第二个结点的pre就必须是新结点，也是正确的

    • 至于头结点的pre和尾结点的next早早确认下来不会改变。头结点的pre此时指向的是第二个结点，第二个结点的next指向head。因为第二个结点先插入的，它是绝对的尾结点。

测试头插法

  1. 查看每个结点的pre和next是否指向正确

  2. 查看头结点的pre和尾结点的next是否指向正确

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// 测试头插法
void test_insert_head() {
    DoublyCircleLinkedList dcll;

    dcll.insertHead(10);
    dcll.insertHead(5);
    dcll.insertHead(2);
    dcll.insertHead(33);
    dcll.insertHead(32);

    std::cout << dcll << std::endl;
}

值为10的结点，绝对是尾结点，且它的next指向头结点，头结点的pre指向他

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

head node:
ptr: 0x603000001ba0
pre_: 0x603000001bd0
next_: 0x603000001c90

node 1:
ptr: 0x603000001c90
data: 32
pre_: 0x603000001ba0
next_: 0x603000001c60

node 2:
ptr: 0x603000001c60
data: 33
pre_: 0x603000001c90
next_: 0x603000001c30

node 3:
ptr: 0x603000001c30
data: 2
pre_: 0x603000001c60
next_: 0x603000001c00

node 4:
ptr: 0x603000001c00
data: 5
pre_: 0x603000001c30
next_: 0x603000001bd0

node 5:
ptr: 0x603000001bd0
data: 10
pre_: 0x603000001c00
next_: 0x603000001ba0

结果也是正确的，代表上述的头插法代码逻辑也是对的。

双向循环链表的尾插法O(1)

在当前的双向循环链表的数据结构中，没有尾结点，只有一个头结点，因此，在进行尾插入之前，还是和双向链表一样，先找到尾结点。

记住一点，插入的新结点是一直都是尾结点，与头插法相反，头插法插入的新结点一直都是第一个有效结点。还是两种情况：

  1. 当前链表除头结点之外，无有效结点

  2. 当前链表除头结点之外，还有至少一个有效结点

先分析第二种情况：

doubly_linked_list_13.svg

在上述图示中，分析四个步骤，因为我喜欢先将新结点的pre和next域给提前赋值好，因为新结点的next和pre赋值不会丢失结点信息。这四步的大概代码就是：先循环找到尾结点，假设这个尾结点是p。

  1. new_node→next = head; 尾结点指向头结点

  2. new_node→pre = p;p是上图中找到的尾结点，插入的新结点现在成为新的尾结点，它的pre指向上一个尾结点。

  3. p→next = new_node;上一个尾结点的next指向新的尾结点。

  4. 整个双向循环链表的闭环还差一个步骤，那就是头结点的pre指向新的尾结点，也就是head→pre = new_node;也就是图上的第四步，也没问题。

根据上述分析的第二种情况的代码逻辑和操作顺序，来去分析一下是否符合第一种情况，先记得一个前提，第一种情况下的头结点，头结点的pre和next都指向自己，都是head，head此时也是尾结点，也假设是p。

先循环找到尾结点，在第一种情况下，头结点也即是尾结点，所以head也是尾结点

  1. new_node→next = head;第一种情况下，新插入的结点是尾结点，它的next指向头结点head。

  2. new_node→pre = p;第二种情况下，新插入的结点是尾结点，同时也是第一个有效结点，它的前一个结点是头结点，是head，也是正确的。

  3. p→next = new_node;头结点的下一个结点也是第一个有效结点

  4. head→pre = new_node;

与第二种情况的代码逻辑完全符合，插入的代码逻辑符合，那么先看看循环找到尾结点的代码逻辑是否符合，双向循环链表中尾结点的特点是它的next域指向head

  1. 定义一个新的指针p指向头结点

  2. 循环终止条件p→next_ ≠ head;

当循环退出的时候，p此时指向尾结点。对于第二种情况，符合。对于第一种情况，p一开始指向head，p→next的值也就是head→next的值，也就是head，所以循环就未进入，p指向的head就是尾结点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// 尾插法
void insertTail(int val) {
    // 循环找到当前链表中的尾结点
    Node* p = head_;
    while (p->next_ != head_) {
        p = p->next_;
    }

    // 构建新的结点
    Node* new_node = new Node{val};

    // 更新新结点的next与pre
    new_node->next_ = head_;
    new_node->pre_ = p;

    // 更新尾结点的next
    p->next_ = new_node;

    // 头结点的pre指向新的尾结点
    head_->pre_ = new_node;
}

更改：脑子抽抽了，在双向循环链表中，根本不需要寻找尾结点，哎呦，脑子抽抽了，这才反应过来，尾结点的地址那不就在头结点的pre存着了吗？更改代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// 尾插法
void insertTail(int val) {
    // 尾结点就是head->pre
    Node* p = head_->pre_;

    // 构建新的结点
    Node* new_node = new Node{val};

    // 更新新结点的next与pre
    new_node->next_ = head_;
    new_node->pre_ = p;

    // 更新尾结点的next，指向新的尾结点
    p->next_ = new_node;

    // 头结点的pre指向新的尾结点
    head_->pre_ = new_node;
}

测试尾插法

测试代码，分别插入10、20、30、40四个结点：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// 测试尾插法
void test_insert_tail() {
    DoublyCircleLinkedList dcll;

    dcll.insertTail(10);
    dcll.insertTail(20);
    dcll.insertTail(30);
    dcll.insertTail(40);

    std::cout << dcll << std::endl;
}

查看输出结果：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

head node:
ptr: 0x603000001ba0
pre_: 0x603000001c60
next_: 0x603000001bd0

node 1:
ptr: 0x603000001bd0
data: 10
pre_: 0x603000001ba0
next_: 0x603000001c00

node 2:
ptr: 0x603000001c00
data: 20
pre_: 0x603000001bd0
next_: 0x603000001c30

node 3:
ptr: 0x603000001c30
data: 30
pre_: 0x603000001c00
next_: 0x603000001c60

node 4:
ptr: 0x603000001c60
data: 40
pre_: 0x603000001c30
next_: 0x603000001ba0

head的pre的值是值为40的结点的地址，值为40的结点作为尾结点，它的next值是head的地址值。其他结点的pre和next值也都是正确

双向循环链表的按值删除单个结点O(n)

有个小技巧，先进行分类讨论删除的结点是否是尾结点，在看两者的代码逻辑之间是否有相同之处，若有，则直接取消分支判断，合为一起

还要记的一个点就是双向循环链表没有任何一个结点中的pre和next是为nullptr的，就连只有头结点的链表，头结点中的next和pre也都是指向自己，而不是为nullptr。它与双向链表是不同的。

单向循环链表与单向链表也是不同的，单向循环链表中，没有任何一个结点的next域是为nullptr的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 按值删除单个结点
void remove(int val) {
    // 定义新的指针指向要删除的结点
    Node* p = head_->next_;

    while (p != head_) {
        // 若p指向的结点的值等于val
        if (p->data_ == val) {
            // p指向的不是尾结点
            if (p->next_ != head_) {
                p->pre_->next_ = p->next_;
                p->next_->pre_ = p->pre_;
            } else {  // 是尾结点
                p->pre_->next_ = p->next_;
                p->next_->pre_ = p->pre_;
            }
            delete p;
            break;
        } else {
            p = p->next_;
        }
    }
}

看上述的代码，不同分支下的代码完全相同，直接合并

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// 按值删除单个结点
void remove(int val) {
    // 定义新的指针指向要删除的结点
    Node* p = head_->next_;

    while (p != head_) {
        // 若p指向的结点的值等于val
        if (p->data_ == val) {
            p->pre_->next_ = p->next_;
            p->next_->pre_ = p->pre_;
            delete p;
            break;
        } else {
            p = p->next_;
        }
    }
}

测试按值删除单个结点

插入若干个数据，查看删除之前的链表数据

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// 测试remove
void test_remove() {
    DoublyCircleLinkedList dcll;

    dcll.insertTail(10);
    dcll.insertTail(20);
    dcll.insertTail(30);
    dcll.insertTail(40);

    std::cout << dcll << std::endl;
}

查看输出结果：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

head node:
ptr: 0x603000001ba0
pre_: 0x603000001c60
next_: 0x603000001bd0

node 1:
ptr: 0x603000001bd0
data: 10
pre_: 0x603000001ba0
next_: 0x603000001c00

node 2:
ptr: 0x603000001c00
data: 20
pre_: 0x603000001bd0
next_: 0x603000001c30

node 3:
ptr: 0x603000001c30
data: 30
pre_: 0x603000001c00
next_: 0x603000001c60

node 4:
ptr: 0x603000001c60
data: 40
pre_: 0x603000001c30
next_: 0x603000001ba0

删除值为40的结点，也就是最后一个结点：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// 测试remove
void test_remove() {
    DoublyCircleLinkedList dcll;

    dcll.insertTail(10);
    dcll.insertTail(20);
    dcll.insertTail(30);
    dcll.insertTail(40);

    dcll.remove(40);

    std::cout << dcll << std::endl;
}

查看输出结果：值为30的结点成为尾结点，它的next域是否指向头结点，头结点的pre是否指向值为30的结点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

head node:
ptr: 0x603000001ba0
pre_: 0x603000001c30
next_: 0x603000001bd0

node 1:
ptr: 0x603000001bd0
data: 10
pre_: 0x603000001ba0
next_: 0x603000001c00

node 2:
ptr: 0x603000001c00
data: 20
pre_: 0x603000001bd0
next_: 0x603000001c30

node 3:
ptr: 0x603000001c30
data: 30
pre_: 0x603000001c00
next_: 0x603000001ba0

双向循环链表的按值删除多个结点O(n)

还是在删除之前，讨论删除的结点是否是尾结点，在看每个分支的代码逻辑是否有相同的地方可合并

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// 按值删除多个结点
void remove_all(int val) {
    // 定义新指针指向第一个有效结点
    Node* p = head_->next_;

    while (p != head_) {
        if (p->data_ == val) {
            // 若删除的是尾结点
            if (p->next_ == head_) {
                p->next_->pre_ = p->pre_;
                p->pre_->next_ = p->next_;
                delete p;
                break;
            } else {  // 若不是尾结点，需要重置p的值
                p->next_->pre_ = p->pre_;
                p->pre_->next_ = p->next_;
                // 删除结点之前，保存p->next的值
                Node* q = p->next_;
                delete p;
                p = q;
            }
        } else {
            p = p->next_;
        }
    }
}

还是可以简单的合并一下的，两个分支下的前两行代码是一样的，且执行之后的代码逻辑无非是直接删除结点，结束循环；要么是重置p指针的值，继续循环删除

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// 按值删除多个结点
void remove_all(int val) {
    // 定义新指针指向第一个有效结点
    Node* p = head_->next_;

    while (p != head_) {
        if (p->data_ == val) {
            p->next_->pre_ = p->pre_;
            p->pre_->next_ = p->next_;

            // 若p指向的结点是尾结点
            if (p->next_ == head_) {
                delete p;
                break;
            } else {  // 若不是尾结点
                Node* q = p->next_;
                delete p;
                p = q;
            }
        } else {
            p = p->next_;
        }
    }
}

更改：

借鉴双向链表中的按值删除多个结点的思想，还可以进行合并

  1. 若p→next指向的不是尾结点，q保存的是p→next的值，删除p，重置p的值，继续循环删除

  2. 若p→next指向的是尾结点，q依然可以保存p→next的值，删除p，重置p的值，此时p的值为head，循环条件不符合，循环终止，达到所要的目的

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// 按值删除多个结点
void remove_all(int val) {
    // 定义新指针指向第一个有效结点
    Node* p = head_->next_;

    while (p != head_) {
        if (p->data_ == val) {                
            p->next_->pre_ = p->pre_;
            p->pre_->next_ = p->next_;

            Node* q = p->next_;
            delete p;
            p = q;
        } else {
            p = p->next_;
        }
    }
}

测试按值删除多个结点

插入若干数据，查看删除之前的链表的数据

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void test_remove_all() {
    DoublyCircleLinkedList dcll;

    dcll.insertTail(10);
    dcll.insertTail(20);
    dcll.insertTail(30);
    dcll.insertTail(20);
  
    std::cout << dcll << std::endl;
}

查看输出结果：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

head node:
ptr: 0x603000001ba0
pre_: 0x603000001c60
next_: 0x603000001bd0

node 1:
ptr: 0x603000001bd0
data: 10
pre_: 0x603000001ba0
next_: 0x603000001c00

node 2:
ptr: 0x603000001c00
data: 20
pre_: 0x603000001bd0
next_: 0x603000001c30

node 3:
ptr: 0x603000001c30
data: 30
pre_: 0x603000001c00
next_: 0x603000001c60

node 4:
ptr: 0x603000001c60
data: 20
pre_: 0x603000001c30
next_: 0x603000001ba0

删除值为20的结点，查看输出结果，重点观察头结点的pre与删除之后尾结点的next的指向

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

head node:
ptr: 0x603000001ba0
pre_: 0x603000001c30
next_: 0x603000001bd0

node 1:
ptr: 0x603000001bd0
data: 10
pre_: 0x603000001ba0
next_: 0x603000001c30

node 2:
ptr: 0x603000001c30
data: 30
pre_: 0x603000001bd0
next_: 0x603000001ba0

嗯，还不错。

根据合并的经验来看，先在草稿纸上或者画图讨论多个分支的情况，先进行最小合并，再看代码多一些的分支下的代码放到代码少一些的分支下是否也能满足，这样可尽量减少一些分支。