单向链表

算法

单向链表是一种线性数据结构,其中每个节点包含数据和指向下一个节点的指针。适用于频繁插入和删除操作的场景。

空间复杂度:O(n)

算法讲解

单向链表

介绍

单向链表是一种线性数据结构,它由一系列节点组成,每个节点包含两部分:数据域和指针域。数据域用于存储实际数据,指针域存储指向下一个节点的引用。链表中的最后一个节点指向空(null),表示链表的结束。

与数组不同,链表中的元素在内存中不是连续存储的,而是通过指针连接在一起。这种特性让链表在某些操作上比数组更灵活,特别是在频繁进行插入和删除操作的场景下。

核心特性

  1. 动态大小:链表可以动态增长和缩小,无需预先定义大小
  2. 非连续存储:节点在内存中分散存储,通过指针相连
  3. 单向性:每个节点只知道下一个节点在哪里,不知道上一个节点
  4. 顺序访问:必须从头节点开始,沿着指针逐个访问节点
  5. 无索引访问:不能像数组那样通过索引直接访问元素

基本操作

1. 访问元素

  • 时间复杂度:O(n)
  • 说明:必须从头节点开始,沿链表遍历直到找到目标节点

2. 在头部插入

  • 时间复杂度:O(1)
  • 说明:创建新节点并指向当前头节点,然后更新头节点

3. 在尾部插入

  • 时间复杂度:O(n)或O(1)
    • O(n):如果只有头指针,需要遍历到尾部
    • O(1):如果维护了尾指针,可以直接在尾部操作

4. 在中间插入

  • 时间复杂度:O(n)
  • 说明:先找到目标位置的前一个节点,再执行插入操作

5. 删除节点

  • 时间复杂度:
    • 删除头节点:O(1)
    • 删除其他节点:O(n),因为需要找到待删除节点的前一个节点

6. 查找元素

  • 时间复杂度:O(n)
  • 说明:从头节点开始遍历链表查找目标元素

基础实现

代码实现

Java

▼
Java
复制代码
// 定义节点类 class Node { int data; // 数据域 Node next; // 指针域,指向下一个节点 // 构造函数 public Node(int data) { this.data = data; this.next = null; } } // 单向链表类 class SinglyLinkedList { private Node head; // 头节点 // 构造函数,创建一个空链表 public SinglyLinkedList() { this.head = null; } // 判断链表是否为空 public boolean isEmpty() { return head == null; } // 在链表头部插入节点 public void insertAtHead(int data) { Node newNode = new Node(data); if (isEmpty()) { head = newNode; } else { newNode.next = head; head = newNode; } } // 在链表尾部插入节点 public void insertAtTail(int data) { Node newNode = new Node(data); if (isEmpty()) { head = newNode; return; } Node current = head; // 找到最后一个节点 while (current.next != null) { current = current.next; } current.next = newNode; } // 在指定位置插入节点 public void insertAtPosition(int data, int position) { // 位置无效 if (position < 0) { System.out.println("位置无效"); return; } // 插入位置为0,相当于在头部插入 if (position == 0) { insertAtHead(data); return; } Node newNode = new Node(data); Node current = head; Node previous = null; int count = 0; // 找到要插入位置的前一个节点 while (current != null && count < position) { previous = current; current = current.next; count++; } // 如果position超出链表长度,则插入到尾部 previous.next = newNode; newNode.next = current; } // 删除第一个值为data的节点 public void delete(int data) { // 链表为空 if (isEmpty()) { System.out.println("链表为空,无法删除"); return; } // 删除的是头节点 if (head.data == data) { head = head.next; return; } // 删除的不是头节点 Node current = head; Node previous = null; // 查找要删除的节点 while (current != null && current.data != data) { previous = current; current = current.next; } // 如果找到了要删除的节点 if (current != null) { previous.next = current.next; } else { System.out.println("未找到要删除的元素"); } } // 查找节点 public boolean search(int data) { if (isEmpty()) { return false; } Node current = head; while (current != null) { if (current.data == data) { return true; } current = current.next; } return false; } // 打印链表 public void display() { if (isEmpty()) { System.out.println("链表为空"); return; } Node current = head; while (current != null) { System.out.print(current.data + " -> "); current = current.next; } System.out.println("null"); } // 获取链表长度 public int size() { int count = 0; Node current = head; while (current != null) { count++; current = current.next; } return count; } } // 使用示例 public class LinkedListDemo { public static void main(String[] args) { SinglyLinkedList list = new SinglyLinkedList(); list.insertAtTail(10); list.insertAtTail(20); list.insertAtTail(30); list.insertAtHead(5); list.display(); // 输出: 5 -> 10 -> 20 -> 30 -> null list.insertAtPosition(15, 2); list.display(); // 输出: 5 -> 10 -> 15 -> 20 -> 30 -> null list.delete(15); list.display(); // 输出: 5 -> 10 -> 20 -> 30 -> null System.out.println("查找结果: " + list.search(20)); // 输出: 查找结果: true System.out.println("链表长度: " + list.size()); // 输出: 链表长度: 4 } }

