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

双向链表：实现、操作与分析【算法 17】

article 2024/11/15 8:24:21

双向链表：实现、操作与分析

请添加图片描述

引言

双向链表（Doubly Linked List）是链表数据结构的一种重要形式，它允许节点从两个方向进行遍历。与单向链表相比，双向链表中的每个节点不仅包含指向下一个节点的指针（或引用），还包含指向前一个节点的指针（或引用）。这种结构使得双向链表在插入和删除节点时更加灵活和高效，特别是在需要频繁访问前驱节点的情况下。

双向链表的实现

节点定义

首先，我们需要定义双向链表的节点。每个节点包含三个部分：存储的数据、指向下一个节点的指针（或引用）以及指向前一个节点的指针（或引用）。

class ListNode:  
    def __init__(self, value=0, prev=None, next=None):  
        self.value = value  
        self.prev = prev  
        self.next = next

双向链表类

接下来，我们定义双向链表类，包含初始化链表、插入节点、删除节点、遍历链表等基本操作。

class DoublyLinkedList:  
    def __init__(self):  
        self.head = None  
        self.tail = None  
  
    def append(self, value):  
        """在链表末尾添加节点"""  
        new_node = ListNode(value)  
        if not self.head:  
            self.head = self.tail = new_node  
        else:  
            self.tail.next = new_node  
            new_node.prev = self.tail  
            self.tail = new_node  
  
    def prepend(self, value):  
        """在链表开头添加节点"""  
        new_node = ListNode(value)  
        if not self.head:  
            self.head = self.tail = new_node  
        else:  
            self.head.prev = new_node  
            new_node.next = self.head  
            self.head = new_node  
  
    def delete_node(self, node):  
        """删除指定节点"""  
        if not node:  
            return  
        if node.prev:  
            node.prev.next = node.next  
        else:  
            self.head = node.next  
        if node.next:  
            node.next.prev = node.prev  
        else:  
            self.tail = node.prev  
  
    def print_list(self):  
        """打印链表"""  
        current = self.head  
        while current:  
            print(current.value, end=" ")  
            current = current.next  
        print()