Python 数据结构：双向链表（Doubly Linked List）

# /*
# Python 数据结构：双向链表（Doubly Linked List）
# --------------------------------------------------------
# 概念：
# 双向链表每个节点包含前驱（prev）和后继（next）指针，
# 可以从任意节点向前或向后遍历。
#
# 特点：
# 1) 插入与删除效率高，尤其是中间节点；
# 2) 遍历灵活，可正向或反向访问；
# 3) 可用于实现浏览器前进/后退、缓存管理等场景。
# */

# ========================================================
# 双向链表节点定义
# ========================================================
class DNode:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

# ========================================================
# 双向链表实现
# ========================================================
class DoublyLinkedList:
    def __init__(self):
        self.head = None

    # 尾插法添加节点
    def append(self, data):
        new_node = DNode(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
        new_node.prev = current

    # 遍历打印链表（正向）
    def display_forward(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

    # 遍历打印链表（反向）
    def display_backward(self):
        current = self.head
        if not current:
            print("链表为空")
            return
        # 找到尾节点
        while current.next:
            current = current.next
        # 反向遍历
        while current:
            print(current.data, end=" <-> ")
            current = current.prev
        print("None")

    # 删除指定节点
    def delete(self, key):
        current = self.head
        while current:
            if current.data == key:
                # 更新前驱节点
                if current.prev:
                    current.prev.next = current.next
                else:  # 删除头节点
                    self.head = current.next
                # 更新后继节点
                if current.next:
                    current.next.prev = current.prev
                return
            current = current.next

# ========================================================
# 示例演示
# ========================================================
dll = DoublyLinkedList()
for value in [10, 20, 30, 40]:
    dll.append(value)

print("正向遍历:")
dll.display_forward()

print("反向遍历:")
dll.display_backward()

print("\n删除节点 20:")
dll.delete(20)
dll.display_forward()

print("\n删除头节点 10:")
dll.delete(10)
dll.display_forward()

print("\n删除尾节点 40:")
dll.delete(40)
dll.display_forward()

print("\n删除最后节点 30:")
dll.delete(30)
dll.display_forward()

# ========================================================
# 要点总结：
# --------------------------------------------------------
# 1) 双向链表每个节点有 prev 和 next 指针；
# 2) 插入与删除节点无需从头遍历到尾节点，效率更高；
# 3) 正向与反向遍历都很方便；
# 4) 删除头尾节点时需特别处理指针更新；
# 5) 常用于实现 LRU 缓存、双向队列、浏览器历史管理等场景。
# */

#
# 正向遍历:
# 10 <-> 20 <-> 30 <-> 40 <-> None
# 反向遍历:
# 40 <-> 30 <-> 20 <-> 10 <-> None
#
# 删除节点 20:
# 10 <-> 30 <-> 40 <-> None
#
# 删除头节点 10:
# 30 <-> 40 <-> None
#
# 删除尾节点 40:
# 30 <-> None
#
# 删除最后节点 30:
# None