线性表——单链表单链表

109 阅读 0 评论 72 点赞

我是靠谱客的博主故意保温杯，这篇文章主要介绍线性表——单链表单链表，现在分享给大家，希望可以做个参考。

单链表

不同于顺序表，可以把单链表形象的比喻成生活中的火车。每节车厢的连接需要靠连接钩进行串接。并且它的访问方式不是随机访问，而是顺序访问，好比在火车上，你必须一个个车厢穿梭才能到达你要去的车厢。

1. 结构定义

复制代码

1
2
3
4
5
typedef struct Node {
int data;
typedef struct *next;
} Node, *LinkedList;

2. 初始化

复制代码

1
2
LinkedList linkedlist = NULL:

3. 插入

插入的时候我们以实际的位序进行插入（默认从零开始）

复制代码

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
LinkedList insert(LinkedList head, Node
*node, int index) {
if (head == NULL) {
if (index != 0) return head;
head = node;
return head;
}
if (index == 0) {
node->next = head;
head = node;
return head;
}
Node *current_node = head;
int count = 0;
while (current_node->next != NULL && count < index - 1) {
current_node = current_node->next;
count++;
}
if (count == index - 1) {
node->next = current_node->next;
current_node->next = node;
return head;
}
return head;
}

注意

当链表为空时，且插入的位序如果不为0，则插入是无效的（OutBound）。
当链表不是空的且插入位置不为0时，我们就需要通过遍历来找寻插入位置的前一个节点。

4. 遍历

我们需要声明一个节点，来提供在链表中的移动。

复制代码

1
2
3
4
5
6
7
8
9
void print(LinkedList head) {
if (head == NULL) return;
Node *current_node = head;
while (current_node != NULL) {
if (current_node->next == NULL) printf("%dn", current_node->data);
printf("%d ", current_node->data);
}
}

5. 销毁（置空)

依次遍历释放每一个节点

复制代码

1
2
3
4
5
6
7
8
9
10
void destroy(LinkedList head) {
if (head == NULL) return;
Node *current_node = head;
while (current_node != NULL) {
Node *delete_node = current_node;
current_node = current_node->next;
free(delete_node);
}
}

6. 删除

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
LinkedList delete(LinkedList head, int index) {
if (head == NULL) return head;
Node *current_node = head;
int count = 0;
while (current_node->next != NULL && count < index - 1) {
current_node = current_node->next;
count++;
}
if (count == index - 1 && current_node->next != NULL) {
Node *delete_node = current_node->next;
current_node->next = delete_node->next;
free(delete_node);
}
return head;
}

7. 逆置

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
LinkedList reverse(LinkedList head) {
if (head == NULL && head->next == NULL) return head;
Node *current_node = head->next;
Node *next_node;
head->next = NULL;
while (current_node != NULL) {
next_node = current_node->next;
current_node->next = head;
head = current_node;
current_node = next_node;
}
return head;
}