数据结构中的单链表

⚡ 智能摘要

单链表是一种线性、单向的数据结构，其中每个节点存储数据和一个指向下一个节点的指针，因此遍历只能从头到尾进行，并且随着新节点的添加，内存是动态分配的。

🧩 节点结构： 每个节点包含一个数据字段和一个下页指向下一个节点的指针；尾节点的下页指针为空。
📦 列表与数组： 当元素数量未知、不需要随机访问且经常需要在链表中间插入元素时，单链表是首选。
➕ 插入： 使用下一个指针重写，可以将节点添加到头部、尾部、匹配节点之后或匹配节点之前。
➖ 删除： 移除头部、尾部或搜索到的节点会更新邻居指针并释放已释放的内存，以避免内存泄漏。
🔁 遍历： 由于没有指向前一个元素的指针，因此只支持向前遍历，所以无法反向遍历单链表。
💻 C++ 和 Python Code: 完整的实现展示了插入、删除、搜索和遍历例程，并有可运行的输出。
📊 复杂： 头部插入或删除操作的复杂度为 O(1)；搜索和其他插入和删除操作的复杂度为 O(n)；空间复杂度为 O(n)。

什么是单链表？

单链表是一种线性单向数据结构，数据存储在节点上，每个节点通过一条链接连接到下一个节点。每个节点包含一个数据字段和一条指向下一个节点的链接。单链表只能沿一个方向遍历，而双链表则可以沿多个方向遍历。双向链表可以双向通行。

以下是单链表的节点结构：

链接列表中节点的结构

为什么使用链表而不是数组？

在某些情况下，链表比……更合适。排列:

未知元素的数量： 当编译时无法确定所需的元素数量时，链表会在添加元素时动态分配内存。
随机访问： 当不需要随机索引访问时，链表是一个合适的选择。
中间插入： 在数组中间插入元素需要移动元素。而链表只需修改几个指针即可在任意位置插入元素。

Opera单链表

单链表非常适合动态分配内存。它支持链表的标准操作，例如插入、删除、搜索、更新、合并两个链表和遍历。

本文将讨论以下操作：

插入头部
插入尾部
在节点后插入
在节点前插入
删除头节点
删除尾节点
搜索并删除节点
遍历链接列表

这是一个包含四个节点的链表示例。

单链表示例

在单链表头部插入元素

这是一个简单的操作，通常称为向单链表中添加新节点。新节点会被创建一个并放置在链表的头部。

要执行此操作，请遵循以下两个重要条件：

如果列表为空，则新创建的节点成为头节点，并且它的下页指针为空。
如果列表不为空，则新节点成为头节点，并且它的下页指针指向前一个头节点。

以下是向链表头部插入节点的伪代码：

function insertAtHead(head, value):
  newNode = Node(value)
  if head is NULL:
    head = newNode
    return head
  else:
    newNode.next = head
    return newNode

插入头部

在单链表末尾插入元素

在链表末尾插入节点与在头部插入节点类似。遍历到尾节点，然后指向它的尾节点。下页指向新节点的指针。如果 head 为 NULL，则新节点成为 head。

步骤1） 横穿直至下页当前节点的指针变为 NULL。

步骤2） 创建具有指定值的新节点。

步骤3） 将新节点指定为尾节点的下一个节点。

在单列列表末尾插入元素的伪代码：

function insertAtEnd(head, value):
  newNode = Node(value)
  if head is NULL:
    head = newNode
    return head
  while head.next is not NULL:
    head = head.next
  head.next = newNode
  newNode.next = NULL

插入尾部

在单链表中插入节点

在节点后插入节点分为两个步骤：查找目标节点，并将新节点附加到其后。遍历列表直到找到匹配项，然后将新节点插入其中。

步骤1） 遍历直到当前节点的值等于搜索项。

步骤2） 设置新节点的下页指向当前节点的指针下页指针。

步骤3） 指向当前节点的下页指向新节点的指针。

伪代码：

function insertAfter(head, value, searchItem):
  newNode = Node(value)
  while head.value != searchItem:
    head = head.next
  newNode.next = head.next
  head.next = newNode

在单链表中的节点后插入一个节点

在单链表中插入节点

这类似于在现有节点后插入节点。遍历节点直到下一个节点与搜索值匹配，然后将新节点插入到该节点之前。

步骤1） 遍历直到下一个节点的值等于搜索项。

步骤2） 创建一个新节点并设置其下页指向当前节点的指针下页.

步骤3） 指向当前节点的下页到新节点。

function insertBefore(head, value, searchItem):
  newNode = Node(value)
  while head.next.value != searchItem:
    head = head.next
  newNode.next = head.next
  head.next = newNode

在单链表中的节点前插入一个节点

删除单链表的头节点

头部指针作为参数提供。头节点被移除，下一个节点成为新的头节点。必须释放已删除节点的内存以避免内存泄漏。

步骤1） 将下一个节点指定为新的头节点。

步骤2） 释放前一个头节点分配的内存。

步骤3） 返回新的头节点。