JavaScript

▼
Javascript
复制代码
// 定义节点类 class Node { constructor(data) { this.data = data; this.next = null; } } // 单向链表类 class SinglyLinkedList { constructor() { this.head = null; } // 判断链表是否为空 isEmpty() { return this.head === null; } // 在链表头部插入节点 insertAtHead(data) { const newNode = new Node(data); if (this.isEmpty()) { this.head = newNode; } else { newNode.next = this.head; this.head = newNode; } } // 在链表尾部插入节点 insertAtTail(data) { const newNode = new Node(data); if (this.isEmpty()) { this.head = newNode; return; } let current = this.head; while (current.next !== null) { current = current.next; } current.next = newNode; } // 在指定位置插入节点 insertAtPosition(data, position) { if (position < 0) { console.log("位置无效"); return; } if (position === 0) { this.insertAtHead(data); return; } const newNode = new Node(data); let current = this.head; let previous = null; let count = 0; while (current !== null && count < position) { previous = current; current = current.next; count++; } previous.next = newNode; newNode.next = current; } // 删除第一个值为data的节点 delete(data) { if (this.isEmpty()) { console.log("链表为空,无法删除"); return; } if (this.head.data === data) { this.head = this.head.next; return; } let current = this.head; let previous = null; while (current !== null && current.data !== data) { previous = current; current = current.next; } if (current !== null) { previous.next = current.next; } else { console.log("未找到要删除的元素"); } } // 查找节点 search(data) { if (this.isEmpty()) { return false; } let current = this.head; while (current !== null) { if (current.data === data) { return true; } current = current.next; } return false; } // 打印链表 display() { if (this.isEmpty()) { console.log("链表为空"); return; } let result = ""; let current = this.head; while (current !== null) { result += current.data + " -> "; current = current.next; } result += "null"; console.log(result); } // 获取链表长度 size() { let count = 0; let current = this.head; while (current !== null) { count++; current = current.next; } return count; } } // 使用示例 const list = new SinglyLinkedList(); list.insertAtTail(10); list.insertAtTail(20); list.insertAtTail(30); list.insertAtHead(5); list.display(); // 输出: 5 -> 10 -> 20 -> 30 -> null list.insertAtPosition(15, 2); list.display(); // 输出: 5 -> 10 -> 15 -> 20 -> 30 -> null list.delete(15); list.display(); // 输出: 5 -> 10 -> 20 -> 30 -> null console.log("查找结果:", list.search(20)); // 输出: 查找结果: true console.log("链表长度:", list.size()); // 输出: 链表长度: 4

Python

