CODEWITHSUNDEEP
pythondoubly-linked-list
user6461923
user6461923

Reputation:

Implementing Iter for doubly-linked list

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

Upvotes: 0

Views: 610

Answers (2)

Prune
Prune

Reputation: 77837

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

Upvotes: 0

ShadowRanger
ShadowRanger

Reputation: 155363

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

Upvotes: 3

Related Questions