Double linked list python iterator

Question

I am creating a doubly linked list and I am struggling to build a double join iterator method in PYTHON .

This is my code so far

class DoubleListNode: def __init__(self,data): self.data=data self.prev = None self.next= None class ListIterator: def __init__(self): self._current = self.head def __iter__(self): return self def next(self): if self.size == 0 : raise StopIteration else: item = self._current.data self._current=self._current.next return item class DoublyLinkedList: def __init__(self): self.head= None self.tail= None self.size = 0 def add(self,data): newnode= DoubleListNode(data) self.size+=1 if self.head is None: self.head = newnode self.tail = self.head elif data < self.head.data: # before head newnode.next = self.head self.head.prev= newnode self.head= newnode elif data > self.tail.data: # at the end newnode.prev= self.tail self.tail.next= newnode self.tail=newnode else: curNode = self.head while curNode is not None and curNode.data < data: curNode=curNode.next newnode.next= curNode newnode.prev=curNode.prev curNode.prev.next= newnode curNode.prev=newnode def remove(self,data): curNode=self.head while curNode is not None and curNode.data!= data: curNode= curNode.next if curNode is not None: self.size -= 1 if curNode is self.head: self.head= curNode.next else: curNode.prev.next=curNode.next if curNode is self.tail: self.tail=curNode.prev else: curNode.next.prev=curNode.prev 

When I run the test, he said TypeError: iteration over non-sequence . Did I do something wrong?

Answer 1

I think there are two important things that need to be fixed.

First, your DoublyLinkedList class DoublyLinkedList not have a __iter__ method. You probably want to create one that returns an instance of ListIterator . You may be trying to do this manually, but this will be the usual approach.

Secondly, you need to fix the code in ListIterator to work properly. Currently, your __init__ method does not initialize things correctly, and your next method tries to access member variables, such as size , that do not exist.

An implementation will be implemented here, which I think will work:

 def ListIterator(object): def __init__(self, node): self.current = node def __iter__(self): return self def next(self): if self.current is None: raise StopIteration() result = self.current.data self.current = self.current.next return result class DoublyLinkedList(object): # all your current stuff, plus: def __iter__(self): return ListIterator(self.head) 

As a side note in your current code, you define classes without reason. This is good in Python 3 (where object will be the default base), but in Python 2 this will result in an "old style" class. Old classes are deprecated, and you will find that some language functions will not work with them properly (although not all functions related to iteration, as far as I know). On the other hand, if you are already using Python 3, you need to define the __next__ method in the iterator class, not next (without underscore).

Answer 2

As indicated, the code is not initialized (i.e. self.head is undefined).

But overall, you are on the right track. Take a look at the source for Python.OrderedDict collections for an elaborate example of going through a doubly linked list.

Here is a simplified example:

 class Link: def __init__(self, value, prev=None, next=None): self.value = value self.prev = prev self.next = next def __iter__(self): here = self while here: yield here.value here = here.next def __reversed__(self): here = self while here: yield here.value here = here.prev if __name__ == '__main__': a = Link('raymond') b = Link('rachel', prev=a); a.next=b c = Link('matthew', prev=b); b.next=c print 'Forwards:' for name in a: print name print print 'Backwards:' for name in reversed(c): print name 

Answer 3

Here is an example for the Double Linked List class.

 class Node: def __init__(self, val): self.data = val self.next = None self.prev = None class LinkedList: def __init__(self): self.head = None self.tail = None self.count = 0 def insert(self, val): newNode = Node(val) if self.count == 0: self.head = newNode self.tail = newNode else: self.head.prev = newNode newNode.next = self.head self.head = newNode self.count += 1 def insertToEnd(self, val): newNode = Node(val) if self.count == 0: self.head = newNode self.tail = newNode else: self.tail.next = newNode newNode.prev = self.tail self.tail = newNode self.count += 1 def search(self, val): p = self.head while p is not None: if p.data == val: return p p = p.next def delete(self, val): curNode = self.head while curNode != None: if curNode.data == val: if curNode.prev != None: curNode.prev.next = curNode.next else: self.head = curNode.next if curNode.next != None: curNode.next.prev = curNode.prev else: self.tail = curNode.prev self.count -= 1 curNode = curNode.next def show(self): s = "" p = self.head while p is not None: s += str(p.data) + ' '; p = p.next print(s + "| count: " + str(self.count)) 

Answer 4

Based on what you post, can I suggest:

 class ListIterator: # other stuff ... def __iter__(self): while self._current: yield self._current.data self._current = self._current.next self._current = self.head # Reset the current pointer 

You do not need to implement next ()

Update

Here is a usage example:

 for data in myListIterator: print data # Without reset, the second time around won't work: for data in myListIterator: print data