function deleteHead(head):
  temp = head
  head = head.next
  free(temp)
  return head

删除链接列表的头部

删除单链表的尾部

删除尾节点与删除头节点类似。区别在于，删除尾节点需要遍历到链表的末尾。在单链表中，其尾节点的删除操作需要遍历到链表的末尾。下页指针为 NULL 时，即为尾节点。

步骤1） 遍历到尾节点之前。保存当前节点。

步骤2） 释放下一个节点（尾节点）的内存。

步骤3） 将当前节点的下一个节点设置为 NULL。

function deleteTail(head):
  while head.next.next is not NULL:
    head = head.next
  free(head.next)
  head.next = NULL

删除单链表的尾部

在单链表中查找并删除节点

此函数执行两个任务：搜索和删除。遍历列表直至末尾。如果找到匹配的节点，则将其删除并重新链接前一个节点。下页指针。

步骤1） 遍历列表直到末尾。检查当前节点是否等于搜索节点。

步骤2） 如果找到匹配项，则存储指向当前节点的指针。

步骤3） 此下页前一个节点成为当前节点的下一个节点。

步骤4） 删除当前节点并释放其内存。

function searchAndDelete(head, searchItem):
  while head.next.next is not NULL and head.next.value != searchItem:
    head = head.next
  temp = head.next
  head.next = head.next.next
  free(temp)

从单链表中搜索并删除节点

遍历单链表

单链表仅支持从头到尾的遍历。由于没有指向前一个节点的指针，因此无法进行反向遍历。链表会依次访问每个节点，并打印其值，直到遇到 NULL 为止。

步骤1） 遍历每个节点，直到遇到 NULL 为止。

步骤2） 打印当前节点的值。

function traverse(head):
  while head is not NULL:
    print head.value
    head = head.next

单链表示例 C++

#include<iostream>
using namespace std;
struct Node{
  int data;
  struct Node *next;
};
void insertAtHead(Node* &head, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  if(head != NULL){
    newNode->next = head;
  }
  head = newNode;
  cout<<"Added "<<newNode->data<<" at the front"<<endl;
}
void insertEnd(Node* &head, int value){
  if(head == NULL){
    insertAtHead(head, value);
    return;
  }
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *temp = head;
  while(temp->next != NULL){
    temp = temp->next;
  }
  temp->next = newNode;
  cout<<"Added "<<newNode->data<<" at the end"<<endl;
}
void searchAndDelete(Node **headPtr, int searchItem){
  Node *temp = NULL;
  if((*headPtr)->data == searchItem){
    temp = *headPtr;
    *headPtr = (*headPtr)->next;
    free(temp);
  } else {
    Node *currentNode = *headPtr;
    while(currentNode->next != NULL){
      if(currentNode->next->data == searchItem){
        temp = currentNode->next;
        currentNode->next = currentNode->next->next;
        free(temp);
        break;
      } else {
        currentNode = currentNode->next;
      }
    }
  }
  cout<<"Deleted Node\t"<<searchItem<<endl;
}
void insertAfter(Node* &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next != NULL && head->data != searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" after node\t"<<searchItem<<endl;
}
void insertBefore(Node* &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next != NULL && head->next->data != searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" before node\t"<<searchItem<<endl;
}
void traverse(Node *headPointer){
  Node* tempNode = headPointer;
  cout<<"Traversal from head:\t";
  while(tempNode != NULL){
    cout<<tempNode->data;
    if(tempNode->next)
      cout<<" --> ";
    tempNode = tempNode->next;
  }
  cout<<endl;
}
int main(){
  Node *head = NULL;
  insertAtHead(head, 5);
  insertAtHead(head, 6);
  insertAtHead(head, 7);
  insertEnd(head, 9);
  traverse(head);
  searchAndDelete(&head, 6);
  traverse(head);
  insertAfter(head, 7, 10);
  insertBefore(head, 9, 11);
  traverse(head);
}

输出

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Traversal from head:    7 --> 6 --> 5 --> 9
Deleted Node    6
Traversal from head:    7 --> 5 --> 9
Inserted 10 after node  7
Inserted 11 before node 9
Traversal from head:    7 --> 10 --> 5 --> 11 --> 9

单链表示例 Python

class Node:
  def __init__(self, data=None, next=None):
    self.data = data
    self.next = next
class SinglyLinkedList:
  def __init__(self):
    self.head = None
  def insertAtHead(self, value):
    newNode = Node(data=value)
    if self.head is not None:
      newNode.next = self.head
    self.head = newNode
    print(f'Added {newNode.data} at the front.')
  def insertAtEnd(self, value):
    if self.head is None:
      self.insertAtHead(value)
      return
    newNode = Node(value)
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    print(f'Added {newNode.data} at the end.')
  def searchAndDelete(self, searchItem):
    if self.head is None:
      return
    if self.head.data == searchItem:
      self.head = self.head.next
      print(f'Deleted node\t{searchItem}')
      return
    currentNode = self.head
    while currentNode.next is not None:
      if currentNode.next.data == searchItem:
        currentNode.next = currentNode.next.next
        print(f'Deleted node\t{searchItem}')
        return
      currentNode = currentNode.next
  def insertAfter(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} after node\t{searchItem}')
  def insertBefore(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} before node\t{searchItem}')
  def traverse(self):
    temp = self.head
    print("Traversing from head:\t", end="")
    while temp:
      print("{}\t".format(temp.data), end="")
      temp = temp.next
    print()
