双向链表的操作方法总结

1. 基本概念

双向链表是一种数据结构，它不仅存储了指向下一个节点的指针（next），还添加了一个指向前一个节点的指针（prev）。这种设计使得在双向链表中插入和删除元素变得更加灵活。双向链表的每个节点通常包含三个部分：数据域、前向指针以及后向指针。

2. 初始化

初始化一个双向链表需要创建头节点和尾节点，并将它们相互链接，形成闭合环路，或者仅设置为单个空节点（未形成闭环）。

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

def create_node(value):
    return Node(value)

# 初始化双向链表
head = create_node(None)
tail = head

3. 插入操作

3.1 在链表尾部插入元素

将新节点的 next 指针指向当前尾节点，同时将尾节点的 prev 指向新节点，并更新尾节点为新节点。

def append(self, value):
    new_node = create_node(value)
    if self.tail is None:
        # 如果链表为空，则新建一个节点
        self.head = new_node
        self.tail = new_node
    else:
        # 新节点的前向指针指向当前尾部，尾部后向指针指向新节点
        new_node.prev = self.tail
        self.tail.next = new_node
        # 更新新的尾节点
        self.tail = new_node

3.2 在链表头部插入元素

将新节点的 prev 指针指向当前头节点，同时将头节点的 next 指向新节点，并更新头节点为新节点。

def prepend(self, value):
    new_node = create_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

3.3 在任意位置插入元素

在链表中的某个指定位置插入一个新节点。首先找到待插入的位置，然后调整前后指针指向。

def insert(self, position, value):
    if position <= 0:
        self.prepend(value)
    elif position >= len(self) - 1:
        self.append(value)
    else:
        current = self.head
        index = 0
        while index < position:
            current = current.next
            index += 1
        
        new_node = create_node(value)
        
        # 调整前后节点的指针指向新节点
        current.prev.next = new_node
        new_node.prev = current.prev
        new_node.next = current
        current.prev = new_node

4. 删除操作

4.1 删除链表尾部元素

找到尾节点，将其前一个节点的 next 指针设置为 None，并更新尾指针。

def pop(self):
    if self.tail is None:
        return None
    value = self.tail.value
    # 如果是最后一个节点
    if self.head == self.tail:
        self.head = None
        self.tail = None
    else:
        prev_tail = self.tail.prev
        self.tail = prev_tail
        prev_tail.next = None

    return value

4.2 删除链表头部元素

找到头节点，将其后一个节点的 prev 指针设置为 None，并更新头指针。

def pop_first(self):
    if self.head is None:
        return None
    value = self.head.value
    # 如果只有一个节点
    if self.head == self.tail:
        self.head = None
        self.tail = None
    else:
        new_head = self.head.next
        self.head = new_head
        new_head.prev = None

    return value

4.3 删除任意位置的元素

找到要删除节点的位置，调整前后节点的指针指向。

def remove(self, position):
    if position <= 0:
        return self.pop_first()
    elif position >= len(self) - 1:
        return self.pop()
    
    current = self.head
    index = 0
    
    while index < position:
        current = current.next
        index += 1
    
    prev_node = current.prev
    next_node = current.next
    
    # 调整前后节点的指针指向
    prev_node.next = next_node
    if next_node:
        next_node.prev = prev_node

5. 遍历操作

遍历双向链表，可以通过从头部或尾部开始进行前向或者后向遍历。

def traverse(self, order="forward"):
    current = self.head if order == "forward" else self.tail
    while current:
        yield current.value
        current = current.next if order == "forward" else current.prev

6. 链表长度

计算链表中的节点数量。

def __len__(self):
    count = 0
    current = self.head
    while current:
        count += 1
        current = current.next
    return count

通过上述操作方法，可以灵活地进行双向链表的创建、插入、删除和遍历等基本操作。这些基础的实现将为更复杂的数据处理提供强有力的支持。