C++实现双链表【每一步详细深入讲解，代码清晰、简单、易懂】_双向链表c++实现

一、双链表的结构（以数据为不重复整数为例）

0、overview

双链表节点由存储的数据、指向前一个元素的指针和指向后一个元素的指针构成，因此双联表节点的代码也很容易得到，如下：

// 双链表节点
struct DoubleListNode {
    int data;
    DoubleListNode* prev;
    DoubleListNode* next;
    DoubleListNode(int val);
};
1
2
3
4
5
6
7

双链表和单链表类似，也需要添加、删除和查找。

// 双链表
class DoubleList {
public:
    DoubleListNode* dummy;
public:
    DoubleList();
    ~DoubleList();
public:
    void add(int);
    void remove(int);
    DoubleListNode* find(int);
};
1
2
3
4
5
6
7
8
9
10
11
12

1、插入操作

插入的情况说明：插入每次都在第一个位置插入，也就是在伪头节点（不含元素）后插入。

插入节点的过程：

• 先将目标节点的next指向dummy的下一个节点
• 同时将目标节点的prev指向dummy节点。
• 将dummy的下一个节点的prev指针指向目标节点（如果后面没有元素则省略）
• 将dummy节点的next指针指向目标节点

插入的代码逻辑：

• 查找目标数据是否在链表中已存在
• 如果存在输出错误信息
• 如果不存在，执行插入操作

