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

Python双向链表教程：概念、实现与应用详解

Python双向链表教程

概念、实现与应用详解

深入理解双向链表数据结构及其在Python中的实现

什么是双向链表？

双向链表（Doubly Linked List）是一种常见的数据结构，与单向链表不同，双向链表中的每个节点除了包含数据域（data）和指向下一个节点的指针（next）外，还包含一个指向前一个节点的指针（prev）。这种结构使得从任意一个节点开始，可以方便地访问前一个节点和后一个节点。

双向链表结构可视化

HEAD
⇨
10
⇦
⇨
20
⇦
⇨
30
⇨
TAIL

双向链表节点结构：[prev | data | next]

双向链表的特点：

  • 双向遍历：可以从头到尾或从尾到头遍历链表
  • 高效删除：删除节点时不需要查找前驱节点
  • 内存开销：每个节点需要额外空间存储前驱指针
  • 动态大小：链表大小可以动态增长或缩小

Python实现双向链表

下面我们使用Python来实现一个完整的双向链表：

节点类实现

Node类 - 双向链表的基本单元 
class Node:
    """双向链表节点类"""
    def __init__(self, data):
        self.data = data    # 节点存储的数据
        self.prev = None    # 指向前一个节点的指针
        self.next = None    # 指向后一个节点的指针
        
    def __repr__(self):
        return f"Node({self.data})"

双向链表类实现

DoublyLinkedList类 - 完整的双向链表实现 
class DoublyLinkedList:
    """双向链表实现类"""
    def __init__(self):
        self.head = None  # 链表头节点
        self.tail = None  # 链表尾节点
        self.size = 0     # 链表大小
    
    def is_empty(self):
        """检查链表是否为空"""
        return self.size == 0
    
    def append(self, data):
        """在链表尾部添加节点"""
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1
    
    def prepend(self, data):
        """在链表头部添加节点"""
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.size += 1
    
    def insert_after(self, target_data, data):
        """在指定节点后插入新节点"""
        current = self.head
        while current:
            if current.data == target_data:
                new_node = Node(data)
                new_node.prev = current
                new_node.next = current.next
                
                if current.next:
                    current.next.prev = new_node
                else:  # 如果目标节点是尾节点
                    self.tail = new_node
                
                current.next = new_node
                self.size += 1
                return
            current = current.next
        raise ValueError(f"节点 {target_data} 不存在")
    
    def delete(self, data):
        """删除指定节点"""
        if self.is_empty():
            raise Exception("链表为空")
        
        current = self.head
        while current:
            if current.data == data:
                if current.prev:  # 不是头节点
                    current.prev.next = current.next
                else:  # 是头节点
                    self.head = current.next
                
                if current.next:  # 不是尾节点
                    current.next.prev = current.prev
                else:  # 是尾节点
                    self.tail = current.prev
                
                self.size -= 1
                return
            current = current.next
        raise ValueError(f"节点 {data} 不存在")
    
    def display_forward(self):
        """正向遍历链表"""
        current = self.head
        while current:
            print(current.data, end=" ⇨ " if current.next else "\n")
            current = current.next
    
    def display_backward(self):
        """反向遍历链表"""
        current = self.tail
        while current:
            print(current.data, end=" ⇦ " if current.prev else "\n")
            current = current.prev
    
    def __len__(self):
        """返回链表长度"""
        return self.size
    
    def __repr__(self):
        """链表可视化表示"""
        nodes = []
        current = self.head
        while current:
            nodes.append(str(current.data))
            current = current.next
        return " ⇨ ".join(nodes)

使用示例

双向链表使用示例 
# 创建双向链表
dll = DoublyLinkedList()

# 添加元素
dll.append(10)
dll.append(20)
dll.append(30)
dll.prepend(5)

# 在20后面插入25
dll.insert_after(20, 25)

print("正向遍历:")
dll.display_forward()  # 输出: 5 ⇨ 10 ⇨ 20 ⇨ 25 ⇨ 30

print("\n反向遍历:")
dll.display_backward()  # 输出: 30 ⇦ 25 ⇦ 20 ⇦ 10 ⇦ 5

# 删除节点
dll.delete(20)
print("\n删除20后:")
dll.display_forward()  # 输出: 5 ⇨ 10 ⇨ 25 ⇨ 30

print(f"\n链表长度: {len(dll)}")  # 输出: 4

双向链表的优点

  • 支持双向遍历，访问节点更灵活
  • 删除操作更高效，时间复杂度为O(1)
  • 插入操作更灵活，可以在任意节点前后插入
  • 不需要预先分配内存空间

双向链表的缺点

  • 每个节点需要额外空间存储前驱指针
  • 实现比单向链表更复杂
  • 随机访问效率低，时间复杂度为O(n)
  • 需要维护额外的指针关系

双向链表的应用场景

音乐播放器播放列表

双向链表非常适合实现音乐播放器的播放列表，用户可以轻松地切换到上一首或下一首歌曲。

浏览器历史记录

浏览器的前进和后退功能可以通过双向链表实现，每个节点存储访问的页面，prev指向前一页，next指向下一页。

撤销/重做功能

在文本编辑器或图形软件中，双向链表可用于实现撤销(undo)和重做(redo)功能。

LRU缓存实现

在实现LRU（最近最少使用）缓存淘汰算法时，双向链表配合哈希表可以提供高效的实现。

总结

双向链表是一种重要的数据结构，它克服了单向链表只能单向遍历的缺点，但相应地增加了存储空间（因为多了一个指针）。在Python中，我们可以通过定义节点类和链表类来实现双向链表，并实现插入、删除、遍历等操作。

掌握双向链表对于理解更复杂的数据结构（如双向循环链表）以及解决实际问题非常有帮助。在实际应用中，双向链表在需要双向遍历的场景中表现出色，如实现浏览器历史记录、音乐播放列表等。

虽然Python内置的list类型在大多数情况下足够使用，但理解链表等底层数据结构有助于我们编写更高效、更专业的代码，特别是在处理大数据量或特殊需求时。

© 2023 Python数据结构教程 | 双向链表概念与实现

本文由ShuFuTuo于2025-08-07发表在吾爱品聚，如有疑问，请联系我们。
本文链接：https://www.521pj.cn/20257556.html

相关文章

发表评论