链表

原文： 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;

如果您不懂上述任何几行，则只需要对指针和结构进行复习。

仅需几个步骤，我们就创建了一个包含三个节点的简单链表。

具有三个节点的简单链表

链表的功能来自断开链并重新加入链的能力。 例如。 如果您想将元素 4 放在 1 和 2 之间，则步骤为：

• 创建一个新的struct node并为其分配内存。
• 将其数据值添加为 4
• 将其下一个指针指向包含 2 作为数据值的struct node
• 将下一个指针更改为我们刚刚创建的节点“1”。

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

在 python 和 Java 中，可以使用下面的代码所示的类来实现链表。

链表工具

列表是最流行和最有效的数据结构之一，可以在每种编程语言（例如 C，C++ ，Python，Java 和 C# ）中实现。

除此之外，链表是学习指针如何工作的好方法。 通过练习如何操作链表，您可以准备学习更高级的数据结构，例如图形和树。

Python，Java 和 C/C++ 示例

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

链表应用

• 动态内存分配
• 实现栈和队列
• 软件中的撤消功能
• 哈希表，图