链表数据结构
提示
- 基本概念：链表是一种线性数据结构，由一系列相互连接的节点组成，每个节点包含数据和指向下一个节点的地址。
- 链表类型：链表有多种形式，包括单链表、双链表和循环链表，本文重点介绍单链表。
- 链表的应用：链表广泛应用于动态内存分配、栈和队列实现、软件的撤销功能、哈希表和图等领域。
链表是一种线性数据结构，包含一系列相互连接的节点。在链表中，每个节点都存储着数据和下一个节点的地址。例如，
必须从某个地方开始，所以我们给第一个节点的地址取了一个特殊的名字，叫做 HEAD。此外，可以通过其下一个部分指向 NULL 来识别链表中的最后一个节点。
链表可以有多种类型：单链表、双链表和循环链表。在本文中，我们将重点介绍单链表。要了解其他类型，请访问链表的类型。
**注意：**你可能玩过寻宝游戏，其中每个线索都包含下一个线索的信息。这就是链表的运作方式。
链表的表示
让我们看看链表的每个节点是如何表示的。每个节点包含：
- 一个数据项
- 另一个节点的地址
我们将数据项和下一个节点的引用都封装在一个结构体中，如下所示：
struct node
{
int data;
struct node *next;
};
理解链表节点的结构对于掌握链表非常关键。
每个结构体节点都有一个数据项和指向另一个结构体节点的指针。让我们创建一个包含三个项的简单链表，以了解它是如何工作的。
/* 初始化节点 */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
/* 分配内存 */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
/* 分配数据值 */
one->data = 1;
two->data = 2;
three->data = 3;
/* 连接节点 */
one->next = two;
two->next = three;
three->next = NULL;
/* 将第一个节点的地址保存在head中 */
head = one;
如果你不理解上面的任何一行，你只需要回顾一下指针和结构体。
只需几个步骤，我们就创建了一个包含三个节点的简单链表。
链表的强大之处在于能够断开链条并重新连接。例如，如果你想要在1和2之间插入一个元素4，步骤将是：
- 创建一个新的结构体节点并分配内存。
- 将其数据值设为4
- 将其下一个指针指向包含2作为数据值的结构体节点
- 更改“1”的下一个指针为我们刚刚创建的节点。
在数组中执行类似的操作需要移动所有后续元素的位置。
在Python和Java中，可以使用类来实现链表，如下所示的代码所示。
链表实用性
链表是最流行和高效的数据结构之一，几乎在每种编程语言中都有实现，如C、C++、Python、Java和C#。
除此之外，链表是学习指针工作原理的好方法。通过练习如何操作链表，你可以为学习更高级的数据结构，如图和树，做好准备。
Python、Java、C和C++中的链表实现示例
# Python中的链表实现
class Node:
# 创建一个节点
def __init__(self, item):
self.item = item
self.next = None
class LinkedList:
def __init__(self):
self.head = None
if __name__ == '__main__':
linked_list = LinkedList()
# 分配项的值
linked_list.head = Node(1)
second = Node(2)
third = Node(3)
# 连接节点
linked_list.head.next = second
second.next = third
# 打印链表项
while linked_list.head != None:
print(linked_list.head.item, end=" ")
linked_list.head = linked_list.head.next
// Java中的链表实现
class LinkedList {
// 创建一个节点
Node head;
static class Node {
int value;
Node next;
Node(int d) {
value = d;
next = null;
}
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
// 分配值
linkedList.head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
// 连接节点
linkedList.head.next = second;
second.next = third;
// 打印 节点值
while (linkedList.head != null) {
System.out.print(linkedList.head.value + " ");
linkedList.head = linkedList.head.next;
}
}
}
// C中的链表实现
#include <stdio.h>
#include <stdlib.h>
// 创建一个节点
struct node {
int value;
struct node *next;
};
// 打印链表的值
void printLinkedlist(struct node *p) {
while (p != NULL) {
printf("%d ", p->value);
p = p->next;
}
}
int main() {
// 初始化节点
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
// 分配内存
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
// 分配值
one->value = 1;
two->value = 2;
three->value = 3;
// 连接节点
one->next = two;
two->next = three;
three->next = NULL;
// 打印节点值
head = one;
printLinkedlist(head);
}
// C++中的链表实现
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// 创建一个节点
class Node {
public:
int value;
Node* next;
};
int main() {
Node* head;
Node* one = NULL;
Node* two = NULL;
Node* three = NULL;
// 在堆中分配3个节点
one = new Node();
two = new Node();
three = new Node();
// 分配值
one->value = 1;
two->value = 2;
three->value = 3;
// 连接节点
one->next = two;
two->next = three;
three->next = NULL;
// 打印链表的值
head = one;
while (head != NULL) {
cout << head->value;
head = head->next;
}
}
这些示例演示了在Java、C和C++中创建和操作链表的方法。
链表复杂度
时间复杂度
| 最坏情况 | 平均情况 | |
|---|---|---|
| 搜索 | O(n) | O(n) |
| 插入 | O(1) | O(1) |
| 删除 | O(1) | O(1) |
空间复杂度：O(n)
链表应用
- 动态内存分配
- 在栈和队列中实现
- 在软件的撤销功能中使用
- 哈希表，图