Drunkmars's Blog

C++链表实现

字数统计: 3k阅读时长: 12 min
2021/06/15

本文对C++链表记录一些学习笔记以及代码实现。

链表的特点

1
2
3
4
5
1、数据分散存储			

2、查询性能没有Vector好

3、新增与删除的性能好于Vector

为何会出现链表

第一次学习线性表一定会马上接触到一种叫做顺序表(顺序存储结构),经过上一篇的分析顺序表的优缺点是很显然的,它虽然能够很快的访问读取元素,但是在解决如插入和删除等操作的时候,却需要移动大量的元素,效率较低,那么是否有一种方法可以改善或者解决这个问题呢?

首先我们需要考虑,为什么顺序表中的插入删除操作会涉及到元素的移动呢?

好家伙,问题就是围绕着顺序表的最大的特点出现的——顺序存储,相邻放置元素,也就是说每个元素都是根据编号一个一个挨着的,这就导致了 插入或删除后,为了仍然呈顺序线性存储,被操作元素后面的元素的位置均需要发生一定的变化,你应该能想象得到,在拥挤的队伍中突然从中插入一个学生的场景,后面浩浩荡荡的人群,口吐芬芳的向后挪了一个空位,如果人群过大,重新排好队也需要一定的时间

好嘛,人与人之间别这么挤在一起,每个人与人之间都流出一点空隙来,留一定的位置出来,好了,这好像是个办法,但是负责一个一个与学生交流填表的老师可就不干了,这意味着我(找人)遍历的时候,需要多跑好多路,浪费好多时间,先不说这个,体院馆又不行了,你们这么个摆法,我这小馆可放不下,这也就意味着空间复杂度增加了很多

我们刚才所围绕的都是在 “排队” 的基本前提下的,但我们能想到的方法并不是很理想,那么我们索性就不排队了,是不是能有更好的解决方式呢?

一个有效的方法:

让同学们(元素)自己找位置随便站,不过你要知道相对于自己下一位同学的位置,这样既解决了空间上的问题,又能通过这种两两联系的方式访问(遍历)到整个队伍(数组),最重要的是,插入和离开同学,由于同学(元素)之间不存在了那种排队,相邻的特点,所以也不会说影响到过多的同学(元素)只需要和你插入位置的前后两位同学沟通好就行了,反正别人也不知道你们之间发生了什么事

好了思路是有了,我们来看一种最常见的链表——单链表

链表的类型

链表主要分为单链表、循环链表、双向链表

image-20210615000439694

链表的结构

链表中的每个结点都包含一个或多个保存数据的成员。例如,存储在结点中的数据可以是库存记录;或者它可以是由客户的姓名、地址和电话号码等组成的客户信息记录。

除了数据之外,每个结点还包含一个后继指针指向链表中的下一个结点。

img

非空链表的第一个结点称为链表的头。要访问链表中的结点,需要有一个指向链表头的指针。从链表头开始,可以按照存储在每个结点中的后继指针访问链表中的其余结点。最后一个结点中的后继指针被设置为 nullptr 以指示链表的结束。

因为指向链表头的指针用于定位链表的头部,所以也可以认为它代表了链表头。同样的指针也可以用来定位整个链表,从头开始,后面跟着后续指针,所以也可以很自然地把它看作是代表了整个链表。

图 2 给出了一个由 3 个结点组成的链表,其中显示了指向头部的指针,链表的 3 个结点以及表示链表末尾的 nullptr 指针。

img

注意,图 2 中绘制的链表结点彼此非常接近,排列整齐。实际上,链表结点可能散布在内存的各个部分。

在链表中新增节点

这里先放一下自己对于新增节点的分析,这里主要是对函数实现的分析,主要有三种情况:

1
2
3
4
5
在链表头处添加

在链表尾部添加

在链表中添加

img

img

这里再放一下比较完整的新增节点的类型

创建头节点

  

手动new一个新的Node,将Node的next置为NULL即可。

1
head = new Node(0);head->next = NULL;

img

从头插入一个新的节点

手动new出一个新的节点p,使p的next的指向head->next所指向的地址,然后将head->next从新指向p即可。

1
Node * p = new Node(int);  p->next = head->next;  head->next = p;

img

删除指定节点

 

先遍历到指定节点的前一个节点,然后通过将前一个节点的next指针指向指定节点的下一个节点,达到悬空指定节点的效果,然后删除指定节点即可。

img

修改指定节点

  

遍历到指定节点的位置,将其data修改为要修改的值即可。

img

链表反转

  

定义三个临时节点指向头结点之后的第1个节点p,第2个节点q和第3个节点m。将p->next置为空,然后将q->next = p,然后将p向后移动一个节点,即p = q,最后将q向后移动一个节点,即q = m,最后把m向后移动一个节点,即m = m->next;依此类推直到m等于NULL,然后将q->next = p,最后将head->next指向q(即目前第一个节点疑,也就是原本最后的一个节点)。

  通过三个节点达到从头开始逐个逆序的目的。

