为什么我的在头部添加链表节点的函数不起作用？

Question

我正在使用两个数组在python中实现一个链表 - 一个用于存储值，一个用于存储指针，以便节点在值中具有其值，并且它指向的值存储在指针数组中相应的索引中。这是将节点添加到链表头部的函数。

我编写了该函数，以便它在记住最后一个元素的同时，增加两个数组中的每个元素，以便可以将其附加到末尾，然后在数组的 0 索引处插入新节点。我还没有运行代码，因为它是我尚未完成实现的更大类的一部分，但 chatgpt 确实不喜欢我的代码，我将不胜感激关于我的代码中是否存在严重逻辑错误的任何建议：

def addAtHead(self, val):

    """
    :type val: int
    :rtype: None
    """
    
    if not self.values:
        self.values.append(val)         
        self.pointers.append(None)      
        return
    
    append_val = self.values[-1]
    
    for i in range(1, len(self.values)):
        self.values[len(self.values) - i] = self.values[len(self.values) - i-1]
        self.pointers[len(self.values) - i] = self.pointers[len(self.values) - i-1]


    self.values[0] = val
    self.pointers[0] = self.values[1]

    self.values.append(append_val)
    self.pointers.append(None)

我将 self.pointers 的索引保留为 self.values，因为它们的大小相同并且以相同的方式调整。

Answer 1

这里有几个问题：

• 您的代码不存储任何指针。在使用列表的上下文中，指向列表条目的“指针”将是一个index。但是使用

  self.pointers[0] = self.values[1]

  ，您分配一个 值，而不是 索引。

• 将所有条目向前移一位以便为新负责人腾出空间的方法是一种低效的方法。它消除了您期望从链表中获得的好处，链表应该允许在恒定时间内将新节点添加为头而无需任何循环（无论链表中已有多少元素）。

• 这种方法还使得存储值的索引也是它在链表中的顺序。但这使得

  pointers

  列表毫无用处：您只需从左到右迭代

  values

  列表即可按预期顺序访问值，并且您只有一个普通的

  list

  。当您

  不

  移动值，但无论您从列表中添加或删除什么内容，都将它们保留在原来的位置时，pointers变得很有用。然后

  pointers

  列表负责指示它们在链表中的相对顺序。

这也意味着，如果您从链接列表中删除一个项目，则不必移动任何其他值。您应该更新受影响的

pointers

，以便跳过该节点并且不再是链表的一部分。

实施

用两个列表实现链表有点尴尬，因为Python是一种基于对象的语言，所以OOP方法是更自然的方法。但如果你真的想用两个列表来做到这一点，那么还需要维护一个“空闲列表”，即先前删除的节点的链接列表，可以重新用于存储新值。

为了进行演示，我添加了另外两个方法：一个使链表可迭代（这有助于打印），以及一个

remove

方法从链表中删除第一次出现的给定值。

class LinkedList:
    def __init__(self):
        self.values = []
        self.pointers = []
        self.free = None
        self.head = None
        
    def add_head(self, val):
        if self.free is None:  # There is no free slot
            # Create a free slot
            self.free = len(self.values)
            self.values.append(None)
            self.pointers.append(None)
        # Get the index of a free slot
        i = self.free
        self.free = self.pointers[i]  # Update to link the next free slot
        # Populate the newly occupied slot
        self.values[i] = val
        self.pointers[i] = self.head  # link to what was previously the head
        self.head = i  # The new node is now the head
        
    def __iter__(self):
        i = self.head
        while i is not None:
            yield self.values[i]
            i = self.pointers[i]

    def remove(self, val):
        prev = None
        # Find first occurrence of val 
        i = self.head
        while i is not None and self.values[i] != val:
            prev = i  # Keep track of the node that precedes it
            i = self.pointers[i]
        if i is not None:  # Value was found
            # Exclude the node
            if prev is None:  # The node to remove is the head node
                self.head = self.pointers[i]
            else:
                self.pointers[prev] = self.pointers[i]
            # Prepend this slot to the free list
            self.pointers[i] = self.free
            self.free = i

# demo
ll = LinkedList()
ll.add_head(5)
ll.add_head(3)
ll.add_head(2)
print(*ll)  # 2 3 5
ll.remove(3)
print(*ll)  # 2 5
ll.remove(2)
print(*ll)  # 5
ll.add_head(4)
print(*ll)  # 4 5
ll.add_head(8)
print(*ll)  # 8 4 5