数据结构中的单链表
陈莎拉
⚡ 智能摘要
Singly Linked List is a linear, unidirectional data structure where each node stores data and a single pointer to the next node, so traversal moves head-to-tail only and memory is allocated dynamically as new nodes get added.
什么是单链表？
Singly Linked List is a linear and unidirectional data structure where data is saved on the nodes, and each node is connected via a link to its next node. Each node contains a data field and a link to the next node. Singly Linked Lists can be traversed in only one direction, whereas a 双向链表 can be traversed in both directions.
Here is the node structure of a Singly Linked List:
链接列表中节点的结构
Why Use a Linked List Over an Array?
Several scenarios favor a Linked List over an 排列:
- 未知元素的数量： When the required element count is not known at compile time, a Linked List allocates memory dynamically as elements get added.
- 随机访问： When random indexed access is not needed, a Linked List is a suitable choice.
- 中间插入： Inserting in the middle of an array requires shifting elements. A Linked List allows insertion at any position by rewriting only a few pointers.
Opera单链表
A Singly Linked List is good for dynamically allocating memory. It supports the standard operations of the linked list, i.e., insertion, deletion, searching, updating, merging two lists, and traversing.
The following operations are discussed in this article:
- 插入头部
- 插入尾部
- 在节点后插入
- 在节点前插入
- 删除头节点
- 删除尾节点
- 搜索并删除节点
- 遍历链接列表
Here is an example of a linked list with four nodes.
单链表示例
Insertion at the Head of a Singly Linked List
This is a simple operation. It is generally known as pushing onto a Singly Linked List. A new node is created and placed at the head of the list.
To perform this operation, follow two important conditions:
- If the list is empty, the newly created node becomes the head node, and its 下页 pointer is NULL.
- If the list is not empty, the new node becomes the head node, and its 下页 pointer points to the previous head node.
Here is the pseudo-code for inserting a node at the head of a linked list:
function insertAtHead(head, value): newNode = Node(value) if head is NULL: head = newNode return head else: newNode.next = head return newNode
插入头部
Insertion at the End of a Singly Linked List
Inserting a node at the end of a linked list is similar to inserting at the head. Traverse to the tail node, then point its 下页 pointer to the new node. If the head is NULL, the new node becomes the head.
步骤1） Traverse until the 下页 pointer of the current node becomes NULL.
步骤2） 创建具有指定值的新节点。
步骤3） 将新节点指定为尾节点的下一个节点。
The pseudo-code for inserting at the tail of a singly list:
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
插入尾部
Insertion After a Node in a Singly Linked List
Inserting after a node has two parts: search for the target node and attach a new node after it. Traverse the list until a match is found, then splice the new node in.
步骤1） Traverse until the value of the current node equals the search item.
步骤2） Set the new node’s 下页 pointer to the current node’s 下页 指针。
步骤3） Point the current node’s 下页 pointer to the new node.
伪代码：
function insertAfter(head, value, searchItem): newNode = Node(value) while head.value != searchItem: head = head.next newNode.next = head.next head.next = newNode
在单链表中的节点后插入一个节点
Insertion Before a Node in a Singly Linked List
This is similar to insertion after a node. Traverse until the next node matches the search value, then insert the new node before it.
步骤1） 遍历直到下一个节点的值等于搜索项。
步骤2） Create a new node and set its 下页 pointer to the current node’s 下页.
步骤3） Point the current node’s 下页 to the new node.
function insertBefore(head, value, searchItem): newNode = Node(value) while head.next.value != searchItem: head = head.next newNode.next = head.next head.next = newNode
在单链表中的节点前插入一个节点
Delete the Head of the Singly Linked List
The head pointer is provided as the parameter. The head node is removed, and the next node becomes the new head. The memory of the deleted node must be freed to avoid memory leaks.
步骤1） Assign the next node of the head as the new head.
步骤2） Free the allocated memory of the previous head node.
步骤3） 返回新的头节点。
function deleteHead(head): temp = head head = head.next free(temp) return head
删除链接列表的头部
Delete the Tail of the Singly Linked List
Deleting the tail node is similar to deleting the head node. The difference is that traversal to the end of the list is required. In a Singly Linked List, the node whose 下页 pointer is NULL is the tail node.
步骤1） Traverse until just before the tail node. Save the current node.
步骤2） Free the memory of the next node (the tail).
步骤3） Set the next node of the current node to NULL.
function deleteTail(head): while head.next.next is not NULL: head = head.next free(head.next) head.next = NULL
删除单链表的尾部
Search and Delete a Node from a Singly Linked List
This function performs two tasks: search and delete. Traverse until the end of the list. If a matching node is found, remove it and relink the previous node’s 下页 指针。
步骤1） Traverse until the end of the list. Check whether the current node equals the search node.
步骤2） If a match is found, store a pointer to the current node.
步骤3） 此 下页 of the previous node becomes the next node of the current node.
步骤4） Delete the current node and free its memory.
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)
从单链表中搜索并删除节点
Traverse a Singly Linked List
A Singly Linked List only supports traversal from head to tail. There is no pointer to the previous node, so reverse traversal is not possible. Each node is visited in turn, printing its value until NULL is reached.
步骤1） Traverse each node until NULL is reached.
步骤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
单链表的复杂性
There are two kinds of complexity: time complexity and space complexity. The worst and average case time complexity are the same for a Singly Linked List.
Best-case time complexity:
- Insertion at the head can be done in O(1). No traversal inside the list is required.
- Search and delete can be done in O(1) if the target element is at the head node.
Average-case time complexity:
- Insertion inside a linked list takes O(n), where n is the total number of elements.
- Search and delete can take O(n) too, because the target element can reside anywhere up to the tail node.
Space complexity of Singly Linked List
A Singly Linked List dynamically allocates memory. To store n elements, it allocates n memory units. So the space complexity is O(n).
Applications of Singly Linked List
Singly Linked Lists appear in many places where forward-only traversal and dynamic memory are useful:
- Stacks and queues: Underlying storage for LIFO stacks and FIFO queues built from nodes.
- Hash table chaining: Collisions are resolved by chaining entries into a Singly Linked List per bucket.
- Adjacency lists: Sparse graphs use a Singly Linked List of neighbors for each vertex.
- 符号表： Compilers and interpreters chain identifiers into a Singly Linked List per scope.
- Memory allocators: Free-list allocators track free blocks as a Singly Linked List.
