跳到主要内容

链表操作

介绍​

链表是一种常见的线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表在内存中是非连续存储的，这使得它在插入和删除操作上更加高效。链表有多种类型，包括单链表、双链表和循环链表。本文将重点介绍单链表的基本操作。

链表的基本结构​

链表的基本单位是节点（Node），每个节点包含两个部分：

  1. 数据域：存储节点的值。
  2. 指针域：存储指向下一个节点的指针。

以下是一个简单的单链表节点的定义：

python
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

链表的基本操作​

1. 创建链表​

创建一个链表需要初始化一个头节点（head），头节点是链表的起点。以下是一个简单的链表创建示例：

python
class LinkedList:
    def __init__(self):
        self.head = None

2. 插入节点​

链表的插入操作可以在链表的头部、尾部或任意位置进行。

在头部插入节点​

在头部插入节点是最简单的操作之一，只需要将新节点的 next 指针指向当前的头节点，然后将头节点更新为新节点。

python
def insert_at_head(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

在尾部插入节点​

在尾部插入节点需要遍历链表，找到最后一个节点，然后将最后一个节点的 next 指针指向新节点。

python
def insert_at_tail(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
        return
    last_node = self.head
    while last_node.next:
        last_node = last_node.next
    last_node.next = new_node

3. 删除节点​

删除节点操作可以通过修改指针来实现。以下是从链表中删除指定值的节点的示例：

python
def delete_node(self, key):
    temp = self.head

    # 如果头节点就是要删除的节点
    if temp is not None and temp.data == key:
        self.head = temp.next
        temp = None
        return

    # 查找要删除的节点
    while temp is not None:
        if temp.data == key:
            break
        prev = temp
        temp = temp.next

    # 如果链表中没有找到要删除的节点
    if temp == None:
        return

    # 从链表中删除节点
    prev.next = temp.next
    temp = None

4. 遍历链表​

遍历链表是访问链表中每个节点的基本操作。以下是一个简单的遍历链表的函数：

python
def print_list(self):
    temp = self.head
    while temp:
        print(temp.data, end=" -> ")
        temp = temp.next
    print("None")

实际应用案例​

链表在实际编程中有广泛的应用，例如：

  1. 实现栈和队列：链表可以用于实现栈（LIFO）和队列（FIFO）数据结构。
  2. 内存管理：操作系统中的内存管理通常使用链表来跟踪空闲内存块。
  3. 图算法：在图的邻接表表示中，链表用于存储每个顶点的邻居节点。

以下是一个使用链表实现栈的示例：

python
class Stack:
    def __init__(self):
        self.head = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if self.head is None:
            return None
        popped = self.head.data
        self.head = self.head.next
        return popped

总结​

链表是一种灵活且高效的数据结构，特别适合频繁插入和删除操作的场景。通过本文，你应该已经掌握了链表的基本操作，包括创建链表、插入节点、删除节点和遍历链表。链表在实际编程中有广泛的应用，理解其原理和操作对于编程学习至关重要。

附加资源与练习​

  • 练习：尝试实现一个双链表，并为其添加插入和删除操作。
  • 进一步学习：探索循环链表及其应用场景。
  • 推荐阅读：《算法导论》中的链表章节，深入了解链表的算法复杂度分析。