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 ?

In __init__ where is self.head coming from? And how do you iterate? — Igonato
– Igonato, Commented Mar 29, 2013 at 20:29
How are you creating your ListIterator object? Something is definitely wrong there, since self._current = self.head will raise and AttributeError in __init__(). — Andrew Clark
– Andrew Clark, Commented Mar 29, 2013 at 20:31
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 — Tommy
– Tommy, Commented Mar 29, 2013 at 20:36
Please help others to help you by posting the more completed code, starting with init — Hai Vu
– Hai Vu, Commented Mar 29, 2013 at 21:06

Raymond Hettinger · Accepted Answer · 2013-03-31 01:02:33Z

5

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

edited Mar 31, 2013 at 1:02

answered Mar 29, 2013 at 20:30

Raymond Hettinger

229k67 gold badges405 silver badges504 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Raymond Hettinger Over a year ago

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.

Blckknght · Accepted Answer · 2013-04-15 04:42:41Z

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

sumedhe · Accepted Answer · 2016-07-12 07:13:53Z

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

Hai Vu · Accepted Answer · 2013-03-29 21:44:36Z

0

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

edited Mar 29, 2013 at 21:44

answered Mar 29, 2013 at 21:15

Hai Vu

41.5k16 gold badges75 silver badges106 bronze badges

Comments

Yannis · Accepted Answer · 2024-09-06 07:03:29Z

0

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

edited Sep 6, 2024 at 7:03

Yannis

1,7198 gold badges30 silver badges51 bronze badges

answered Aug 29, 2024 at 20:52

Daniel Ceballos

1

Collectives™ on Stack Overflow

doubly Linked list iterator python

5 Answers 5

1 Comment

Comments

Comments

Update

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

Comments

Comments

Update

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related