使双向链表可迭代

Question

我不知道如何在使用嵌套循环时使双向链表的可迭代性正常工作。

我试图让它可迭代：

def __iter__(self):
    self.index = 0
    return (self)

def next(self):
    try:
        result = self._findNode(self.index).get()
    except IndexError:
        self.index = 0
        raise StopIteration
    self.index += 1
    return result

def __getitem__(self, item):
    return self._findNode(item).get()

如果在一个 for 循环中似乎有效，但在两个循环中无效：

myList = DoublyLinkedList()

myList.append(0)
myList.append(1)
myList.append(2)
myList.append(3)

for i in myList:
    print i         #works as expected

for i in myList:
    for j in myList:
        print j     #goes forever

我想问题是对象内部只有一个 self.index 被两个 for 循环更新，但我不知道如何解决这个问题。

Answer 1

我想你很清楚问题出在哪里：

1 for i in mylist: 
2    for j in mylist:
3        print j
4    # when j loop ends index goes back 0, this is where the infinite
5    # loop is,next line in execution is 1, and the method called is
6    # "next()", it will read linkedlist[0] for the second time (and
7    # then repeat...forever)

简而言之，每次在 i 循环中调用 next 时，它只会 return doubleLinkedList[0]，它朝着索引异常前进。

有很多解决方案，
1. 如果你在嵌套 for 循环中所做的只是 print j，你可以简单地遍历链表的长度：

for i in range(len(mylist)): # I see that you already have the __len__ method
    for j in mylist:
        print j

2.This 是我最喜欢的解决方案：代替 pf 实现迭代器接口，使用 python 生成器:

def traverseList(doubly_linked_list):
# select and delete all of your __iter__() and next(), use the following code
    index = 0
    while True:
        try:
            yield doubly_linked_list._findNode(index).get()
            index += 1
        except IndexError:
            break

for i in traverseList(mylist):
     for j in traverseList(mylist):
         # do things, note that I did not create two linked list
         # I sort of create two iterators...

如果你对generators不是太熟悉的话可以查一下coroutine，但是基本上他们都有自己的stack，所以每个iterator您的双向链表维护自己的 index（您尝试在代码中实现的目标）

3.hmmm还在想，有什么新想法会更新

Answer 2

Containers 应该是 Iterable，而不是 Iterators。不要在 class 本身上实现 next。要么使 __iter__ 成为一个生成器函数，要么为它写一个单独的 class 到 return 来包装 linked 列表并实现 next.

最简单的方法是将 __iter__ 定义为 generator function:

def __iter__(self):
    cur = self.head
    while cur is not None:
        yield cur.value
        cur = cur.nextNode

从 DoubleLinkedList 中删除 next 函数，仅此而已。当您尝试使用 for 循环对其进行迭代时，对生成器函数 return 的调用是一个新的独立生成器对象，然后该对象独立于可能已请求的任何其他生成器进行迭代。而且它比像你所做的那样重复索引要快得多（它必须从 head 开始并每次遍历；生成器在运行时保存状态，所以它只遍历链中的一个 link每一项 yielded).

使双向链表可迭代

Making a Doubly Linked list iterable

python

class

iterable