🔥🔥 欢迎来到小林的博客！！
      🛰️博客主页：✈️小林爱敲代码
      🛰️博客专栏：✈️ 数据结构与算法
      🛰️社区 :✈️ 进步学堂
      🛰️欢迎关注：👍点赞🙌收藏✍️留言

前言

今天给大家带来四个内容，一个是单链表非带头的实现，一个是双链表带头循环的实现。剩下的就是数组模拟单链表和双链表。

单链表

链表，在内存中并不是连续存储的。而链表通常会有next指针指向它的下一个节点。链表的最后一个节点一定指向空。

头插

头插我们需要让新节点指向头节点，然后更换头节点为新节点即可。

尾插

我们只需要找到最后一个节点，让它的next指向新节点，再把新节点指向NULL即可。

头删

先保存头节点的下一个节点，然后删除头节点。并把保存下来的下一个节点设置为新的头节点。

尾删

尾删需要记录一下最后一个节点的前一个节点。然后删除最后一个节点，把前一个节点指向NULL。否则会出现指向野指针的情况。

指定位置后插入

我们这里只讲解在指定位置的后一个元素插入，因为单链表在指定节点的前一个插入，需要前一个节点。但是单链表只指后不指前。所以想拿到前一个节点必须再遍历一次，所以不建议单链表用前插。在指定位置后插，我们只需要保存一下这个位置的下一个节点，然后让新节点指向这个位置的下一个节点。这个位置指向新节点。

假设我们在pos位置后面插入：

指定位置后删除

我们还是删除指定位置后的元素，因为如果删除指定元素，我们也需要它的前一个节点。单链表无法直接获取前一个节点。指定位置后删除，我们只需要保存下一个节点的下一个节点，然后删除下一个节点，然后让这个位置指向保存下来的的节点。

单链表的代码实现：

#include<stdlib.h>
#include<assert.h>
#include<stdio.h>

typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;


// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
SListNode* newNode = (SListNode*)malloc(sizeof(SListNode)); //开辟空间
newNode->data = x; //空间值为x
return newNode;
}
// 单链表打印
void SListPrint(SListNode* plist)
{
SListNode* cur = plist;
while (cur) //遍历一遍链表
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
assert(pplist);
if (*pplist == NULL)//如果链表为空调用头插
{
SListPushFront(pplist, x); 
return;
}
    //找到尾部节点
SListNode* tail = *pplist;
while (tail->next)
{
tail = tail->next;
}
    //复用SListInsertAfter函数插入
SListInsertAfter(tail, x);
}
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
assert(pplist);
SListNode* newNode = BuySListNode(x);
if (*pplist == NULL) //链表为空需要更新头节点
{
*pplist = newNode;
newNode->next = NULL;
return;
}
newNode->next = *pplist;
*pplist = newNode;
}
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
assert(pplist && *pplist);
if ((*pplist)->next == NULL) //链表就一个元素，调用头删
{
SListPopFront(pplist);
return;
}
SListNode* tail = *pplist;
SListNode* prev = NULL;

    //遍历链表并删除
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
// 单链表头删
void SListPopFront(SListNode** pplist)
{
assert(pplist && *pplist);
    //头删
SListNode* next = (*pplist)->next;
free(*pplist);
*pplist = next;
}
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
SListNode* cur = plist;
while (cur)
{
if (x == cur->data)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode* next = pos->next;
SListNode* newNode = BuySListNode(x);
pos->next = newNode;
newNode->next = next;
}
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
assert(pos);
SListNode* nextnext = pos->next->next;
free(pos->next);
pos->next = nextnext;
}
// 单链表的销毁
void SListDestroy(SListNode* plist)
{
SListNode* cur = plist;
SListNode* next = plist->next;
while (cur)
{
next = cur->next;
free(cur);
cur = 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
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

双链表

这里我们实现一个带头循环的双链表，因为循环链表可以从头节点直接找到最后一个节点。带头是因为更好的确定链表的尾部，带头节点在这里就冲当了尾节点的作用。

指定位置前插入

双链表我们只需要写指定插入和指定删除，就可以复用这两个接口实现头插，头删，尾插，尾删了。指定位置前插入和单链表类似。先保存前一个节点坐标，然后让前一个节点和新节点连接，再把自己的prev指针指向新节点。

为了方便观看，我把首尾节点指向的线省略了，实际上指针是指向首尾的。我们在pos前插入一个节点。

动图演示可能线连接的不怎么好看，但最后都是这样的

指定位置删除

指定位置删除，我们只需要存下前一个节点和后一个节点。然后把两个节点连接起来，再释放当前节点即可。

双链表代码实现：

#include <assert.h>
#include<stdio.h>

// 带头+双向+循环链表增删查改实现
typedef int LTDataType;

typedef struct _ListNode
{
LTDataType _data;
struct _ListNode* _next; //指向后一个节点
struct _ListNode* _prev; //指向前一个节点
}ListNode;



//创建节点
ListNode* CreateListNode(LTDataType x)
{
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->_data = x;
return newNode;
}

// 创建链表，返回链表的头结点.
ListNode* ListCreate()
{
ListNode* head = CreateListNode(0);
head->_next = head; //自己指向自己
head->_prev = head; //自己指向自己
return head;
}

// 双向链表销毁
void ListDestory(ListNode* pHead)
{
ListNode* cur = pHead->_next;
while (cur != pHead)
{
ListNode* next = cur->_next;
free(cur);
cur = next;
}
free(pHead);
}
// 双向链表打印
void ListPrint(ListNode* pHead)
{
ListNode* cur = pHead->_next;
while(cur != pHead)
{
printf("%d->", cur->_data);
cur = cur->_next;
}
printf("NULL\n");
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
ListInsert(pHead, x); //复用指定插入
}
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
ListErase(pHead->_prev); //复用指定删除
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
ListInsert(pHead->_next, x); //复用指定插入
}
// 双向链表头删
void ListPopFront(ListNode* pHead)
{
ListErase(pHead->_next); //复用指定删除
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
while (pHead)
{
if (pHead->_data == x)
return pHead;
pHead = pHead->_next;
}
return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
ListNode* prev = pos->_prev;
ListNode* newNode = CreateListNode(x);
prev->_next = newNode;
newNode->_prev = prev;
newNode->_next = pos;
pos->_prev = newNode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* prev = pos->_prev;
ListNode* next = pos->_next;
free(pos);
prev->_next = next;
next->_prev = prev;
}
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

数组模拟单链表

数组模拟链表我们需要开一个数组来存链表的值，还要开一个数组连存储链表的指向，还需要一个变量来代表链表的编号。

e[] 数组用来存储链表的值 ， ne[] 数组用来存储节点指向节点的下标，数组的下标代表节点。 head代表头节点，值-1则为空节点。 idx 是给链表的节点的一个编号，代表下标。

代码：

#include<iostream>
using namespace std;

const int N = 100010; //链表总大小
int e[N];//存储值
int ne[N];//存储下一个节点 
int head,idx;  

//链表初始化
void init()
{
    head = -1 ; //-1为空
    idx = 0; //当前节点的编号
}
void add_to_head(int x)  //头插
{
    e[idx] = x; //给新节点赋值
    ne[idx] = head; //指向head指向的节点
    head = idx++; //头节点指向新节点
}

//插入到k节点后面
void add(int k ,int x)
{
    e[idx] = x; //idx编号的元素的值赋值为x
    ne[idx] = ne[k]; //指向k节点的下一个节点
    ne[k] = idx++; //指向新插入节点
}

void remove(int k )
{
    ne[k] = ne[ne[k]]; //指向下一个节点的下一个节点
}

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

数组模拟双链表

单链表需要一个数组来存储指向的节点，那么双链表就需要两个数组来存储，一个指向前节点，一个指向后节点。

r[] 存储节点的后一个节点下标

l[] 存储节点的前一个节点下标

e[] 存储节点的值

hh 头的下标

tt 尾的下标

idx 节点的编号，对应数组下标，每一个新的编号被使用说明创建了一个节点

#include<iostream>
#include<string>
using namespace std;

const int N = 1e6 + 10;
int r[N],l[N],e[N];
int hh,tt,idx;

void init()
{
    hh = 0,tt = 1,idx = 2;//hh代表头，tt代表尾，idx是其他节点的编号
    r[hh] = tt; //头指向尾
    l[tt] = hh; //尾指向头
}

//指定位置的右边插入
void add_right(int k,int x)
{
    e[idx] = x; //idx编号的节点的值为x
    r[idx] = r[k],l[idx] = k; //idx右边指向k的右边，坐标指向k
    l[r[k]] = idx,r[k] = idx++; //k右节点的坐标指向idx，k的右边指向idx。idx编号+1
}
//删除
void remove(int k)
{
    r[l[k]] = r[k]; //k前一个节点的右一个节点指向k的右节点
    l[r[k]] = l[k]; //k后一个节点的左节点指向k的左节点
}
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

总结：

链式实现的链表的动态的，每次增加节点需要开辟空间。开辟空间是有消耗的。而数组模拟的链表是静态的，这就意味着数组模拟的链表比链式实现的链表更快。但因为是静态的，会占用固定的空间。所以个人推荐，做题的时候用静态链表，其他的时候用动态链表。