doubly Linked list iterator python

Question

I am constructing a doubly linked list and I am struggling on construct a doubly linked list 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 a test it said TypeError: iteration over non-sequence. Did I do something wrong ?

• Igonato: In __init__ where is self.head coming from? And how do you iterate?
• Andrew Clark: How are you creating your ListIterator object? Something is definitely wrong there, since self._current = self.head will raise and AttributeError in __init__().
• Tommy: I implemented a doubly linked list earlier here is the code for doubly linked list class class DoublyLinkedList: #init def __init__(self): self.head= None self.tail= None self.size = 0 in that class I have add remove len methods
• Hai Vu: Please help others to help you by posting the more completed code, starting with init

Answer 1

As posted, the code doesn't initialize (i.e. self.head isn't defined).

But overall, you are on the right track. Take a look at the source for Python's collections.OrderedDict for a worked-out example of traversing a doubly linked list.

Here's 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

• Raymond Hettinger: The message TypeError: iteration over non-sequence means that Python cannot find an __iter__ method for an object. Also note that in Python 3, we use __next__ instead of next.

Answer 2

I think there are two important things to fix.

First, your DoublyLinkedList class doesn't have an __iter__ method. You probably want to create one that returns a ListIterator instance. Perhaps you're trying to do this manually, but this would be the normal approach.

Second, you need to fix the code in your ListIterator to work properly. Currently your __init__ method doesn't initialize things correctly, and your next method tries to access member variables like size that don't exist.

Here's an implementation that 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're defining classes with no bases. This is fine in Python 3 (where object will be the base by default), but in Python 2 this will result in getting an "old-style" class. Old-style classes are deprecated, and you'll find that some language features won't work properly with them (though not any of the features involved in iteration, as far as I know). On the other hand, if you are already using Python 3 then you need to define a __next__ method in the iterator class, rather than next (without the underscores).

Answer 3

Here is an example for Doubly 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, may 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 don't have to implement next()

Update

Here is an example usage:

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

Answer 5

If you're just iterating/traversing through the linked list you can try a basic set up for both the node and the Doublyll objects, and replace the val with whatever you defined in your code:

class Node:
 def __init__(self, val):
 self.val = val
 self.next = None
 self.prev = None
class Doublyll:
 def __init__(self):
 self.head = None
 self.tail = None
 self.size = 0
 def traversal(self):
 curr = self.head
 while curr:
 print(curr.val, end='--')
 curr = curr.next 
 print('None')