python - Python 中的双向链表

Question

我正在开发一个项目，在该项目中我操作大量排序的元素列表，并且我需要能够快速删除其中的任何一个。由于我不需要任何类型的索引，因此我认为双向链表结构是最好的。我找不到任何好的预制模块，所以我自己制作了:

class Node: # nodes for doubly-linked lists
    def __init__(self, val, dll):
        self.val = val
        self.next = None
        self.prev = None
        self.dll = dll

class DLList: # doubly-linked lists
    def __init__(self):
        self.first = None
        self.last = None
        self.len = 0

#    def __iter__(self):
#        self.curr = self.first
#        return self
#    
#    def __next__(self):
#        if self.curr == None:
#            raise StopIteration
#        self.curr = self.curr.next
#        if self.curr == None:
#            raise StopIteration
#        return self.curr

    def append(self, val): # add a node with value val at the end of the list
        node = Node(val, self)
        node.prev = self.last
        self.last = node
        if self.first == None: # <=> if self was empty
            self.first = node
        self.len += 1

    def appendleft(self, val): # same as previous, but at the beginning of the list
        node = Node(val, self)
        node.next = self.first
        self.first = node
        if self.last == None:
            self.last = node
        self.len += 1

    def nodeat(self, i): # gives the ith node (starting at 0)
        if i == -1:
            return None
        if i > self.len or i < -1:
            raise IndexError('index out of range')
        curr = self.first
        for j in range(i):
            curr = curr.next
        return curr

    def remove(self, node): # remove a given node in the list
        if node.dll != self: #cannot remove a node that is not in the list
            raise ValueError('node not in list')
        p = node.prev
        n = node.next
        v = node.val
        node.dll = None
        if p != None:
            p.next = n
        else:
            self.first = n
        if n != None:
            n.prev = p
        else:
            self.last = p
        self.len -= 1
        return v

    def add(self, val, i): # add a node at the ith place in the list
        node = Node(val, self)
        if i > self.len:
            raise IndexError('index out of range')
        self.len += 1
        previ = self.nodeat(i)
        node.prev = previ.prev
        node.next = previ
        previ.prev = node

    def clear(self): # empty the list
        self.first = None
        self.last = None
        self.len = 0

    def extend(self, iterable): # add the elements of iterable in order at the end of the list
        for i in iterable:
            self.append(i)
            self.len += 1

    def extendleft(self, iterable): # same as previous, but at the beginning (and in reverse order)
        for i in iterable:
            self.appendleft(i)
            self.len += 1

    def dll_to_list(self): # return a python list with the elements of the doubly-linked list
        res = []
        curr = self.first
        while curr != None:
            res.append(curr.val)
            curr = curr.next
        return res

    def is_empty(self): # check whether the list is empty
        return self.len == 0

由于我会浪费时间通过浏览来检查要删除的项目是否在列表中，因此我在节点内部添加了一个指向节点所在列表的指针，以便我可以检查我是否没有删除错误列表中的内容。

这些列表存储在 Python 字典中，在某些时候我开始收到“节点不在列表中”错误。有谁知道它是如何出现的？除了这里列出的方法之外，我从不使用任何其他方法来操作列表...

否则，有谁知道我可以使用一个编码良好的模块来代替这个模块？

谢谢!

Answer 1

双向链表具有双向链接。

示例:

def append(self, val): # add a node with value val at the end of the list
    node = Node(val, self)  # new node, ok
    node.prev = self.last   # ok, the new nodes prev is the last node of your list
    self.last = node        # ok, your new node is now the last of your list 
    if self.first == None:  # yeah, ok, if its empty its also the first one now
        self.first = node
    self.len += 1

但是......你没有设置反向:

    node.prev.next = node  # before  node.prev = self.last   

与您的其他附录类似。如果您向双向链表添加/删除内容，则必须始终清除/重置/设置两个方向上的所有链接:

(红色是附加上所有更改的变量)

本质上你的列表并不完整 - 如果你对其进行操作/迭代，事情会以意想不到的方式丢失