Python实现双向链表

双向链表是一种常见的线性数据结构，它允许在任意位置插入、删除、查找节点，具有很好的灵活性和效率。本篇文章将介绍Python如何实现双向链表，包括链表的节点定义、插入删除操作的实现、以及几个示例来说明如何使用双向链表。

链表节点定义

首先，我们需要定义一个双向链表的节点类。节点包含三个属性：前一个节点的指针prev、当前节点的值val、下一个节点的指针next。

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

双向链表的插入操作

在双向链表中，我们可以在指定位置插入一个新节点。插入节点的基本操作包括以下几步：

1. 新建一个节点；
2. 将前一个节点的next指向新节点；
3. 将新节点的prev指向前一个节点，将新节点的next指向后一个节点；
4. 将后一个节点的prev指向新节点。

具体实现如下：

class DoublyLinkedList:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.head = None
        self.tail = None
        self.size = 0

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.size:  # 处理非法索引
            return

        if index == 0:  # 在头部插入
            self.addAtHead(val)
        elif index == self.size:  # 在尾部插入
            self.addAtTail(val)
        else:
            node = Node(val)
            curr = self.head
            for i in range(index - 1):
                curr = curr.next
            node.prev = curr  # 1. 将前一个节点的next指向新节点
            node.next = curr.next  # 2. 将新节点的prev指向前一个节点，将新节点的next指向后一个节点
            curr.next.prev = node  # 3. 将后一个节点的prev指向新节点
            curr.next = node
            self.size += 1

双向链表的删除操作

在双向链表中，我们可以在指定位置删除一个节点。删除节点的基本操作包括以下几步：

1. 将前一个节点的next指向后一个节点；
2. 将后一个节点的prev指向前一个节点。

具体实现如下：

class DoublyLinkedList:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.head = None
        self.tail = None
        self.size = 0

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:  # 处理非法索引
            return

        if index == 0:  # 删除头部节点
            self.head = self.head.next
            if self.head:  # 注意判断链表是否为空
                self.head.prev = None
            else:
                self.tail = None
        elif index == self.size - 1:  # 删除尾部节点
            self.tail = self.tail.prev
            self.tail.next = None
        else:
            curr = self.head
            for i in range(index):
                curr = curr.next
            curr.prev.next = curr.next  # 1. 将前一个节点的next指向后一个节点
            curr.next.prev = curr.prev  # 2. 将后一个节点的prev指向前一个节点
        self.size -= 1

示例说明

我们来看两个使用示例。

示例1：删除链表中的节点

dll = DoublyLinkedList()
dll.addAtHead(1)
dll.addAtTail(3)
dll.addAtIndex(1, 2)
dll.deleteAtIndex(1)
print(dll.head.val)  # 1
print(dll.head.next.val)  # 3

首先，创建一个双向链表，插入三个节点，值分别为1、2、3。然后，删除第二个节点，即值为2的节点。最后，打印链表头部节点和头部节点的下一个节点，结果分别为1、3。

示例2：反转双向链表

dll = DoublyLinkedList()
dll.addAtHead(1)
dll.addAtTail(3)
dll.addAtIndex(1, 2)

# 反转链表
new_head = dll.tail
while new_head:
    print(new_head.val)
    new_head = new_head.prev

首先，创建一个双向链表，插入三个节点，值分别为1、2、3。然后，使用while循环反转链表，按照逆序打印链表节点的值。最后的输出结果为3、2、1，说明链表已经被成功反转。