▼
Python
复制代码
class Node: def __init__(self, data): self.data = data self.next = None class SinglyLinkedList: def __init__(self): self.head = None def is_empty(self): return self.head is None def insert_at_head(self, data): new_node = Node(data) if self.is_empty(): self.head = new_node else: new_node.next = self.head self.head = new_node def insert_at_tail(self, data): new_node = Node(data) if self.is_empty(): self.head = new_node return current = self.head while current.next is not None: current = current.next current.next = new_node def insert_at_position(self, data, position): if position < 0: print("位置无效") return if position == 0: self.insert_at_head(data) return new_node = Node(data) current = self.head previous = None count = 0 while current is not None and count < position: previous = current current = current.next count += 1 previous.next = new_node new_node.next = current def delete(self, data): if self.is_empty(): print("链表为空,无法删除") return if self.head.data == data: self.head = self.head.next return current = self.head previous = None while current is not None and current.data != data: previous = current current = current.next if current is not None: previous.next = current.next else: print("未找到要删除的元素") def search(self, data): if self.is_empty(): return False current = self.head while current is not None: if current.data == data: return True current = current.next return False def display(self): if self.is_empty(): print("链表为空") return result = "" current = self.head while current is not None: result += str(current.data) + " -> " current = current.next result += "None" print(result) def size(self): count = 0 current = self.head while current is not None: count += 1 current = current.next return count # 使用示例 if __name__ == "__main__": linked_list = SinglyLinkedList() linked_list.insert_at_tail(10) linked_list.insert_at_tail(20) linked_list.insert_at_tail(30) linked_list.insert_at_head(5) linked_list.display() # 输出: 5 -> 10 -> 20 -> 30 -> None linked_list.insert_at_position(15, 2) linked_list.display() # 输出: 5 -> 10 -> 15 -> 20 -> 30 -> None linked_list.delete(15) linked_list.display() # 输出: 5 -> 10 -> 20 -> 30 -> None print(f"查找结果: {linked_list.search(20)}") # 输出: 查找结果: True print(f"链表长度: {linked_list.size()}") # 输出: 链表长度: 4

Go

▼
Go
复制代码
package main import "fmt" // 定义节点结构体 type Node struct { data int next *Node } // 单向链表结构体 type SinglyLinkedList struct { head *Node } // 创建新链表 func NewSinglyLinkedList() *SinglyLinkedList { return &SinglyLinkedList{nil} } // 判断链表是否为空 func (list *SinglyLinkedList) IsEmpty() bool { return list.head == nil } // 在链表头部插入节点 func (list *SinglyLinkedList) InsertAtHead(data int) { newNode := &Node{data: data, next: nil} if list.IsEmpty() { list.head = newNode } else { newNode.next = list.head list.head = newNode } } // 在链表尾部插入节点 func (list *SinglyLinkedList) InsertAtTail(data int) { newNode := &Node{data: data, next: nil} if list.IsEmpty() { list.head = newNode return } current := list.head for current.next != nil { current = current.next } current.next = newNode } // 在指定位置插入节点 func (list *SinglyLinkedList) InsertAtPosition(data int, position int) { if position < 0 { fmt.Println("位置无效") return } if position == 0 { list.InsertAtHead(data) return } newNode := &Node{data: data, next: nil} current := list.head var previous *Node count := 0 for current != nil && count < position { previous = current current = current.next count++ } previous.next = newNode newNode.next = current } // 删除第一个值为data的节点 func (list *SinglyLinkedList) Delete(data int) { if list.IsEmpty() { fmt.Println("链表为空,无法删除") return } if list.head.data == data { list.head = list.head.next return } current := list.head var previous *Node for current != nil && current.data != data { previous = current current = current.next } if current != nil { previous.next = current.next } else { fmt.Println("未找到要删除的元素") } } // 查找节点 func (list *SinglyLinkedList) Search(data int) bool { if list.IsEmpty() { return false } current := list.head for current != nil { if current.data == data { return true } current = current.next } return false } // 打印链表 func (list *SinglyLinkedList) Display() { if list.IsEmpty() { fmt.Println("链表为空") return } current := list.head for current != nil { fmt.Printf("%d -> ", current.data) current = current.next } fmt.Println("nil") } // 获取链表长度 func (list *SinglyLinkedList) Size() int { count := 0 current := list.head for current != nil { count++ current = current.next } return count } func main() { list := NewSinglyLinkedList() list.InsertAtTail(10) list.InsertAtTail(20) list.InsertAtTail(30) list.InsertAtHead(5) list.Display() // 输出: 5 -> 10 -> 20 -> 30 -> nil list.InsertAtPosition(15, 2) list.Display() // 输出: 5 -> 10 -> 15 -> 20 -> 30 -> nil list.Delete(15) list.Display() // 输出: 5 -> 10 -> 20 -> 30 -> nil fmt.Printf("查找结果: %t\n", list.Search(20)) // 输出: 查找结果: true fmt.Printf("链表长度: %d\n", list.Size()) // 输出: 链表长度: 4 }

