当前位置： 首页 > article >正文

玩转python: 掌握Python数据结构之链表

article 2025/3/20 20:18:16

链表是计算机科学中最基础的数据结构之一，也是许多高级数据结构和算法的基础。本文将带你从零开始，逐步掌握链表的概念、实现和应用。通过丰富的案例和通俗易懂的解释，你将能够轻松理解并应用链表。

什么是链表？

链表是一种线性数据结构，由一系列节点（Node）组成。每个节点包含两个部分：数据域和指针域。数据域用于存储数据，指针域用于指向下一个节点。链表中的节点通过指针连接在一起，形成一个链式结构。

与数组不同，链表的内存空间不需要连续分配。这意味着链表可以更灵活地利用内存空间，但也意味着访问链表中的元素需要从头节点开始逐个遍历。

链表的类型

链表有多种类型，常见的有：

  1. 单链表（Singly Linked List）：每个节点只有一个指针，指向下一个节点。
  2. 双链表（Doubly Linked List）：每个节点有两个指针，一个指向前一个节点，一个指向下一个节点。
  3. 循环链表（Circular Linked List）：尾节点的指针指向头节点，形成一个环。

本文将重点介绍单链表，因为它是最基础且最常用的链表类型。

单链表的实现

在Python中，我们可以通过定义一个Node类和一个LinkedList类来实现单链表。

1. 定义节点类

首先，我们需要定义一个节点类Node，它包含数据域和指针域。

class Node:
    def __init__(self, data):
        self.data = data  # 数据域
        self.next = None  # 指针域，初始化为None

2. 定义链表类

接下来，我们定义一个链表类LinkedList，它包含对链表的各种操作，如插入、删除、遍历等。

