上查看所有课程
链表是一种线性数据结构，包含一系列连接的节点。在这里，每个节点存储数据和下一个节点的地址。例如，
你必须从某个地方开始，所以我们将第一个节点的地址命名为一个特殊名称，称为HEAD。同样，链表的最后一个节点可以通过其下一个部分指向NULL来识别。
链表可以有多种类型：单向、双向和循环链表。在本文中，我们将重点介绍单向链表。要了解其他类型，请访问链表类型。
注意：你可能玩过寻宝游戏，其中每个线索都包含下一个线索的信息。这就是链表的操作方式。
链表表示
让我们看看链表每个节点是如何表示的。每个节点包含
- 一个数据项
- 另一个节点的地址
我们将数据项和下一个节点引用都封装到一个结构体中，如下所示：
struct node
{
int data;
struct node *next;
};理解链表节点的结构是掌握它的关键。
每个结构体节点都有一个数据项和一个指向另一个结构体节点的指针。让我们创建一个包含三个简单项的链表来理解它是如何工作的。
/* Initialize nodes */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
/* Assign data values */
one->data = 1;
two->data = 2;
three->data=3;
/* Connect nodes */
one->next = two;
two->next = three;
three->next = NULL;
/* Save address of first node in head */
head = one;如果你不理解上面任何一行，你只需要复习一下指针和结构体。
只需几个步骤，我们就创建了一个包含三个节点的简单链表。
链表的力量在于能够断开链条并重新连接它。例如，如果你想将元素 4 插入到 1 和 2 之间，步骤将是：
- 创建一个新的结构体节点并为其分配内存。
- 添加其数据值为 4
- 将其下一个指针指向包含数据值 2 的结构体节点
- 将“1”的下一个指针更改为我们刚刚创建的节点。
在数组中执行类似操作将需要移动所有后续元素的位置。
在 python 和 Java 中，链表可以使用类来实现，如下面的代码所示。
链表实用性
列表是最流行和最高效的数据结构之一，在 C、C++、Python、Java 和 C# 等每种编程语言中都有实现。
除此之外，链表是学习指针工作原理的好方法。通过练习如何操作链表，你可以为学习图和树等更高级的数据结构做好准备。
Python、Java、C 和 C++ 中的链表实现示例
链表可视化：不要只阅读链表，亲眼观看它的工作过程。通过我们新的 DSA 可视化工具，逐步查看数据结构的每一行。 亲自尝试！
# Linked list implementation in Python
class Node:
# Creating a 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()
# Assign item values
linked_list.head = Node(1)
second = Node(2)
third = Node(3)
# Connect nodes
linked_list.head.next = second
second.next = third
# Print the linked list item
while linked_list.head != None:
print(linked_list.head.item, end=" ")
linked_list.head = linked_list.head.next
// Linked list implementation in Java
class LinkedList {
// Creating a node
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();
// Assign value values
linkedList.head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
// Connect nodess
linkedList.head.next = second;
second.next = third;
// printing node-value
while (linkedList.head != null) {
System.out.print(linkedList.head.value + " ");
linkedList.head = linkedList.head.next;
}
}
}// Linked list implementation in C
#include <stdio.h>
#include <stdlib.h>
// Creating a node
struct node {
int value;
struct node *next;
};
// print the linked list value
void printLinkedlist(struct node *p) {
while (p != NULL) {
printf("%d ", p->value);
p = p->next;
}
}
int main() {
// Initialize nodes
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
// Allocate memory
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
// Assign value values
one->value = 1;
two->value = 2;
three->value = 3;
// Connect nodes
one->next = two;
two->next = three;
three->next = NULL;
// printing node-value
head = one;
printLinkedlist(head);
}// Linked list implementation in C++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Creating a node
class Node {
public:
int value;
Node* next;
};
int main() {
Node* head;
Node* one = NULL;
Node* two = NULL;
Node* three = NULL;
// allocate 3 nodes in the heap
one = new Node();
two = new Node();
three = new Node();
// Assign value values
one->value = 1;
two->value = 2;
three->value = 3;
// Connect nodes
one->next = two;
two->next = three;
three->next = NULL;
// print the linked list value
head = one;
while (head != NULL) {
cout << head->value;
head = head->next;
}
}链表复杂度
时间复杂度
| 最坏情况 | 平均情况 | |
|---|---|---|
| 搜索 | O(n) | O(n) |
| 插入 | O(1) | O(1) |
| 删除 | O(1) | O(1) |
空间复杂度：O(n)
链表应用
- 动态内存分配
- 在栈和队列中实现
- 在软件的撤销功能中
- 哈希表、图