C

▼
C
复制代码
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> // 定义节点结构 typedef struct Node { int data; struct Node* next; } Node; // 定义链表结构 typedef struct { Node* head; } SinglyLinkedList; // 创建新链表 SinglyLinkedList* createList() { SinglyLinkedList* list = (SinglyLinkedList*)malloc(sizeof(SinglyLinkedList)); if (list == NULL) { printf("内存分配失败\n"); exit(1); } list->head = NULL; return list; } // 判断链表是否为空 bool isEmpty(SinglyLinkedList* list) { return list->head == NULL; } // 创建新节点 Node* createNode(int data) { Node* newNode = (Node*)malloc(sizeof(Node)); if (newNode == NULL) { printf("内存分配失败\n"); exit(1); } newNode->data = data; newNode->next = NULL; return newNode; } // 在链表头部插入节点 void insertAtHead(SinglyLinkedList* list, int data) { Node* newNode = createNode(data); if (isEmpty(list)) { list->head = newNode; } else { newNode->next = list->head; list->head = newNode; } } // 在链表尾部插入节点 void insertAtTail(SinglyLinkedList* list, int data) { Node* newNode = createNode(data); if (isEmpty(list)) { list->head = newNode; return; } Node* current = list->head; while (current->next != NULL) { current = current->next; } current->next = newNode; } // 在指定位置插入节点 void insertAtPosition(SinglyLinkedList* list, int data, int position) { if (position < 0) { printf("位置无效\n"); return; } if (position == 0) { insertAtHead(list, data); return; } Node* newNode = createNode(data); Node* current = list->head; Node* previous = NULL; int count = 0; while (current != NULL && count < position) { previous = current; current = current->next; count++; } previous->next = newNode; newNode->next = current; } // 删除第一个值为data的节点 void deleteNode(SinglyLinkedList* list, int data) { if (isEmpty(list)) { printf("链表为空,无法删除\n"); return; } if (list->head->data == data) { Node* temp = list->head; list->head = list->head->next; free(temp); return; } Node* current = list->head; Node* previous = NULL; while (current != NULL && current->data != data) { previous = current; current = current->next; } if (current != NULL) { previous->next = current->next; free(current); } else { printf("未找到要删除的元素\n"); } } // 查找节点 bool search(SinglyLinkedList* list, int data) { if (isEmpty(list)) { return false; } Node* current = list->head; while (current != NULL) { if (current->data == data) { return true; } current = current->next; } return false; } // 打印链表 void display(SinglyLinkedList* list) { if (isEmpty(list)) { printf("链表为空\n"); return; } Node* current = list->head; while (current != NULL) { printf("%d -> ", current->data); current = current->next; } printf("NULL\n"); } // 获取链表长度 int size(SinglyLinkedList* list) { int count = 0; Node* current = list->head; while (current != NULL) { count++; current = current->next; } return count; } // 释放链表内存 void freeList(SinglyLinkedList* list) { Node* current = list->head; Node* next; while (current != NULL) { next = current->next; free(current); current = next; } free(list); } // 使用示例 int main() { SinglyLinkedList* list = createList(); insertAtTail(list, 10); insertAtTail(list, 20); insertAtTail(list, 30); insertAtHead(list, 5); display(list); // 输出: 5 -> 10 -> 20 -> 30 -> NULL insertAtPosition(list, 15, 2); display(list); // 输出: 5 -> 10 -> 15 -> 20 -> 30 -> NULL deleteNode(list, 15); display(list); // 输出: 5 -> 10 -> 20 -> 30 -> NULL printf("查找结果: %s\n", search(list, 20) ? "true" : "false"); // 输出: 查找结果: true printf("链表长度: %d\n", size(list)); // 输出: 链表长度: 4 freeList(list); return 0; }

