在链表的索引处插入

Question

为什么insert at index方法不能正常工作？有人可以解释一下吗？我相信我做对了。或者根据我的理解，我认为，正在发生的事情是我正在将我想要新数据的索引旁边的先前节点分配给该位置的旧节点。

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

class LinkedList:
    def __init__(self):
        self.head = None
    
    def add_at_beggining(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def print_list(self):
        if(self.head == None):
            print("linkedList is empty")
        else:
            curr = self.head
            while curr is not None:
                print(curr.data)
                curr = curr.next

    def add_at_end(self, data):
        new_node = Node(data)
        if(self.head == None):
            new_node = self.head
        else:
            curr = self.head
            while curr.next is not None:
                curr = curr.next
            curr.next = new_node

    def get_length(self):
        size = 0
        curr = self.head
        while curr is not None:
            size+=1
            curr = curr.next
        
        return size

    def remove_at(self,index):
        if index < 0 or index<= self.get_length():
            raise Exception("invalid input")
        
        if index == 0:
            self.head = self.head.next
            return
        count = 0
        curr = self.head
        while curr:
            if count == index -1:
                curr.next = curr.next.next
                break
            curr = curr.next
            count +=1

    def add_at_index(self,data,index):
        new_node = Node(data)
        if index < 0 or index >= self.get_length():
            raise Exception("invalid input")
        if index == 0:
            new_node.next = self.head
            self.head = new_node
        #code is good upto here
        count = 0
        curr = self.head
        while curr is not None:
            if count == index-1:
                new_node = curr.next
                break
            curr = curr.next 
            count +=1

Answer 1

您正在用 curr.next 覆盖 new_node。这不会修改列表。相反，您丢失了对您创建的新节点的引用。相反：

if count == index-1:
    new_node.next = curr.next
    curr.next = new_node
    break

还有一些其他问题：

add_at_index开头的if条件应该允许索引等于列表的长度，这意味着插入将在最后一个节点之后发生。所以应该是：

    if index < 0 or index > self.get_length():
        raise Exception("invalid input")

在 remove_at 中，类似的 if 条件不允许接受任何好的索引。第二种情况是比较器的方向错误。应该是：

    if index < 0 or index >= self.get_length():
        raise Exception("invalid input")

Answer 2

我明白了，但现在我想打印语句以可视化更多但它们不会打印哈哈

def add_at_index(self,data,index):
        new_node = Node(data)
        if index < 0 or index >= self.get_length():
            raise Exception("invalid input")
        if index == 0:
            new_node.next = self.head
            self.head = new_node
        #code is good upto here
        count = 0
        curr = self.head
        while curr is not None:
            if count == index-1:
                #Need to assign old node to new node pointer
                new_node.next = curr.next
                curr.next = new_node
                break
            print("curr:" , curr)
            curr = curr.next
            count+=1

在链表的索引处插入

Insert at index in linked List

python

linked-list