你想要实现的是一个使用双向链表实现的MutableSequence API。
在Python中,你应该依赖于collections.abc,它可以指导你完成所有必需方法的实现。
例如,一个链表实际上是从MutableSequence继承的类。
from collections.abc import MutableSequence
class LinkedList(MutableSequence):
pass
ll = LinkedList()
在实例化一个含有尚未编写的抽象方法的类时,你会收到一个
TypeError
,它将指导你需要实现哪些方法。
TypeError: Can't instantiate abstract class LinkedList with abstract methods __delitem__, __getitem__, __len__, __setitem__, insert
特别注意,
list
或
linked-list
不是一个迭代器,它是一个可迭代对象。这意味着
__iter__
方法不应该返回
self
并依赖于
__next__
,而是应该返回基于链接列表内容的全新迭代器。
换句话说,你只能通过迭代器遍历一次,但可以通过可迭代对象多次遍历。
完整实现
事实证明,我有一个按照这种方式实现的双向链接列表的完整实现。你可以看一下。
from collections.abc import MutableSequence
class LinkedList(MutableSequence):
class _Node:
def __init__(self, value, _next=None, _last=None):
self.value, self._next, self._last = value, _next, _last
def __str__(self):
return f'Node({self.value})'
def __init__(self, iterable=()):
self.start = None
self.last = None
empty = object()
iterable = iter(iterable)
first = next(iterable, empty)
if first is empty:
return
current = self._Node(first)
self.start, self.last = current, current
for value in iterable:
new_node = self._Node(value, _last=self.last)
self.last._next = new_node
self.last = new_node
def __len__(self):
if self.start is None:
return 0
else:
return sum(1 for _ in self)
def __iter_nodes(self):
current = self.start
while current is not None:
yield current
current = current._next
def __reversed_iter_nodes(self):
current = self.last
while current is not None:
yield current
current = current._last
def __iter__(self):
for node in self.__iter_nodes():
yield node.value
def __reversed__(self):
for node in self.__reversed_iter_nodes():
yield node.value
def __get_node(self, index):
if index >= 0:
for item in self.__iter_nodes():
if index == 0:
return item
index -= 1
else:
for item in self.__reversed_iter_nodes():
if index == 0:
return item
index += 1
raise IndexError
def __getitem__(self, index):
if index >= 0:
for item in self:
if index == 0:
return item.value
index -= 1
else:
for item in reversed(self):
if index == 0:
return item.value
index += 1
raise IndexError
def __setitem__(self, key, value):
self[key].value = value
def __delitem__(self, key):
node = self[key]
if node._last:
node._last._next = node._next
if node._next:
node._next._last = node._last
def insert(self, index, value):
if index > len(self):
self.last = self._Node(value, _last=self.last)
else:
where = self.__get_node(index)
_last = where._last
new_node = self._Node(value, _next=where, _last=_last)
if _last:
_last._next = new_node
else:
self.start = new_node
where._last = new_node
例子
ll = LinkedList(range(1, 5))
print(*ll)
print(*reversed(ll))
ll.insert(2, 'foo')
print(*ll)
输出
1 2 3 4
4 3 2 1
1 2 foo 3 4
NodeDLL
类的类定义,以便正确缩进。 - blhsingLinkedListIterator
所做的那样,将你的代码复制粘贴为文本吗?这样我们就可以轻松地运行并自己尝试它,而不是将其作为图片发布。 - blhsing