void DoubleList::add(int val) {
    auto ptr = find(val);
    if (ptr) {
        std::cerr << val << "exists, add failed!" << std::endl;
    } else {
        auto temp = new DoubleListNode(val);
        temp->next = dummy->next;
        temp->prev = dummy;
        if (dummy->next)
        	dummy->next->prev = temp;
        dummy->next = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2、删除操作

• 将目标节点的下一个节点的prev指针指向目标节点的前一个节点（目标节点下一个节点不存在则省略）
• 将目标节点的前一个节点的next指针指向目标节点的下一个节点

代码逻辑：

• 查找目标节点
• 如果不存在，输出错误信息
• 如果存在，执行删除操作，之后delete

void DoubleList::remove(int val) {
    auto ptr = find(val);
    if (ptr == nullptr) {
        std::cerr << val << " does not exist, remove failed!" << std::endl;
    } else {
        if (ptr->next)
        	ptr->next->prev = ptr->prev;
        ptr->prev->next = ptr->next;
        delete ptr;
    }
}
1
2
3
4
5
6
7
8
9
10
11

3、查找操作

不同于单链表，双链表查找直接返回目标节点，对于删除操作十分方便。逻辑基本与单链表一致。

代码逻辑：

• 遍历链表
• 如果找到，直接返回该节点
• 如果没找到，返回nullptr

DoubleListNode* DoubleList::find(int val) {
    auto temp = dummy->next;
    while (temp) {
        if (temp->data == val)
            return temp;
     	temp = temp->next;
    }
    return nullptr;
}
1
2
3
4
5
6
7
8
9

循环链表的不同之处：

循环链表在初始化时，伪头节点的prev和next指针都指向本身。经理各种操作过后，链表的最后一个节点的next指针指向dummy，伪头节点的prev指针指向最后一个节点。

链表改为循环链表之后，添加删除操作都没影响，只有在构造以及一些需要判断链表是否到尾部的地方（如查找、析构、和测试代码）

循环链表的查找代码：

DoubleListNode* DoubleList::find(int val) {
    auto temp = dummy->next;
    while (temp != dummy) { // 改为不等于dummy节点
        if (temp->data == val)
            return temp;
     	temp = temp->next;
    }
    return nullptr;
}
1
2
3
4
5
6
7
8
9

4、完整代码

// DoubleList.h双链表类定义

// 双链表节点
struct DoubleListNode {
    int data;
    DoubleListNode* prev;
    DoubleListNode* next;
    DoubleListNode(int val);
};

// 双链表
class DoubleList {
public:
    DoubleListNode* dummy;
public:
    DoubleList();
    ~DoubleList();
public:
    void add(int);
    void remove(int);
    DoubleListNode* find(int);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// DoubleList.cpp双链表成员函数实现
#include <iostream>

#include "DoubleList.h"

DoubleListNode::DoubleListNode(int val) 
    : data(val), prev(nullptr), next(nullptr) { }

DoubleList::DoubleList() : dummy(new DoubleListNode(-1)) {
    dummy->prev = nullptr;
    dummy->next = nullptr;
}

DoubleList::~DoubleList() {
    auto ptr = dummy->next;
    while (ptr) {
        auto temp = ptr;
        ptr = ptr->next;
        delete temp;
        std::cout << "Element Deleted!" << std::endl;
    }
    delete dummy;
    std::cout << "DoubleList destoryed!" << std::endl;
}

void DoubleList::add(int val) {
    auto ptr = find(val);
    if (ptr) {
        std::cerr << val << "exists, add failed!" << std::endl;
    }
    else {
        auto temp = new DoubleListNode(val);
        temp->next = dummy->next;
        temp->prev = dummy;
        if (dummy->next)
            dummy->next->prev = temp;
        dummy->next = temp;
    }
}

void DoubleList::remove(int val) {
    auto ptr = find(val);
    if (ptr == nullptr) {
        std::cerr << val << " does not exist, remove failed!" << std::endl;
    }
    else {
        if (ptr->next)
            ptr->next->prev = ptr->prev;
        ptr->prev->next = ptr->next;
        delete ptr;
    }
}

DoubleListNode* DoubleList::find(int val) {
    auto temp = dummy->next;
    while (temp) {
        if (temp->data == val)
            return temp;
        temp = temp->next;
    }
    return 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

// DoubleListTest.cpp 双链表测试代码
#include <iostream>
#include "DoubleList.h"

int main(void) {
	DoubleList list;

	list.add(0);
	list.add(1);
	list.add(2);
	list.add(3);
	list.add(4);
	list.add(4);	// 添加已存在元素
	list.remove(0); // 末尾元素
	list.remove(2); // 中间元素
	list.remove(4); // 开头元素
	list.remove(4); // 删除不存在元素
	for (auto temp = list.dummy->next; temp; temp = temp->next)
		std::cout << temp->data << " ";
	std::cout << std::endl;
	/*期望的输出
	4 exists, add failed!
	4 does not exist, remove failed!
	3 1
	Element deleted!
	Element deleted!
	DoubleList Destroyed!
	*/
	return 0;
}
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

5、循环链表代码

// DoubleList.h 双循环链表类定义

// 双链表节点
struct DoubleListNode {
    int data;
    DoubleListNode* prev;
    DoubleListNode* next;
    DoubleListNode(int val);
};

// 双链表
class DoubleList {
public:
    DoubleListNode* dummy;
public:
    DoubleList();
    ~DoubleList();
public:
    void add(int);
    void remove(int);
    DoubleListNode* find(int);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// DoubleList.cpp 双循环链表成员函数实现
#include <iostream>

#include "DoubleList.h"

DoubleListNode::DoubleListNode(int val)
    : data(val), prev(nullptr), next(nullptr) { }

DoubleList::DoubleList() : dummy(new DoubleListNode(-1)) {
    dummy->prev = dummy; // nullptr改为dummy
    dummy->next = dummy; // nullptr改为dummy
}

DoubleList::~DoubleList() {
    auto ptr = dummy->next;
    while (ptr != dummy) { // 改为不等于dummy
        auto temp = ptr;
        ptr = ptr->next;
        delete temp;
        std::cout << "Element deleted!" << std::endl;
    }
    delete dummy;
    std::cout << "DoubleList destoryed!" << std::endl;
}

void DoubleList::add(int val) {
    auto ptr = find(val);
    if (ptr) {
        std::cerr << val << "exists, add failed!" << std::endl;
    }
    else {
        auto temp = new DoubleListNode(val);
        temp->next = dummy->next;
        temp->prev = dummy;
        if (dummy->next)
            dummy->next->prev = temp;
        dummy->next = temp;
    }
}

void DoubleList::remove(int val) {
    auto ptr = find(val);
    if (ptr == nullptr) {
        std::cerr << val << " does not exist, remove failed!" << std::endl;
    }
    else {
        if (ptr->next)
            ptr->next->prev = ptr->prev;
        ptr->prev->next = ptr->next;
        delete ptr;
    }
}

DoubleListNode* DoubleList::find(int val) {
    auto temp = dummy->next;
    while (temp != dummy) { // 改为不等于dummy
        if (temp->data == val)
            return temp;
        temp = temp->next;
    }
    return 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

// DoubleListTest.cpp 双链表测试代码
#include <iostream>
#include "DoubleList.h"

int main(void) {
	DoubleList list;

	list.add(0);
	list.add(1);
	list.add(2);
	list.add(3);
	list.add(4);
	list.add(4);	// 添加已存在元素
	list.remove(0); // 末尾元素
	list.remove(2); // 中间元素
	list.remove(4); // 开头元素
	list.remove(4); // 删除不存在元素
	for (auto temp = list.dummy->next; temp != list.dummy; temp = temp->next)
		std::cout << temp->data << " ";
	std::cout << std::endl;
	/*期望的输出
	4 exists, add failed!
	4 does not exist, remove failed!
	3 1
	Element deleted!
	Element deleted!
	DoubleList Destroyed!
	*/
	return 0;
}
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