Implementing Iter for doubly-linked list

Question

Problem: Being new to python I am currently trying to learn the ropes, getting a better handle on the difference between an array and a linked structure. I've attempted creating a linked list class to assist in getting a better understanding of the language and its structures. What I have written so far:

class LinkedList:
    class Node:
        def __init__(self, val, prior=None, next=None):
            self.val = val
            self.prior = prior
            self.next  = next

    def __init__(self):
        self.head = LinkedList.Node(None) 
        self.head.prior = self.head.next = self.head 
        self.length = 0

    def __str__(self):
        if len(self)==0:
            return '[]'
        else:
            return '[' +  ', '.join(str(x) for x in self) + ']'

    def __repr__(self):
        """Supports REPL inspection. (Same behavior as `str`.)"""
        return str(self)

    def __len__(self):
        """Implements `len(self)`"""
        return self.length

    def __iter__(self):
        """Supports iteration (via `iter(self)`)"""
        cursor = self.head
        while cursor:
            yield cursor.val
            cursor = cursor.next

    def append(self, value):
        n = LinkedList.Node(value, prior=self.head.prior, next=self.head)
        n.prior.next = n.next.prior = n
        self.length += 1

Testing the code below, I'll have a problem where the kernel task won't end, or the debugger will point to line 7 of the test code where it failed. I don't think my __repr__ method is wrong which is why I ask, how could I edit the __iter__ method body to fix this issue? I thought all I had to do was loop through the values in cursor.

from unittest import TestCase
tc = TestCase()

lst = LinkedList()
for d in (10, 20, 30, 40, 50):
    lst.append(d)
tc.assertEqual('[10, 20, 30, 40, 50]', str(lst))
tc.assertEqual('[10, 20, 30, 40, 50]', repr(lst))

You don't show your append method ... consider the possibility that its accidentally creating circles in your structure ... — donkopotamus
– donkopotamus, Commented Jun 13, 2016 at 23:24
When posting code, please make sure what you post is runnable and reproduces the problem you describe when you run it. The code you've posted has no definition of append. — user2357112
– user2357112, Commented Jun 13, 2016 at 23:25
1. I don't see an implementation of append here, which is rather important. 2. Implementing __repr__ in terms of __str__ is strange; typically, you implement __repr__ first, and leave __str__ unimplemented if you don't need separate behavior (__repr__ will be used in place of __str__ if __str__ is not defined). 3. Your __init__ indicates you're using self.head as the indicator for end of iteration, not None or the like; if append follows the same rules, that would explain the problem; you're iterating circularly. — ShadowRanger
– ShadowRanger, Commented Jun 13, 2016 at 23:25
Is your list intended to be circularly linked? Is the initial self.head supposed to be a sentinel node? — user2357112
– user2357112, Commented Jun 13, 2016 at 23:26
My mistake it got cut off, edited. and yes self.head is the sentinel node — user6461923
– user6461923, Commented Jun 13, 2016 at 23:26

ShadowRanger · Accepted Answer · 2016-06-13 23:32:25Z

3

Since you say self.head is the sentinel node, your __iter__ is incorrect; it's testing as if it expects to find a "falsy" value (e.g. None), when being circularly linked, it will never reach such a point. Presumably, you want something like:

def __iter__(self):
    """Supports iteration (via `iter(self)`)"""
    cursor = self.head.next  # Must advance past non-valued head
    # Done when we get back to head
    while cursor is not self.head:
        yield cursor.val
        cursor = cursor.next

edited Jun 13, 2016 at 23:32

answered Jun 13, 2016 at 23:29

ShadowRanger

158k12 gold badges221 silver badges316 bronze badges

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

3 Comments

user2357112 Over a year ago

You're still yielding the sentinel's None value of val. You should probably start at cursor = self.head.next and test while cursor is not self.head.

ShadowRanger Over a year ago

@user2357112: Was already fixing that once I saw the append method which made it clear head shouldn't be part of the iteration. :-)

user6461923 Over a year ago

I tried this implementation but I'm still getting the same error

Prune · Accepted Answer · 2016-06-13 23:49:07Z

You have a circular list. I diagnosed this with the usual high-tech method: the print statement. :-)

I inserted a couple of prints into your str method:

def __str__(self):
    if len(self)==0:
        return '[]'
    else:
        print "NODE VALUE:", self.head.val
        for x in self:
            print "LIST ITEM", x
        return '[' +  ', '.join(str(x) for x in self) + ']'

... and cut back the test a touch:

lst = LinkedList()
for d in (10, 20, 30, 40, 50):
    lst.append(d)
print "str\t", str(lst)

Your method loops through the five expected values and a None header.

LIST ITEM None
LIST ITEM 10
LIST ITEM 20
LIST ITEM 30
LIST ITEM 40
LIST ITEM 50
LIST ITEM None
LIST ITEM 10
LIST ITEM 20
LIST ITEM 30
LIST ITEM 40
LIST ITEM 50
LIST ITEM None
LIST ITEM 10
LIST ITEM 20

Collectives™ on Stack Overflow

Implementing Iter for doubly-linked list

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related