C++

▼
C++
复制代码
#include <iostream> // 定义节点类 class Node { public: int data; Node* next; // 构造函数 Node(int data) { this->data = data; this->next = nullptr; } }; // 单向链表类 class SinglyLinkedList { private: Node* head; public: // 构造函数 SinglyLinkedList() { head = nullptr; } // 析构函数 ~SinglyLinkedList() { Node* current = head; Node* next = nullptr; while (current != nullptr) { next = current->next; delete current; current = next; } } // 判断链表是否为空 bool isEmpty() { return head == nullptr; } // 在链表头部插入节点 void insertAtHead(int data) { Node* newNode = new Node(data); if (isEmpty()) { head = newNode; } else { newNode->next = head; head = newNode; } } // 在链表尾部插入节点 void insertAtTail(int data) { Node* newNode = new Node(data); if (isEmpty()) { head = newNode; return; } Node* current = head; while (current->next != nullptr) { current = current->next; } current->next = newNode; } // 在指定位置插入节点 void insertAtPosition(int data, int position) { if (position < 0) { std::cout << "位置无效" << std::endl; return; } if (position == 0) { insertAtHead(data); return; } Node* newNode = new Node(data); Node* current = head; Node* previous = nullptr; int count = 0; while (current != nullptr && count < position) { previous = current; current = current->next; count++; } previous->next = newNode; newNode->next = current; } // 删除第一个值为data的节点 void deleteNode(int data) { if (isEmpty()) { std::cout << "链表为空,无法删除" << std::endl; return; } if (head->data == data) { Node* temp = head; head = head->next; delete temp; return; } Node* current = head; Node* previous = nullptr; while (current != nullptr && current->data != data) { previous = current; current = current->next; } if (current != nullptr) { previous->next = current->next; delete current; } else { std::cout << "未找到要删除的元素" << std::endl; } } // 查找节点 bool search(int data) { if (isEmpty()) { return false; } Node* current = head; while (current != nullptr) { if (current->data == data) { return true; } current = current->next; } return false; } // 打印链表 void display() { if (isEmpty()) { std::cout << "链表为空" << std::endl; return; } Node* current = head; while (current != nullptr) { std::cout << current->data << " -> "; current = current->next; } std::cout << "nullptr" << std::endl; } // 获取链表长度 int size() { int count = 0; Node* current = head; while (current != nullptr) { count++; current = current->next; } return count; } }; // 使用示例 int main() { SinglyLinkedList list; list.insertAtTail(10); list.insertAtTail(20); list.insertAtTail(30); list.insertAtHead(5); list.display(); // 输出: 5 -> 10 -> 20 -> 30 -> nullptr list.insertAtPosition(15, 2); list.display(); // 输出: 5 -> 10 -> 15 -> 20 -> 30 -> nullptr list.deleteNode(15); list.display(); // 输出: 5 -> 10 -> 20 -> 30 -> nullptr std::cout << "查找结果: " << (list.search(20) ? "true" : "false") << std::endl; // 输出: 查找结果: true std::cout << "链表长度: " << list.size() << std::endl; // 输出: 链表长度: 4 return 0; }

优缺点

优点

  1. 动态大小:链表可以根据需要动态分配内存,不需要预先定义大小
  2. 插入和删除高效:在已知位置插入或删除节点的时间复杂度为O(1)
  3. 内存利用灵活:不需要连续的内存空间,可以充分利用可用内存
  4. 实现简单:基本操作实现相对简单直观

缺点

  1. 随机访问低效:无法像数组那样通过索引直接访问元素,必须从头开始遍历
  2. 额外内存开销:每个节点除了存储数据外,还需要存储指针,增加了内存消耗
  3. 缓存不友好:由于内存不连续,不能有效利用CPU缓存,可能导致性能下降
  4. 反向遍历困难:单向链表不支持反向遍历

