数据结构中的单链表

由： 陈莎拉 陈莎拉
Hours 更新

什么是单链表？

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

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

链接列表中节点的结构
链接列表中节点的结构

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

在某些情况下，使用链表比使用 排列. 以下是一些场景：

  • 未知元素的数量： 当您不知道程序运行时需要存储多少个元素时，可以使用链表。当您将元素添加到链表时，内存是动态分配的。
  • 随机访问： 在您不需要使用元素随机访问的场景中，您可以使用链接列表。
  • 中间插入： 在数组中间插入元素是一项复杂的任务。因为您需要将其他元素推到右侧。但是，链接列表允许您将元素添加到您想要的任何位置。

Opera单链表

单链表适合动态分配内存。它提供了链表的所有基本操作，即插入、删除、搜索、更新、合并两个链表、遍历等。

这里我们讨论链表的以下操作：

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

这是一个具有四个节点的链表的示例。

单链表示例
单链表示例

在单链表的头部插入

这是一个简单的操作。一般来说，它被称为推送单链表。您需要创建一个新节点并将其放在链表的头部。

要执行此操作，我们需要遵循两个重要条件。它们是

  1. 如果列表为空，则新创建的节点将作为头节点，头节点的下一个节点将为“NULL”。
  2. 如果列表不为空，则新节点将作为头节点，并且next将指向上一个头节点。

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

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

在单链表末尾插入

在链表尾部插入节点与在链表头插入节点有相似之处。你需要做的就是，遍历到尾节点或尾节点。然后将尾节点的“下一个”节点指向新创建的节点。如果头节点为空，则新节点将为头节点。

步骤如下：

步骤1） 遍历直到当前节点的“下一个”节点为空。

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

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

在单链表尾部插入节点的伪代码：

function insertAtEnd( head, value ):
	newNode = Node(value)
	if head is NULL:
		head = newNode
		return head
	while head.next is not NULL:
		then head = head.next
	head.next = newNode
	newNode.next = NULL
插入尾部
插入尾部

在单链表的节点后插入

在节点后插入有两个部分：搜索节点并附加在搜索到的节点后。我们需要遍历所有节点。对于每个节点，我们需要与搜索元素进行匹配。如果匹配，那么我们将在搜索到的节点后添加新节点。

步骤如下：

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

步骤2） 新节点的下一个指针将是当前节点的下一个指针。

步骤3） 当前节点的下一个节点将成为新节点。

以下是在节点后插入节点的伪代码：

function insertAfter( head, value, searchItem ):
	newNode = Node(value)
	while head.value equals searchItem:
		then head = head.next
	newNode.next = head.next.next
	head.next = newNode
在单链表中的节点后插入一个节点
在单链表中的节点后插入一个节点

相关文章

在单链表的节点前插入

这个函数和在节点后插入很相似。我们必须创建一个新节点并遍历链表，直到当前节点与搜索节点匹配。之后，我们将新节点添加为当前节点的前一个节点。

步骤如下：

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

步骤2） 创建新节点，并将该节点的“next”赋值为当前节点的下一个节点。

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

伪代码如下：

function insertBefore( head, value, searchItem ):
	newNode = Node(value)
	while head.next.value equals searchItem:
		then head = head.next
	newNode.next = head.next.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 is not equals searchItem :
		head = head.next
	head.next = head.next.next
	delete(head.next)
从单链表中搜索并删除节点
从单链表中搜索并删除节点

遍历单链表

单链表只具有从头到尾遍历的功能。没有指向前一个节点的指针；这就是为什么我们不能以相反的顺序遍历单链表。我们将遍历每个节点并打印当前节点的值，直到得到 null。

步骤如下：

步骤1） 遍历每个节点，直到得到 null 作为下一个节点。

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

遍历单链表的伪代码：

function traverse( head ):
		while head.next is not NULL:
			print the value of the head
			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);
  }
  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 = new Node();
  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);
      }else{
        currentNode = currentNode->next;
      }
    }
  }
  cout<<"Deleted Node\t"<<searchItem<<endl;
  return;
}
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 = new 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.')
    return  
  def insertAtEnd(self,value):
    if self.head is None:
      self.insertAtHead(value)
    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):
    temp = Node()
    if self.head is searchItem:
      temp = self.head
      self.head = self.head.next
    else:
      currentNode = self.head
      while currentNode.next is not None:
        if currentNode.next.data is searchItem:
          temp = currentNode.next
          currentNode.next = currentNode.next.next
        else:
          currentNode = currentNode.next
    print(f'Deleted node\t{searchItem}')
    return
  def insertAfter(self,searchItem,value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data is not searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} after node\t{searchItem}')
    return 
  def insertbefore(self,searchItem,value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data is not searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} before node\t{searchItem}')
    return
  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) 内完成搜索和删除操作。

平均情况的时间复杂度：

  • 如果单链表中有“n”个元素，则在链表内插入将需要 O(n)。
  • 搜索和删除也可能需要 O(n)，因为搜索元素可能存在于尾节点中。在这种情况下，您应该遍历整个列表。

单链表的空间复杂度

单链表动态分配内存，如果要存储 n 个元素，则需要分配 n 个内存单元，因此空间复杂度为 O(n)。

你可能会喜欢：