单链表浅析 - 数据结构笔记

链表!!!

Posted by ChungZH on 2018-10-13

这篇文章我们来学习 单链表


单链表概念

链表是使用 链式存储结构 的一种数据结构。链式存储结构 存储密度比顺序存储结构小,是一种物理存储单元上非连续、非顺序的存储结构。相较于 顺序表 ,有 存储的元素个数不受限制插入和删除元素时,不用移动其他元素 等优点。链表有 单链表双向链表 、还有 循环链表 。对于链表中的 数据元素 来说,除了存储其本身的信息之外,还需要存储一个指示其后继(也可以是前继)结点的地址。这两个部分组成一个 结点

单链表实现

首先,我们来定义一个单链表中的结点。先上一个图:

Node

相应的,代码实现如下:

1
2
3
4
struct Node {
int data; // 结点中的数据域
Node * next; // 指针域
};

注意:在单链表中,一个结点中有数据域和指针域,即其本身存储的信息和它的后继的地址

先上一个链表的图:

LinkedList

下面我们开始实现一个单链表,包括删除、插入等基本操作。

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
#include <iostream>
using namespace std;
struct Node {
int data; // 结点中的数据域
Node * next; // 指针域
};
Node * head = new Node; // 头结点

void Init(); // 链表的初始化
void Delete(int index); // 删除链表的第 index 个元素
void Insert(int pos, int data); // 向链表的第 pos 位置插入 data

int main()
{
Node * node = new Node;
node = head;

Init();
for (int i = 1; i <= 10; i++)
{
Insert(i, i); // 向链表插入 1 - 10 这10个数
}
cout << "向链表插入了 1 - 10 这十个数" << endl;

Insert(5, 11); // 向链表的第 5 个位置插入 11

cout << "向链表的第 5 个位置插入了 11 这个数" << endl;
cout << "链表当前情况:" << endl;

while(node->next != NULL)
{
node = node->next;
cout << node->data << " ";
}

cout << endl;

Delete(1); // 删除第 1 个数
Delete(3); // 删除第 3 个数

cout << "删除了第一个数后,又删除了第三个数。" << endl;

node = head;
cout << "链表当前情况:" << endl;

while(node->next != NULL)
{
node = node->next;
cout << node->data << " ";
}


return 0;
}


void Init()
{
head->next = NULL; // 直接把头指针的 next 设为空
head->data = 0; // 这里用头指针的数据域存储链表的长度
}

void Delete(int index)
{
Node * node, * currNode;
node = new Node;
currNode = new Node;
currNode = head;
for (int j = 0; j < index && currNode; j++) // 找到要删除的结点和它的前一个节点
{
node = currNode;
currNode = currNode->next;
}

if (node == NULL || currNode == NULL)
return;

node->next = currNode->next; // 将要删除的前一个节点
delete currNode; // 释放空间
}

void Insert(int pos, int data)
{
Node * node, * insertData;
node = new Node;
node = head;

insertData = new Node;
insertData->data = data;
insertData->next = NULL;

if (pos == 1 && head->data == 0) // 如果插入的位置是第一个位置并且链表为空
{
head->data++;
head->next = insertData;
return;
} else if (pos == 1 && head->data != 0) {
insertData->next = head->next;
head->next = insertData;
return;
}

int j = 1;

while (j < pos && node->next != NULL)
{
node = node->next;
j++;
}

if (node == NULL)
{
return;
}

insertData->next = node->next;
node->next = insertData;

}

输出:

1
2
3
4
5
6
7
向链表插入了 1 - 10 这十个数
向链表的第 5 个位置插入了 11 这个数
链表当前情况:
1 2 3 4 11 5 6 7 8 9 10
删除了第一个数后,又删除了第三个数。
链表当前情况:
2 3 11 5 6 7 8 9 10

大家可以买一本数据结构的书自己看一下,可能比较难理解。

(这篇文章可能是暑假的最后一篇了。)


如果你想学习数据结构和算法,却苦于没有简单易学的教程,那么我给你推荐下面这个课程:

AI前奏必备-数据结构与算法课 - 老九学堂

(此课程中还有Cocos2dx和前端入门课赠送。)


作者:ChungZH