python实现双向链表原理

Python实现双向链表原理

双向链表是一种非常经典的数据结构，它的每一个节点都有两个指针，一个指向前驱节点，一个指向后继节点。相对于单向链表，双向链表能够快速地在任意位置插入或删除元素，因此被广泛地应用于实际场景中。

Python语言提供了很多数据结构类型，包括列表、字典、集合等等。但是在某些情况下，双向链表也能够更好地满足我们的需求。本篇文章将详细介绍Python实现双向链表的原理及代码实现。

双向链表的结构

首先，我们需要定义一个双向链表的节点类。它需要包含三个属性：value、prev、next。其中，value表示节点存储的值，prev表示前驱节点，next表示后继节点。代码如下所示：

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

然后，我们需要定义一个双向链表类。它需要包含两个属性：head、tail。其中，head表示双向链表的头节点，tail表示双向链表的尾节点。代码如下所示：

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

在双向链表中，每一个节点都有一个前驱节点和一个后继节点。因此，我们需要实现向双向链表中添加节点的方法 add_node，它需要按照正确的顺序往链表中插入节点。我们可以定义三种情况：

1. 链表为空，直接将节点插入到头部即可；
2. 链表非空，节点需要插入到头部；
3. 链表非空，节点需要插入到中间或者尾部。

代码如下所示：

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    # 向链表中添加节点
    def add_node(self, value):
        # 创建新节点
        new_node = Node(value)

        # 链表为空，直接将节点插入到头部
        if self.head is None:
            self.head = new_node
            self.tail = new_node

        # 链表非空，节点需要插入到头部
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

在双向链表中，每一个节点都有一个前驱节点和一个后继节点。因此，我们需要实现从双向链表中删除节点的方法 remove_node，它需要按照正确的顺序将节点从链表中删除。我们可以定义三种情况：

1. 链表为空，无需进行任何操作；
2. 链表仅有一个元素，直接将头部和尾部节点清空即可；
3. 链表非空，需要删除中间或者尾部的节点。

代码如下所示：

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    # 向链表中添加节点
    def add_node(self, value):
        # 创建新节点
        new_node = Node(value)

        # 链表为空，直接将节点插入到头部
        if self.head is None:
            self.head = new_node
            self.tail = new_node

        # 链表非空，节点需要插入到头部
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

    # 从链表中删除节点
    def remove_node(self, value):
        # 链表为空，无需进行任何操作
        if self.head is None:
            return

        # 链表仅有一个元素，直接将头部和尾部节点清空即可
        elif self.head == self.tail and self.head.value == value:
            self.head = None
            self.tail = None

        # 链表非空，需要删除中间或者尾部的节点
        else:
            curr_node = self.head
            while curr_node:
                # 找到匹配的节点，删除它
                if curr_node.value == value:
                    # 中间节点
                    if curr_node.prev and curr_node.next:
                        curr_node.prev.next = curr_node.next
                        curr_node.next.prev = curr_node.prev

                    # 尾部节点
                    elif curr_node == self.tail:
                        self.tail = curr_node.prev
                        curr_node.prev.next = None

                    # 头部节点
                    else:
                        self.head = curr_node.next
                        curr_node.next.prev = None

                    del curr_node
                    break

                curr_node = curr_node.next

示例说明

示例 1：添加节点

以下是通过双向链表添加 1、2、3 三个节点后的链表结构：

doubly_linked_list = DoublyLinkedList()
doubly_linked_list.add_node(3)
doubly_linked_list.add_node(2)
doubly_linked_list.add_node(1)

print(doubly_linked_list.head.value)  # 1
print(doubly_linked_list.head.next.value)  # 2
print(doubly_linked_list.head.next.next.value)  # 3

print(doubly_linked_list.tail.value)  # 3
print(doubly_linked_list.tail.prev.value)  # 2
print(doubly_linked_list.tail.prev.prev.value)  # 1

示例 2：删除节点

以下是通过双向链表删除 2 节点后的链表结构：

doubly_linked_list = DoublyLinkedList()
doubly_linked_list.add_node(3)
doubly_linked_list.add_node(2)
doubly_linked_list.add_node(1)

doubly_linked_list.remove_node(2)

print(doubly_linked_list.head.value)  # 1
print(doubly_linked_list.head.next.value)  # 3
print(doubly_linked_list.tail.value)  # 3
print(doubly_linked_list.tail.prev.value)  # 1