向用两个列表实现的链表添加一个节点

Question

我正在Python中使用两个列表实现一个链表 - 一个存储值，一个存储指针，这样一个节点在

values

中有它的值，并且它指向的值存储在

pointers中相应的索引中

数组。

我编写了一个函数，将一个节点添加到链表的头部。它会增加两个数组中的每个元素，同时记住最后一个元素，以便可以将其附加到末尾，然后将新节点插入到列表的 0 索引处。

我将

self.pointers

的索引保留为

self.values

，因为它们的大小相同并且以相同的方式调整。

我的代码：

class LinkedList:
    def __init__(self):
        self.values = []
        self.pointers = []
        
    def addAtHead(self, val):
        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)
        

ll = LinkedList()
ll.addAtHead(10)
ll.addAtHead(20)

当我运行此程序时，出现以下错误：

Traceback (most recent call last):
  File "/main.py", line 29, in <module>
    ll.addAtHead(2)
  File "/main.py", line 20, in addAtHead
    self.pointers[0] = self.values[1]
                       ~~~~~~~~~~~^^^
IndexError: list index out of range

但是需要这个语句来附加第一个节点...

我的错误是什么？

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