基于python实现双向链表

实现双向链表需要以下几个步骤：

1. 定义节点类

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

链表节点需要存储的信息有：值、上一个节点的引用（即prev），下一个节点的引用（即next）。

2. 初始化链表

class DoubleLinkedList:
    def __init__(self):
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail    # 头节点的next指针指向尾节点
        self.tail.prev = self.head    # 尾节点的prev指针指向头节点
        self.length = 0

初始化时需要创建头和尾节点，使其相互指向，并设置初始长度为0。

3. 插入节点

class DoubleLinkedList:
    ...
    def insert(self, val):
        # 创建新节点
        new_node = ListNode(val=val)
        # 新节点的next指向原头节点的next
        new_node.next = self.head.next
        # 原头节点的next的prev指向新节点
        self.head.next.prev = new_node
        # 头节点的next指向新节点
        self.head.next = new_node
        # 新节点的prev指向头节点
        new_node.prev = self.head
        # 长度+1
        self.length += 1

插入节点需要在头节点和第一个节点之间插入。新节点的next指针指向原头节点的next，原头节点的next的prev指针指向新节点，头节点的next指针指向新节点，新节点的prev指针指向头节点，最后将长度加一。

4. 删除节点

class DoubleLinkedList:
    ...
    def delete(self, val):
        cur = self.head.next
        while cur != self.tail:
            if cur.val == val:
                cur.prev.next = cur.next
                cur.next.prev = cur.prev
                self.length -= 1
                return True
            cur = cur.next
        return False

删除节点需要遍历链表，找到对应的节点后，将其前后的节点相互连接，长度减一。如果找不到对应节点则返回False。

示例1：插入节点

my_linked_list = DoubleLinkedList()
my_linked_list.insert(1)
my_linked_list.insert(2)
my_linked_list.insert(3)

执行后my_linked_list的状态如下：

head -> 1 <-> 2 <-> 3 <- tail

示例2：删除节点

my_linked_list = DoubleLinkedList()
my_linked_list.insert(1)
my_linked_list.insert(2)
my_linked_list.insert(3)
my_linked_list.delete(2)

执行后my_linked_list的状态如下：

head -> 1 <-> 3 <- tail