Создание двойного связанного списка iterable

Question

Я не могу понять, как правильно выполнить итерабельность моего двойного связного списка при использовании вложенных циклов.

Мой код до сих пор: http://pastebin.com/PU9iFggr

Я попытался сделать его итерацию:

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() 

Это похоже на работу, если внутри одного для цикла, но не внутри двух:

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

Container s должно быть Iterable, а не Iterator s. Не используйте next на самом классе. Либо сделайте __iter__ функцией генератора, либо напишите отдельный класс для его возврата, который обертывает связанный список и реализует next.

Самый простой подход заключается в определении __iter__ как generator function:

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

Удалить функцию next из DoubleLinkedList и это все. Когда вы пытаетесь выполнить итерацию с помощью цикла for, вызов функции-генератора возвращает новый независимый объект-генератор, который затем выполняет итерацию независимо от любых других генераторов, которые могли быть запрошены. И это намного быстрее, чем повторная индексация, как вы делали (которая должна начинаться с head и проходить каждый раз, генератор сохраняет состояние по мере его поступления, поэтому он перемещается только по одной ссылке в цепочке для каждого элемента yield ed).

Answer 2

Я думаю, что вы очень хорошо знаете, где проблема:

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) 

короче каждый раз, когда вы звоните следующий в я цикл, он просто будет возвращать doubleLinkedList [0], это сделать для прогресса к исключению индекса.

Есть много решений,
1. если все, что вы делаете в вложенном для петли print j, вы можете просто просто итерацию по длине вашей LinkedList:

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

2.Это мое любимое решение: Вместо пф реализует интерфейс итератора, используйте питон генератор:

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... 

вы можете посмотреть сотрудничества рутина, если вы не слишком хорошо знакомы с генераторами, но в основном они имеют свой собственный стек, так что каждый итератор вашего двусвязному списка поддерживает свой собственный индекс (то, что вы пытаетесь достичь в своем коде)

3 .hmmm Я все еще думаю, я буду обновлять, если у меня появятся новые идеи