双链表插入节点python

### 如何在 Python 中实现双链表插入节点

为了实现在双链表中插入新节点的功能，可以定义一个 `DoublyLinkedList` 类以及相应的操作方法。以下是具体实现：

#### 定义节点类
每个节点不仅包含数据部分，还含有两个指针分别指向其前驱和后继节点。

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None  # 指向下一个结点
        self.prev = None  # 指向前一个结点

#### 插入节点到头部
当需要将新的元素作为第一个元素加入时，会创建一个新的头节点并更新前后链接关系[^2]。

def insert_at_head(self, new_data):
    new_node = Node(new_data)

    if not self.head:
        self.head = new_node
    else:
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node

#### 在指定位置之前插入节点
如果要在已有的某个特定位置之前插入，则需遍历直到找到目标位置，并调整相邻三个节点之间的连接[^1]。

def insert_before(self, target_node_data, new_data):
    curr = self.head
    
    while curr and curr.data != target_node_data:
        curr = curr.next
        
    if curr is None:
        raise Exception("The given node with provided value was not found")

    new_node = Node(new_data)
    
    prev_node = curr.prev
    
    # 更新前后节点的关系
    new_node.next = curr
    new_node.prev = prev_node
    
    if prev_node is not None:
        prev_node.next = new_node
    else:
        self.head = new_node  # 新增节点成为新的head
    
    curr.prev = new_node

通过上述代码片段展示了如何构建支持双向访问特性的链表结构及其基本的操作函数之一——插入功能。此设计允许高效地执行前置或后置插入动作而无需重新排列整个序列中的其他成员[^3]。