<p>您要实现的是一个<code>MutableSequence</code>的API,它实现了一个双链接列表。在</p>
<p>要在Python中做到这一点,您应该依赖于<code>collections.abc</code>,它可以指导您完成实现所有必需方法的过程。在</p>
<p>例如,链表实际上是从<code>MutableSequence</code>继承的类。在</p>
<pre><code>from collections.abc import MutableSequence
class LinkedList(MutableSequence):
pass
ll = LinkedList()
</code></pre>
<p>在实例化一个有一些尚未编写的抽象方法的类时,您将得到一个<code>TypeError</code>,它将指导您完成需要实现的方法。在</p>
^{pr2}$
<p>特别是,请注意,<code>list</code>或链表不是一个<em>迭代器</em>,而是一个<em>iterable</em>。这意味着<code>__iter__</code>方法不应返回<code>self</code>,而应依赖于<code>__next__</code>,而应返回链接列表内容的全新迭代器。在</p>
<p>换句话说,您只能通过一个<em>迭代器</em>迭代一次,并且可以多次遍历和<em>iterable</em>。在</p>
<h2>全面实施</h2>
<p>结果我得到了一个完全的双链表实现方式。你可以看看。在</p>
<pre><code>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
</code></pre>
<h2>示例</h2>
<pre><code>ll = LinkedList(range(1, 5))
print(*ll)
print(*reversed(ll))
ll.insert(2, 'foo')
print(*ll)
</code></pre>
<h2>输出</h2>
<pre><code>1 2 3 4
4 3 2 1
1 2 foo 3 4
</code></pre>