Python中的双向链表
Python中的双向链表
提问于 2018-08-05 01:45:02
我正在做一个项目，在这个项目中，我操作了大量排序的元素列表，并且我需要能够快速删除其中的任何元素。因为我不需要任何类型的索引，所以我认为双向链表结构将是最好的。我找不到任何好的预制模块，所以我自己做了一个：
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因为通过浏览来检查我想要删除的项是否在列表中会浪费时间，所以我在节点中添加了一个指向node所在列表的指针，这样我就可以检查我没有从错误的列表中删除内容。
这些列表存储在Python字典中，在某种程度上，我开始收到“node not in list”错误。有人知道它是怎么出现的吗？除了这里列出的方法之外，我从来不使用任何方法来操作列表...
否则，有没有人知道我可以用一个编码良好的模块来代替这个模块？
谢谢!
回答 1
Stack Overflow用户
发布于 2018-08-05 01:57:55
双向链表具有双向的链接。
示例：
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 在其他附加中也是类似的。如果您向双向链表添加/删除内容，则必须始终清除/重置/设置两个方向的所有链接：
(红色是追加时更改的所有变量)
从本质上讲，你的列表是不完整的--如果你对它进行操作/迭代，事情将会以意想不到的方式丢失
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51688159
复制相关文章
相似问题