链表是一种线性数据结构，包含一系列相互连接的节点。如下，每一个节点包含数据和下一个节点的地址。

你总得从某个地方开始，所以我们给链表中第一个节点的地址起了一个特殊的名字，叫做 “头指针（HEAD）”。此外，链表中的最后一个节点是可以识别出来的，因为它的 “next” 部分指向了空值（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语言指针和结构体的知识。

经过几个步骤，我们已经创建了一个简单的有3个节点的链表

链表的强大之处在于它能够断开链并重新连接起来。例如，如果你想在元素 1 和元素 2 之间插入一个元素 4，步骤将会是：

• 创建一个新的结构体节点，并为其分配内存。
• 将它的数据值设置为 4。
• 将它的 “next” 指针指向那个数据值为 2 的结构体节点。
• 将数据值为“1” 的节点的 “next” 指针指向我们刚刚创建的节点。

在数组中做类似的操作就需要移动所有后续元素的位置。

在 Python 和 Java 中，可以使用类来实现链表，如下方代码所示。

---

链表有什么用

链表是最受欢迎且高效的数据结构之一，在诸如 C、C++、Python、Java 和 C# 等每一种编程语言中都有其实现方式。

除此之外，链表是学习指针如何工作的绝佳途径。通过练习如何操作链表，你可以为学习更高级的数据结构（如图和树）做好准备。

---

Python、Java、C 和 C++ 中链表的实现示例

Python

# 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);
}

C++

// 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)

---

链表的应用

• 动态内存分配
• 在栈和队列中实现
• 在软件的撤销功能中（应用）
• 哈希表，图