class LinkedList:
    def __init__(self):
        self.head = None  # 头节点，初始化为None

    # 在链表末尾插入节点
    def append(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  # 将新节点插入到末尾

    # 在链表头部插入节点
    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head  # 新节点的指针指向当前头节点
        self.head = new_node  # 更新头节点为新节点

    # 删除指定数据的节点
    def delete(self, data):
        current_node = self.head
        if current_node and current_node.data == data:  # 如果头节点就是要删除的节点
            self.head = current_node.next
            current_node = None
            return
        prev_node = None
        while current_node and current_node.data != data:  # 遍历查找要删除的节点
            prev_node = current_node
            current_node = current_node.next
        if current_node is None:  # 如果没找到要删除的节点
            return
        prev_node.next = current_node.next  # 跳过要删除的节点
        current_node = None

    # 打印链表
    def print_list(self):
        current_node = self.head
        while current_node:
            print(current_node.data, end=" -> ")
            current_node = current_node.next
        print("None")

3. 使用链表

现在，我们可以使用LinkedList类来创建和操作链表。

# 创建一个链表
llist = LinkedList()

# 在链表末尾插入节点
llist.append(1)
llist.append(2)
llist.append(3)

# 在链表头部插入节点
llist.prepend(0)

# 打印链表
llist.print_list()  # 输出: 0 -> 1 -> 2 -> 3 -> None

# 删除节点
llist.delete(2)

# 打印链表
llist.print_list()  # 输出: 0 -> 1 -> 3 -> None

链表的应用案例

链表在实际应用中有很多用途，以下是几个常见的案例：

1. 实现队列

队列是一种先进先出（FIFO）的数据结构，链表可以很方便地实现队列。

class Queue:
    def __init__(self):
        self.linked_list = LinkedList()

    # 入队
    def enqueue(self, data):
        self.linked_list.append(data)

    # 出队
    def dequeue(self):
        if self.linked_list.head is None:
            return None
        data = self.linked_list.head.data
        self.linked_list.delete(data)
        return data

    # 打印队列
    def print_queue(self):
        self.linked_list.print_list()

# 使用队列
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.print_queue()  # 输出: 1 -> 2 -> 3 -> None
print(queue.dequeue())  # 输出: 1
queue.print_queue()  # 输出: 2 -> 3 -> None

2. 实现栈

栈是一种后进先出（LIFO）的数据结构，链表也可以很方便地实现栈。

class Stack:
    def __init__(self):
        self.linked_list = LinkedList()

    # 入栈
    def push(self, data):
        self.linked_list.prepend(data)

    # 出栈
    def pop(self):
        if self.linked_list.head is None:
            return None
        data = self.linked_list.head.data
        self.linked_list.delete(data)
        return data

    # 打印栈
    def print_stack(self):
        self.linked_list.print_list()

# 使用栈
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.print_stack()  # 输出: 3 -> 2 -> 1 -> None
print(stack.pop())  # 输出: 3
stack.print_stack()  # 输出: 2 -> 1 -> None

3. 反转链表

反转链表是一个经典的面试题，我们可以通过修改指针的方向来实现。

def reverse_linked_list(llist):
    prev_node = None
    current_node = llist.head
    while current_node:
        next_node = current_node.next  # 保存下一个节点
        current_node.next = prev_node  # 反转指针
        prev_node = current_node  # 移动prev_node
        current_node = next_node  # 移动current_node
    llist.head = prev_node  # 更新头节点

# 反转链表
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.print_list()  # 输出: 1 -> 2 -> 3 -> None
reverse_linked_list(llist)
llist.print_list()  # 输出: 3 -> 2 -> 1 -> None

4. 链表实现LRU缓存

LRU（Least Recently Used）缓存是一种常见的缓存淘汰策略，它会优先淘汰最近最少使用的数据。链表可以很好地支持LRU缓存的实现。

案例：浏览器缓存

假设你正在浏览网页，浏览器会将你最近访问的网页缓存起来。当你访问一个新网页时，如果缓存已满，浏览器会淘汰最久未访问的网页缓存。这个过程可以用链表来实现。

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity  # 缓存容量
        self.cache = {}  # 存储缓存数据
        self.linked_list = LinkedList()  # 使用链表记录访问顺序

    # 获取缓存数据
    def get(self, key):
        if key in self.cache:
            # 如果缓存中有该数据，将其移到链表头部（表示最近使用）
            self.linked_list.delete(key)
            self.linked_list.prepend(key)
            return self.cache[key]
        return -1  # 如果缓存中没有该数据，返回-1

    # 插入缓存数据
    def put(self, key, value):
        if key in self.cache:
            # 如果缓存中已有该数据，更新其值并移到链表头部
            self.linked_list.delete(key)
        elif len(self.cache) >= self.capacity:
            # 如果缓存已满，淘汰链表尾部的数据（最久未使用）
            last_key = self.linked_list.head
            while last_key.next:
                last_key = last_key.next
            self.linked_list.delete(last_key.data)
            del self.cache[last_key.data]
        # 将新数据插入链表头部
        self.linked_list.prepend(key)
        self.cache[key] = value

# 使用LRU缓存
cache = LRUCache(2)
cache.put(1, "网页1")
cache.put(2, "网页2")
print(cache.get(1))  # 输出: 网页1
cache.put(3, "网页3")  # 缓存已满，淘汰网页2
print(cache.get(2))  # 输出: -1（网页2已被淘汰）
通俗解释：
  • 链表记录了数据的访问顺序，最近访问的数据在链表头部，最久未访问的数据在链表尾部。
  • 当缓存满时，直接淘汰链表尾部的数据，确保缓存中始终保留最近使用的数据。

5. 链表实现多项式相加

多项式相加是数学中常见的操作，链表可以用来表示多项式，并实现相加功能。

案例：多项式计算

假设有两个多项式：

  • 多项式A：3x^2 + 2x + 5
  • 多项式B：4x^3 + 2x^2 + 1

我们可以用链表表示这两个多项式，并实现它们的相加。

class PolynomialTerm:
    def __init__(self, coefficient, exponent):
        self.coefficient = coefficient  # 系数
        self.exponent = exponent  # 指数
        self.next = None  # 指向下一个项的指针

class Polynomial:
    def __init__(self):
        self.head = None  # 多项式的头节点

    # 添加项
    def add_term(self, coefficient, exponent):
        new_term = PolynomialTerm(coefficient, exponent)
        if self.head is None:
            self.head = new_term
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_term

    # 打印多项式
    def print_polynomial(self):
        current = self.head
        while current:
            print(f"{current.coefficient}x^{current.exponent}", end=" + " if current.next else "\n")
            current = current.next

    # 多项式相加
    def add_polynomials(poly1, poly2):
        result = Polynomial()
        current1 = poly1.head
        current2 = poly2.head
        while current1 and current2:
            if current1.exponent > current2.exponent:
                result.add_term(current1.coefficient, current1.exponent)
                current1 = current1.next
            elif current1.exponent < current2.exponent:
                result.add_term(current2.coefficient, current2.exponent)
                current2 = current2.next
            else:
                result.add_term(current1.coefficient + current2.coefficient, current1.exponent)
                current1 = current1.next
                current2 = current2.next
        # 将剩余项加入结果
        while current1:
            result.add_term(current1.coefficient, current1.exponent)
            current1 = current1.next
        while current2:
            result.add_term(current2.coefficient, current2.exponent)
            current2 = current2.next
        return result

# 创建多项式A：3x^2 + 2x + 5
polyA = Polynomial()
polyA.add_term(3, 2)
polyA.add_term(2, 1)
polyA.add_term(5, 0)

# 创建多项式B：4x^3 + 2x^2 + 1
polyB = Polynomial()
polyB.add_term(4, 3)
polyB.add_term(2, 2)
polyB.add_term(1, 0)

# 相加并打印结果
result = Polynomial.add_polynomials(polyA, polyB)
result.print_polynomial()  # 输出: 4x^3 + 5x^2 + 2x + 6
通俗解释：
  • 每个链表节点表示多项式的一个项，包含系数和指数。
  • 通过遍历两个链表，将相同指数的项相加，最终得到一个新的多项式。

6. 链表实现约瑟夫问题

约瑟夫问题是一个经典的数学问题，描述如下：n个人围成一圈，从第k个人开始报数，数到m的人出列，直到所有人出列。链表可以很好地模拟这个过程。

案例：游戏中的淘汰机制

假设你和朋友们围成一圈玩“数到3就淘汰”的游戏，链表可以模拟这个过程。

def josephus(n, k, m):
    # 创建循环链表
    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None
    head = Node(1)
    prev = head
    for i in range(2, n + 1):
        new_node = Node(i)
        prev.next = new_node
        prev = new_node
    prev.next = head  # 形成环

    # 找到第k个人
    current = head
    for _ in range(k - 1):
        current = current.next

    # 开始报数并淘汰
    while current.next != current:
        # 报数到m-1
        for _ in range(m - 1):
            current = current.next
        # 淘汰第m个人
        print(f"淘汰：{current.next.data}")
        current.next = current.next.next
        current = current.next
    print(f"最后剩下：{current.data}")

# 使用约瑟夫问题
josephus(5, 1, 3)  # 输出: 淘汰：3 -> 淘汰：1 -> 淘汰：5 -> 淘汰：2 -> 最后剩下：4
通俗解释：
  • 链表模拟了一个圆圈，每个人是一个节点，节点的指针指向下一个人。
  • 从第k个人开始报数，数到m的人被淘汰（从链表中移除），直到最后剩下一个人。

总结

通过以上案例，我们可以看到链表在实际问题中的广泛应用。无论是缓存管理、数学计算还是游戏模拟，链表都能提供高效的解决方案。希望这些案例能帮助你更好地理解链表的应用场景，并激发你进一步探索数据结构的兴趣！


http://www.kler.cn/a/575902.html

相关文章：

  • 【从零开始学习计算机科学】数字逻辑（六）组合逻辑电路
  • ES Module 的 import 导入和 import () 动态导入
  • 《Python实战进阶》No13: NumPy 数组操作与性能优化
  • 在16卡服务器上使用最新版的CUDA和驱动训练`llama - 2 - 7b`和`llama - 2 - 70b`模型，并生成训练指标数据
  • 以商业思维框架为帆，驭创业浪潮前行
  • 智慧农业中，物联网（IoT）通过集成产量数据和市场价格信息
  • 计算机毕业设计SpringBoot+Vue.js校园资产管理(源码+文档+PPT+讲解)
  • 23种设计模式之《适配器模式（Adapter）》在c#中的应用及理解
  • 数字孪生对于新基建的价值浅析，算是抛砖引玉。
  • 网络安全总集成服务
  • svn删除所有隐藏.svn文件，文件夹脱离svn控制
  • 基于磁数据的伤痕、生锈、断丝分类训练平台搭建规划
  • 从零开始实现大语言模型（十四）：高阶训练技巧
  • flink集成oracle 19c详解
  • Dify 开源大语言模型应用开发平台使用（二）
  • 隐私保护在 Facebook 用户身份验证中的应用
  • c++ 调用 gurobi 库，cmake，mac
  • 计算机毕业设计SpringBoot+Vue.js网络海鲜市场系统(源码+文档+PPT+讲解)
  • 动态规划背包刷题
  • 城市智慧路灯的 (运营 管理 运维)实现方案和技术架构