# 链表 > 原文： [https://www.programiz.com/dsa/linked-list](https://www.programiz.com/dsa/linked-list) #### 在本教程中，您将学习链表及其应用。 您还将学习如何在链表上创建和执行不同的操作。 在寻宝游戏中，您首先要寻找第一个线索。 当您找到它时，它不再具有宝藏，而是具有下一条线索的位置，依此类推。 您会一直遵循这些线索，直到找到宝藏为止。 链表类似。 它是一系列连接的“节点”，包含下一个节点的“地址”。 每个节点可以存储一个数据点，该数据点可以是数字，字符串或任何其他类型的数据。 * * * ## 链表表示  链表表示 您必须从某个地方开始，所以我们给第一个节点的地址一个特殊的名称，叫做`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; ``` 如果您不懂上述任何几行，则只需要对[指针和结构](/c-programming/c-structures-pointers)进行复习。 仅需几个步骤，我们就创建了一个包含三个节点的简单链表。  具有三个节点的简单链表 链表的功能来自断开链并重新加入链的能力。 例如。 如果您想将元素 4 放在 1 和 2 之间，则步骤为： * 创建一个新的`struct node`并为其分配内存。 * 将其数据值添加为 4 * 将其下一个指针指向包含 2 作为数据值的`struct node` * 将下一个指针更改为我们刚刚创建的节点“1”。 在数组中执行类似的操作将需要移动所有后续元素的位置。 在 python 和 Java 中，可以使用下面的代码所示的类来实现链表。 * * * ## 链表工具 列表是最流行和最有效的数据结构之一，可以在每种编程语言（例如 C，C++ ，Python，Java 和 C# ）中实现。 除此之外，链表是学习指针如何工作的好方法。 通过练习如何操作链表，您可以准备学习更高级的数据结构，例如图形和树。 * * * ## Python，Java 和 C/C++ 示例 ```py # 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 ``` ```java // 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; } } } ``` ```c // 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); } ``` ```cpp // Linked list implementation in C++ #include <bits/stdc++.h> 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) { printf("%d ", head->value); head = head->next; } } ``` * * * ## 链表复杂度 时间复杂度 |   | 最坏情况 | 平均情况 | | --- | --- | --- | | **搜索** | `O(n)` | `O(n)` | | **插入** | `O(1)` | `O(1)` | | **删除** | `O(1)` | `O(1)` | 空间复杂度：`O(n)` * * * ## 链表应用 * 动态内存分配 * 实现栈和队列 * 软件中的撤消功能 * 哈希表，图