singlyLinkedList = SinglyLinkedList()
singlyLinkedList.insertAtHead(5)
singlyLinkedList.insertAtHead(6)
singlyLinkedList.insertAtHead(7)
singlyLinkedList.insertAtEnd(9)
singlyLinkedList.traverse()
singlyLinkedList.searchAndDelete(6)
singlyLinkedList.traverse()
singlyLinkedList.insertAfter(7, 10)
singlyLinkedList.insertBefore(9, 11)
singlyLinkedList.traverse()

输出

Added 5 at the front.
Added 6 at the front.
Added 7 at the front.
Added 9 at the end.
Traversing from head:   7       6       5       9
Deleted node    6
Traversing from head:   7       5       9
Inserted 10 after node  7
Inserted 11 before node 9
Traversing from head:   7       10      5       11      9

单链表的复杂性

复杂度分为两种：时间复杂度和空间复杂度。对于单链表，最坏情况的时间复杂度和平均时间复杂度相同。

最佳情况时间复杂度：

在链表头部插入元素的时间复杂度为 O(1)。无需遍历链表内部。
如果目标元素位于头节点，则搜索和删除可以在 O(1) 时间内完成。

平均情况时间复杂度：

在链表中插入元素的时间复杂度为 O(n)，其中 n 是元素的总数。
搜索和删除操作的时间复杂度也可能为 O(n)，因为目标元素可以位于尾节点之前的任何位置。

单链表的空间复杂度

单链表动态分配内存。用于存储 n 它分配元素 n 存储单元。因此，空间复杂度为 O(n)。

单链表的应用

单链表在许多需要向前遍历和动态内存的地方都会用到：

栈和队列： 由节点构建的 LIFO 栈和 FIFO 队列的底层存储。
哈希表链式法： 通过将条目链接到每个桶的单链表中来解决冲突。
邻接表： 稀疏图使用单链表来表示每个顶点的邻居。
符号表： 编译器和解释器会将标识符按作用域链接成一个单链表。
内存分配器： 自由列表分配器 trac将 k 个空闲块表示为单链表。

常见问题

单链表将 AI 框架内的训练样本、小批量数据和空闲内存块链接起来，从而实现流式输入的动态队列和可随模型需求扩展的无锁数据管道。

是的。GitHub Copilot 和 GPT 可以用 C 语言生成完整的单链表。 C++, Java, Python 或 Java脚本，包括插入、删除、撤销、循环检测和单元测试。

单链表只有一个指向下一个节点的指针，只能向前遍历。双向链表既有指向下一个节点的指针，也有指向上一个节点的指针，可以双向遍历，但每个节点占用的内存更多。

常见用途包括栈和队列实现、哈希表链接、稀疏图的邻接表、编译器中的符号表、空闲列表分配器以及轻量级编辑器中的撤销历史记录。

在头部进行插入或删除操作的时间复杂度为 O(1)。在尾部进行插入、搜索、在特定位置插入以及删除特定节点的时间复杂度均为 O(n)，因为需要从头部开始遍历。

链表在运行时会动态增长和收缩，一旦位置已知，插入或删除操作的时间复杂度为 O(1)，并且永远不需要连续的内存空间。数组提供 O(1) 的随机访问时间和更好的缓存局部性。

使用三个指针 prev、curr 和 next 遍历列表。每一步，保存 curr.next，将 curr.next 指向 prev，并将 prev 和 curr 向前移动。返回 prev 作为新的头元素。

弗洛伊德龟兔赛跑算法使用两个速度不同的指针。如果它们相遇，则链表中包含一个环。否则，速度较快的指针会指向 NULL，链表中不存在环。

数据结构中的单链表

什么是单链表？

为什么使用链表而不是数组？

Opera单链表

在单链表头部插入元素

在单链表末尾插入元素

在单链表中插入节点

在单链表中插入节点

删除单链表的头节点

删除单链表的尾部

在单链表中查找并删除节点

遍历单链表

单链表示例 C++

输出

单链表示例 Python

输出

单链表的复杂性

单链表的应用

常见问题

总结一下这篇文章：

注册简报

什么是单链表？

为什么使用链表而不是数组？

Opera单链表

在单链表头部插入元素

在单链表末尾插入元素

在单链表中插入节点

在单链表中插入节点

相关文章

删除单链表的头节点

删除单链表的尾部

在单链表中查找并删除节点

遍历单链表

单链表示例 C++

输出

单链表示例 Python

输出

单链表的复杂性

单链表的应用

常见问题

总结一下这篇文章：

注册简报