img

代码实现

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
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
// cplus链表.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <Windows.h>
#define SUCCESS 1 // 执行成功
#define ERROR -1 // 执行失败
#define INDEX_IS_ERROR -2 // 错误的索引号
#define BUFFER_IS_EMPTY -3 // 缓冲区已空


template <class T_ELE>
class LinkedList
{
public:
LinkedList();
~LinkedList();
public:
BOOL IsEmpty(); //判断链表是否为空 空返回1 非空返回0
void Clear(); //清空链表
DWORD GetElement(IN DWORD dwIndex,OUT T_ELE& Element); //根据索引获取元素
DWORD GetElementIndex(IN T_ELE& Element); //根据元素获取链表中的索引
DWORD Insert(IN T_ELE Element); //新增元素
DWORD Insert(IN DWORD dwIndex, IN T_ELE Element); //根据索引新增元素
DWORD Delete(IN DWORD dwIndex); //根据索引删除元素
DWORD GetSize(); //获取链表中元素的数量
private:
typedef struct _NODE
{
T_ELE Data;
_NODE* pNext;
}NODE,*PNODE;
PNODE GetIndexCurrentNode(DWORD dwIndex); //获取索引为dwIndex的指针
PNODE GetIndexPreviousNode(DWORD dwIndex); //获取索引为dwIndex的前一个节点指针
PNODE GetIndexNextNode(DWORD dwIndex); //获取索引为dwIndex的后一个节点指针
private:
PNODE m_pList; //链表头指针,指向第一个节点
DWORD m_dwLength; //元素的数量
};

//无参构造函数 初始化成员
template<class T_ELE> LinkedList<T_ELE>::LinkedList()
:m_pList(NULL),m_dwLength(0)
{

}

//析构函数 清空元素
template<class T_ELE> LinkedList<T_ELE>::~LinkedList()
{
Clear();
printf("The destructor has already been executed!");
}

//获取dwIndex前面节点的地址
template<class T_ELE>
LinkedList<T_ELE>::PNODE LinkedList<T_ELE>::GetIndexPreviousNode(DWORD dwIndex)
{
PNODE ptempNODE = m_pList;

for (int w = 0 ; w < dwIndex - 1; w++)
{
ptempNODE = ptempNODE->pNext;
}

return ptempNODE;

}
//获取dwIndex节点的地址
template<class T_ELE>
LinkedList<T_ELE>::PNODE LinkedList<T_ELE>::GetIndexCurrentNode(DWORD dwIndex)
{
PNODE ptempNODE = m_pList;

for (int w = 0 ; w < dwIndex; w++)
{
ptempNODE = ptempNODE->pNext;
}

return ptempNODE;

}
//获取dwIndex后面节点的地址
template<class T_ELE>
LinkedList<T_ELE>::PNODE LinkedList<T_ELE>::GetIndexNextNode(DWORD dwIndex)
{
PNODE ptempNODE = m_pList;

for (int w = 0 ; w < dwIndex + 1; w++)
{
ptempNODE = ptempNODE->pNext;
}

return ptempNODE;
}

//判断链表是否为空
template<class T_ELE> BOOL LinkedList<T_ELE>::IsEmpty()
{
if ( m_pList == NULL || m_dwLength == 0)
{
return true;
}
else
{
return false;
}

}
//清空链表
template<class T_ELE> void LinkedList<T_ELE>::Clear()
{
PNODE pNode = m_pList;
PNODE ptemp = pNode->pNext;

// 1. 判断链表是否为空

if ( m_pList == NULL || m_dwLength == 0)

return ;

// 2. 循环删除链表中的节点

for (int i = 0 ; i < m_dwLength; i++)
{
delete pNode;
pNode = ptemp;
}

// 3. 删除最后一个节点并将链表长度置为0

m_dwLength = 0;

}