应用场景

  1. 历史记录
  2. 撤销功能:编辑器的撤销操作实现
  3. 合适的插入/删除场景:需要频繁在数据结构中间插入或删除元素的场景
  4. 作为其他数据结构的基础

扩展:双向链表和循环链表

单向链表的一个主要缺点是只能从头到尾遍历。为了克服这个限制,有两种常见的链表变种:

双向链表

双向链表中的每个节点有两个指针:一个指向下一个节点,一个指向前一个节点。这使得链表可以双向遍历。

▼
Java
复制代码
class DoublyNode { int data; DoublyNode next; DoublyNode prev; public DoublyNode(int data) { this.data = data; this.next = null; this.prev = null; } }

循环链表

循环链表是一种特殊的链表,其最后一个节点的指针不是null,而是指向头节点,形成一个环。循环链表可以是单向的或双向的。

测验

1)如果要在单向链表中找到倒数第k个节点,最简单的方法是什么?需要几次遍历?

2)如何判断一个单向链表中是否包含环(循环)?

3)编写一个算法反转单向链表。

4)如果有两个单链表,如何找到它们的交点(如果存在)?

测验答案

1)找到倒数第k个节点的方法:

  • 先遍历一次链表,获取链表长度n
  • 再遍历一次,找到第(n-k+1)个节点
  • 需要两次遍历

另一种优化方法是使用快慢指针:

▼
Java
复制代码
public Node findKthFromEnd(int k) { if (head == null || k <= 0) { return null; } Node fast = head; Node slow = head; // 快指针先走k步 for (int i = 0; i < k; i++) { if (fast == null) return null; // k大于链表长度 fast = fast.next; } // 快慢指针同时走,当快指针到达末尾时,慢指针指向倒数第k个节点 while (fast != null) { slow = slow.next; fast = fast.next; } return slow; }

2)判断链表是否包含环,可以使用快慢指针(Floyd's Cycle-Finding Algorithm):

▼
Java
复制代码
public boolean hasCycle() { if (head == null || head.next == null) { return false; } Node slow = head; Node fast = head; while (fast != null && fast.next != null) { slow = slow.next; // 慢指针每次走一步 fast = fast.next.next; // 快指针每次走两步 // 如果存在环,快慢指针最终会相遇 if (slow == fast) { return true; } } return false; }

3)反转单向链表:

▼
Java
复制代码
public void reverse() { Node prev = null; Node current = head; Node next = null; while (current != null) { next = current.next; // 暂存下一个节点 current.next = prev; // 反转当前节点的指针 prev = current; // 向前移动prev current = next; // 向前移动current } head = prev; // 更新头节点 }

4)找两个单链表的交点,可以使用双指针法:

  • 设链表A长度为m,链表B长度为n,公共部分长度为k
  • 指针pA从链表A头部出发,走到末尾后切换到链表B头部继续走;指针pB从链表B头部出发,走到末尾后切换到链表A头部继续走
  • 如果有交点:两个指针都走了 (m - k) + k + (n - k) = m + n - k 步后,会在交点处相遇
  • 如果没有交点:两个指针都走了 m + n 步后,同时变为null,循环结束
  • 时间复杂度O(m + n),空间复杂度O(1)
▼
Java
复制代码
public static Node getIntersectionNode(Node headA, Node headB) { if (headA == null || headB == null) { return null; } Node pA = headA; Node pB = headB; // 两个指针走过的总路程相同,要么在交点相遇,要么同时为null while (pA != pB) { pA = (pA == null) ? headB : pA.next; // 走完A后切换到B pB = (pB == null) ? headA : pB.next; // 走完B后切换到A } return pA; // 交点,或者null表示不相交 }

相关LeetCode热门题目

给大家推荐一些练手题目:

  1. 206. 反转链表 - 反转一个单链表
  2. 21. 合并两个有序链表 - 将两个升序链表合并为一个新的升序链表
  3. 141. 环形链表 - 判断链表中是否有环
  4. 19. 删除链表的倒数第 N 个结点 - 删除链表的倒数第 n 个节点
  5. 160. 相交链表 - 找到两个单链表相交的起始节点