02 | 双向链表：如何实现高效地插入与删除

在数据结构与算法的世界中，链表作为一种基础且灵活的数据结构，广泛应用于各种编程场景。相较于数组，链表在动态内存管理、高效插入与删除操作方面具有显著优势。而双向链表（Doubly Linked List）作为链表的一种变体，更是在这些优势的基础上增加了向前遍历的能力，进一步提升了操作的灵活性。本章将深入探讨双向链表如何实现高效的插入与删除操作，并通过代码示例详细阐述其工作原理。

一、双向链表的基本概念

双向链表是一种链式数据结构，其中每个节点包含三个部分：存储数据元素的数据域、指向下一个节点的指针（或引用）以及指向前一个节点的指针（或引用）。这种结构允许我们从链表的任何节点开始，向前或向后遍历整个链表。

双向链表节点的定义（以Python为例）：

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

在上面的代码中，ListNode类定义了双向链表的节点，其中value用于存储数据，prev和next分别指向前一个和后一个节点。

二、双向链表的插入操作

双向链表的插入操作相对灵活，可以在链表的头部、尾部或任意指定位置插入新节点。下面分别讨论这三种情况的实现方法。

2.1 在链表头部插入节点

在链表头部插入节点时，需要更新新节点的next指针指向原头节点，并更新原头节点的prev指针指向新节点。如果链表为空（即没有头节点），则新节点同时成为头节点和尾节点，其prev和next都设为None。

代码示例：

class DoublyLinkedList:
    def __init__(self):
        self.head = None
    def insert_at_head(self, value):
        new_node = ListNode(value)
        if not self.head:
            self.head = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

2.2 在链表尾部插入节点

在链表尾部插入节点时，首先检查链表是否为空。如果为空，则新节点即为头节点和尾节点。如果不为空，遍历到当前尾节点，更新其next指针指向新节点，并设置新节点的prev指针指向当前尾节点。

代码示例：

def insert_at_tail(self, value):
    new_node = ListNode(value)
    if not self.head:
        self.head = new_node
    else:
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
        new_node.prev = current

2.3 在链表指定位置插入节点

在链表中的指定位置（非头尾）插入节点时，需要找到该位置的前一个节点，然后更新指针关系。这涉及到遍历链表直到找到正确的前置节点。

代码示例：

def insert_at_position(self, position, value):
    if position <= 0:
        self.insert_at_head(value)
        return
    new_node = ListNode(value)
    current = self.head
    index = 0
    while current and index < position - 1:
        current = current.next
        index += 1
    if not current:  # 如果position超出链表长度
        return
    new_node.next = current.next
    if current.next:
        current.next.prev = new_node
    current.next = new_node
    new_node.prev = current

三、双向链表的删除操作

双向链表的删除操作同样高效，因为它可以直接通过节点的prev和next指针来跳过要删除的节点，从而保持链表的连续性。

3.1 删除链表头部节点

删除链表头部节点时，只需更新头指针指向原头节点的下一个节点，并处理原头节点的next节点（如果存在）的prev指针。

代码示例：

def delete_head(self):
    if not self.head:
        return None
    temp = self.head
    self.head = self.head.next
    if self.head:
        self.head.prev = None
    return temp

3.2 删除链表尾部节点

删除链表尾部节点时，需要先遍历到倒数第二个节点，然后更新其next指针为None，并处理原尾节点的内存释放（在Python等高级语言中，通常通过垃圾回收机制自动处理）。

代码示例：

def delete_tail(self):
    if not self.head:
        return None
    if not self.head.next:
        temp = self.head
        self.head = None
        return temp
    current = self.head
    while current.next.next:
        current = current.next
    temp = current.next
    current.next = None
    return temp

3.3 删除链表中的指定节点

删除链表中的指定节点时，需要找到该节点的前一个节点，并更新其next指针指向待删除节点的下一个节点（如果存在），同时处理待删除节点的next节点的prev指针（如果存在）。

代码示例：

def delete_node(self, node):
    if not node or not self.head:
        return
    if node == self.head:
        self.delete_head()
        return
    if not node.next:
        current = self.head
        while current.next != node:
            current = current.next
        current.next = None
        return
    node.prev.next = node.next
    if node.next:
        node.next.prev = node.prev

四、总结

双向链表通过引入指向前一个节点的指针，使得在链表中的插入与删除操作更加高效和灵活。无论是头部、尾部还是指定位置的插入与删除，双向链表都能通过直接修改节点间的指针关系来完成，无需像数组那样进行大量元素的移动。这种特性使得双向链表在需要频繁进行插入和删除操作的场景中表现出色。通过本章的学习，读者应该能够深入理解双向链表的结构特点及其高效插入与删除操作的实现原理。