如何在链表中间添加或删除节点？基于Python代码的实现问询

我正在尝试实现链表中间节点的删除操作。目前已用__setitem__方法实现链表首尾添加节点，用__delitem__方法实现首尾节点删除，但不清楚如何通过这两个方法实现中间节点的添加与删除。比如添加中间节点时，需要遍历到指定索引，记录前驱节点（previous）和当前节点（current），将前驱节点指向新节点，新节点指向当前节点。

以下是未完成的Python代码：

from utils import Node, Collections, StaticArray

class LinkedList(Collections):
    def __init__(self, isSet = False, isDoubly = False, isCircular = False):
        super(LinkedList,self).__init__()
        self.head=None
        self.isSet= isSet
        self.isDoubly=isDoubly
        self.isCircular=isCircular
    def __getitem__(self, index):
        count=0
        cur=self.head
        while True:
            if cur == None:
                break
                
            if count ==index:
                return cur 
            
            cur=cur.next
            count += 1
            
    def __setitem__(self, index, value):
        if self.head==None:
            self.head=Node(value)
        elif index == 0: #adding a value in the front 
            node=Node(value)
            node.next=self.head   # node = E, self.head =A
            self.head=node #node=E -> self.head =A
            
            if self.isDoubly:
                self.head.prev=node
            self.head=node
            
            
        elif self[index]==None: #adding a value in the end 
            self[len(self)-1]
            cur.next=Node(value)
            if self.isCircular:
                cur.next.next=self.head
        
        #else add to middle 
    
    def __delitem__(self, index):
        if self.head==None:
            return
        elif index==0: #removing from the front 
            self.head=self.head.next
        elif index==self.get_size()-1: #removing from the end
            cur=self[self.get_size()-2] #get the second to last nod3 
            
            cur.next=None #point to none
            
       # else: #remove form middle

问题修正与中间节点实现 #

先修复原代码中的几个问题：

• __setitem__头部添加双向链表逻辑错误：新节点成为head后，应让原head的prev指向新节点，而非新节点的prev指向自身
• __setitem__尾部添加时未将self[len(self)-1]赋值给cur，导致cur未定义

接下来完善中间节点的添加与删除逻辑：

1. 中间节点添加逻辑

找到目标索引的前驱节点（index-1位置的节点），将前驱节点的next指向新节点，新节点的next指向原索引位置的节点。如果是双向链表，需额外维护prev指针；循环链表仅需在首尾操作时维护循环指向。

2. 中间节点删除逻辑

找到前驱节点，将前驱节点的next指向待删除节点的下一个节点。如果是双向链表，需同步更新待删除节点下一个节点的prev指针。

修正并完善后的完整代码：

from utils import Node, Collections, StaticArray

class LinkedList(Collections):
    def __init__(self, isSet = False, isDoubly = False, isCircular = False):
        super(LinkedList,self).__init__()
        self.head=None
        self.isSet= isSet
        self.isDoubly=isDoubly
        self.isCircular=isCircular

    def __getitem__(self, index):
        count=0
        cur=self.head
        while cur is not None:
            if count == index:
                return cur 
            cur=cur.next
            count += 1
        # 索引超出范围返回None
        return None
    
    def __setitem__(self, index, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            # 循环链表单个节点指向自身
            if self.isCircular:
                self.head.next = self.head
        elif index == 0: # 头部添加
            new_node.next = self.head
            if self.isDoubly:
                self.head.prev = new_node
            self.head = new_node
            # 循环链表维护首尾循环
            if self.isCircular:
                last_node = self[self.get_size()-1]
                last_node.next = self.head
        elif self[index] is None: # 尾部添加
            last_node = self[self.get_size()-1]
            last_node.next = new_node
            if self.isDoubly:
                new_node.prev = last_node
            # 循环链表维护首尾循环
            if self.isCircular:
                new_node.next = self.head
        else: # 中间添加
            prev_node = self[index-1]
            current_node = prev_node.next
            prev_node.next = new_node
            new_node.next = current_node
            # 双向链表维护prev指针
            if self.isDoubly:
                new_node.prev = prev_node
                current_node.prev = new_node

    def __delitem__(self, index):
        if self.head is None:
            return
        size = self.get_size()
        if index < 0 or index >= size:
            # 索引越界直接返回
            return
        elif index == 0: # 头部删除
            if size == 1:
                self.head = None
            else:
                self.head = self.head.next
                if self.isDoubly:
                    self.head.prev = None
                # 循环链表维护首尾循环
                if self.isCircular:
                    last_node = self[size-2]
                    last_node.next = self.head
        elif index == size-1: # 尾部删除
            prev_node = self[index-1]
            prev_node.next = None
            if self.isDoubly:
                prev_node.next = None
            # 循环链表维护首尾循环
            if self.isCircular:
                prev_node.next = self.head
        else: # 中间删除
            prev_node = self[index-1]
            del_node = prev_node.next
            next_node = del_node.next
            prev_node.next = next_node
            # 双向链表维护prev指针
            if self.isDoubly:
                next_node.prev = prev_node

关键逻辑说明 #

• 中间添加：通过__getitem__获取前驱节点，调整next指针完成插入；双向链表额外维护prev指针保证双向关联。
• 中间删除：跳过待删除节点，直接关联前驱和后继节点；双向链表同步更新后继节点的prev指针。
• 循环链表：仅在首尾操作时维护最后一个节点指向head的循环关系，中间操作无需额外处理。

内容的提问来源于stack exchange，提问作者prodoto