C++数据结构之：链List

摘要：

  it人员无论是使用哪种高级语言开发东东，想要更高效有层次的开发程序的话都躲不开三件套：数据结构，算法和设计模式。数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

  此系列专注讲解数据结构数组、链表、队列、栈、树、哈希表、图，通过介绍概念以及提及一些可能适用的场景，并以C++代码简易实现，多方面认识数据结构，最后为避免重复造轮子会浅提对应的STL容器。本文介绍的是链List。

（开发环境：VScode，C++17）

关键词： C++，数据结构，链表，List

声明：本文作者原创，转载请附上文章出处与本文链接。

正文：

介绍：

  链表（Linked List）是一种常见的数据结构，它通过一系列的节点（Node）来存储数据，每个节点包含两个部分：一个是数据域（Data Field），用于存储数据；另一个是链接域（Link Field），用于存储指向下一个节点的引用（在单链表中）或前一个节点和下一个节点的引用（在双向链表中）。链表数据一般都是分散存储于内存中 的，无须存储在连续空间内。

双向链表：

特性：

• 动态性：链表不需要在内存中预先分配固定大小的空间，可以根据需要动态地创建和删除节点。这使得链表在处理不确定大小的数据集合时非常灵活。
• 多种类型：链表有多种类型，包括单向链表、双向链表、循环链表等。每种类型的链表都有其特定的应用场景和优缺点。
• 插入和删除效率高：在链表中插入或删除一个节点时，只需要修改相关节点的指针（或引用）即可，而不需要移动大量数据。
• 非连续性：链表中的节点在内存中不一定是连续存储的。每个节点都包含一个指向下一个节点的指针（或引用），这些指针（或引用）将节点连接在一起。

应用：

• 实现堆栈（Stack）和队列（Queue）等抽象数据类型。
• 在数据库中实现邻接列表来表示图（Graph）。
• 在浏览器中表示历史记录或书签。
• 在操作系统中表示进程列表或文件列表。
• 在许多算法中，如归并排序（Merge Sort）和快速排序（Quick Sort）的链表实现等。

代码实现：

#clist.h
#ifndef CLIST_H
#define CLIST_H
#include <iostream>
#include <cstdlib>

using namespace std;
// 链表结点
template <class T>
class DNode
{
public:
    DNode<T> *next;
    DNode<T> *prev;
    T data;
};

// 双向列表类
template <class T>
class CList
{
public:
    CList();                     // 默认构造函数
    CList(const CList& ln);      // 拷贝构造函数
    ~CList();                    // 析构函数

    void add(T e);               // 向链表添加数据
    void remove(T index);        // 移除某个结点
    T find(int index);           // 查找结点
    bool empty();                // 判断是否为空

    int size();                  // 链表长度
    void print();                // 显示链表
    void print_reverse();        // 链表反向显示

    void clear();                // 删除全部结点
private:
    DNode<T> *head;
    DNode<T> *tail;
    int length;
};

// 默认构造函数
template <typename T>
CList<T>::CList()
{
    head = new DNode<T>;
    tail = new DNode<T>;
    head->next = tail;
    head->prev = nullptr;
    tail->next = nullptr;
    tail->prev = head;
    length = 0;
}

// 拷贝构造函数
template <typename T>
CList<T>::CList(const CList &ln)
{
    head = new DNode<T>;
    head->prev = nullptr;
    tail = new DNode<T>;
    head->next = tail;
    tail->prev = head;
    length = 0;
    DNode<T>* temp = ln.head;

    while (temp->next != ln.tail){
        temp = temp->next;
        tail->data = temp->data;
        DNode<T> *p = new DNode<T>;
        p->prev = tail;
        tail->next = p;
        tail = p;
        length++;
    }
    tail->next = nullptr;
}

// 析构函数
template <typename T>
CList<T>::~CList()
{
    if (length == 0){
        delete head;
        delete tail;
        head = nullptr;
        tail = nullptr;
        return;
    }
    while (head->next != nullptr){
        DNode<T> *temp = head;
        head = head->next;
        delete temp;
    }
    delete head;
    head = nullptr;
}

// 向链表添加数据
template <typename T>
void CList<T>::add(T e)
{
    DNode<T>* temp = this->tail;
    tail->data = e;
    tail->next = new DNode<T>;
    DNode<T> *p = tail;
    tail = tail->next;
    tail->prev = p;
    tail->next = nullptr;
    length++;
}

// 查找结点
template <typename T>
T CList<T>::find(int index)
{
    if (length == 0){
        cout << "CList is empty";
        return -1;
    }
    if (index >= length){
        cout << "Out of bounds";
        return -1;
    }
    int x = 0;
    DNode<T> *p;
    p = head->next;
    while (p->next != nullptr && x++ != index){
        p = p->next;
    }

    return p->data;
}

// 删除结点
template <typename T>
void CList<T>::remove(T index)
{
    if (length == 0){
        cout << "CList is empty";
        return;
    }
    DNode<T> *p = head;
    while (p->next != nullptr){
        p = p->next;
        if (p->data == index){
            DNode<T> *temp = p->prev;
            temp->next = p->next;
            p->next->prev = temp;
            delete p;
            length--;
            return;
        }
    }
}

// 删除所有结点
template <typename T>
void CList<T>::clear()
{
    if (length == 0){
        return;
    }
    DNode<T> *p = head->next;
    while (p != tail){
        DNode<T>* temp = p;
        p = p->next;
        delete temp;
    }
    head->next = tail;
    tail->prev = head;
    length = 0;
}

// 判断是否为空
template <typename T>
bool CList<T>::empty()
{
    if (length == 0){
        return true;
    }
    else {
        return false;
    }
}

// 链表长度
template <typename T>
int CList<T>::size()
{
    return length;
}

// 输出链表
template <typename T>
void CList<T>::print()
{
    if (length == 0){
        cout << "CList is empty" << endl;
        return;
    }
    DNode<T> *p = head->next;
    while (p != tail){
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 反向输出链表
template <typename T>
void CList<T>::print_reverse()
{
    if (length == 0)return;
    DNode<T> *p = tail->prev;
    while (p != head){
        cout << p->data << " ";
        p = p->prev;
    }
    cout << endl;
}

#endif // !CLIST_H
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224

#clist.cpp
#include "clist.h"
#include <iostream>
using namespace std;

int main(int argc, char**argv)
{
    CList<int> list;
    list.add(6);
    list.add(443);
    list.add(767);
    list.add(56);

    CList<int> list2(list);
    list2.print_reverse();
    list2.print();
    cout << "list2.size(): " << list2.size() << endl;
    cout << "list2.find(2): " << list2.find(2) << endl;
    list2.remove(443);
    list2.print();

    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

对应STL：

• list：

  双向循环链表。使用起来很高效，对于任意位置的插入和删除都很快，在操作过后，以后指针、迭代器、引用都不会失效。

• forward_list：

  单向链表。只支持单向访问，在链表的任何位置进行插入/删除操作都非常快

推荐阅读

C/C++专栏：https://blog.csdn.net/weixin_45068267/category_12268204.html
(包含其它数据结构即对应的STL容器使用)