//根据索引获取元素
template<class T_ELE> DWORD LinkedList<T_ELE>::GetElement(IN DWORD dwIndex,OUT T_ELE& Element)
{
PNODE ptemp = m_pList;

// 1. 判断索引是否有效

if (dwIndex < 0 || dwIndex >= m_dwLength)
{
return INDEX_IS_ERROR;
}

// 2. 取得索引指向的节点

for (int k = 0; k < dwIndex; k++)
{
ptemp = ptemp->pNext;
}

// 3. 将索引指向节点的值复制到OUT参数

memcpy(&Element, ptemp, sizeof(T_ELE));
return SUCCESS;

}
//根据元素内容获取索引
template<class T_ELE> DWORD LinkedList<T_ELE>::GetElementIndex(IN T_ELE& Element)
{
PNODE ptemp = m_pList;

// 1. 判断链表是否为空

if(IsEmpty())
{
return BUFFER_IS_EMPTY;
}

// 2. 循环遍历链表,找到与Element相同的元素

for (int t = 0; t < m_dwLength; t++)
{
if (!memcmp(ptemp, &Element, sizeof(T_ELE)))
{
printf("The value is %d,find successfully!",t);
return t;
}
ptemp = ptemp->pNext;
}
retrun SUCCESS;

}
//在链表尾部新增节点
template<class T_ELE> DWORD LinkedList<T_ELE>::Insert(IN T_ELE Element)
{
PNODE pNewNode = new NODE;
PNODE pTempNode = m_pList;
memset(pNewNode, 0, sizeof(NODE));
memcpy(pNewNode, &Element, sizeof(T_ELE));

// 1. 判断链表是否为空

if(IsEmpty())
{
m_pList = pNewNode;
m_dwLength++;
return SUCCESS;
}
// 2. 如果链表中已经有元素

for ( int q = 0 ; q < m_dwLength - 1 ; q++)
{
pTempNode = pTempNode->pNext;
}
pTempNode->pNext = pNewNode;
m_dwLength++;
return SUCCESS;

}
//将节点新增到指定索引的位置
template<class T_ELE> DWORD LinkedList<T_ELE>::Insert(IN DWORD dwIndex, IN T_ELE Element)
{
PNODE pPreviousNode = NULL;
PNODE pCurrentNode = NULL;
PNODE pNewNode = new NODE;
memset(pNewNode, 0, sizeof(NODE));
memcpy(pNewNode, &Element, sizeof(T_ELE));

// 1. 判断链表是否为空

if(IsEmpty())
{
if ( !dwIndex)
{
return ERROR;
}
Insert(Element);
}

// 2. 判断索引值是否有效

if ( dwIndex < 0 || dwIndex > m_dwLength)
{
printf("It's seems not a valid index value,please try again!\n");
return INDEX_IS_ERROR;
}bu

// 3. 如果索引为0

if ( dwIndex == 0 )
{
pNewNode->pNext = m_pList;
m_pList = pNewNode;
m_dwLength++;
return SUCCESS;
}

// 4. 如果索引为链表尾

if ( dwIndex == m_dwLength)
{
pPreviousNode = GetIndexPreviousNode(dwIndex); //获取dwIndex前面节点的地址
pPreviousNode->pNext = pNewNode;
m_dwLength++;
return SUCCESS;
}

// 5. 如果索引为链表中
if ( dwIndex > 0 && dwIndex < m_dwLength)
{
pPreviousNode = GetIndexPreviousNode(dwIndex); //获取dwIndex前面节点的地址
pCurrentNode = GetIndexCurrentNode(dwIndex); //获取dwIndex节点的地址
pPreviousNode->pNext = pNewNode;
pNewNode->pNext = pCurrentNode;
m_dwLength++;
return SUCCESS;
}
}

//根据索引删除节点
template<class T_ELE> DWORD LinkedList<T_ELE>::Delete(IN DWORD dwIndex)
{
PNODE pdeltemp = m_pList;
PNODE ptemp = pdeltemp;

// 1. 判断链表是否为空

if ( IsEmpty() )
{
return BUFFER_IS_EMPTY;
}

// 2. 判断索引值是否有效

if ( dwIndex < 0 || dwIndex > m_dwLength )
{
printf("It's seems not a valid index value,please try again!\n");
return INDEX_IS_ERROR;
}

// 3. 如果链表中只有头节点,且要删除头节点

if ( dwIndex == 0 && m_dwLength == 1)
{
delete m_pList;
}

// 4. 如果要删除头节点
// 5. 如果是其他情况

if ( dwIndex >= 0 && dwIndex <= m_dwLength)
{
for (int m = 0; m < dwIndex - 1; m++)
{
ptemp = ptemp->pNext;
}
pdeltemp = ptemp->pNext;
ptemp->pNext = pdeltemp->pNext;
delete pdeltemp;
return SUCCESS;
}
}

//获取链表中节点的数量
template<class T_ELE> DWORD LinkedList<T_ELE>::GetSize()
{
return m_dwLength;
}

void TestLink()
{

LinkedList<int>* p = new LinkedList<int>;

p->Insert(1);
p->Insert(2);
p->Insert(3);
p->Insert(4);
p->Insert(0,10);

int x = 0;
p->GetElement(0,x);
printf("The value is:%d\n", x);
//p->Delete(2);
p->GetElement(2,x);
printf("The value is:%d\n", x);
}


int main(int argc, char* argv[])
{
TestLink();

return 0;
}

实现结果如下:

image-20210615001547403

CATALOG
  1. 1. 链表的特点
  2. 2. 为何会出现链表
  3. 3. 链表的类型
  4. 4. 链表的结构
  5. 5. 在链表中新增节点
    1. 5.1. 创建头节点
    2. 5.2. 从头插入一个新的节点
    3. 5.3. 删除指定节点
    4. 5.4. 修改指定节点
    5. 5.5. 链表反转
  6. 6. 代码实现