Circular linked list code is getting into infinite loop

Question

I have defined by Circular Linked List like this.

class Link(object):
    def __init__ (self, data, next = None):
        self.data = data
        self.next = next


class CircularList(object):

    def __init__ ( self ):
        self.first = Link(None, None)
        self.first.next = self.first

    def insert_first ( self, item ):
        new_link = Link(item)
        new_link.next = self.first
        self.first = new_link

    def __iter__(self):
        current = self.first
        first = current
        while current.next != first:
            yield current
            current = current.next

    def __str__(self):
        return str([Link.data for Link in self])

    def __repr__(self):
        return self.__str__()

And I insert item to my list

a = CircularList()
a.insert_first(4)
a.insert_first(5)

I want to have a string representation of my circular list, but it looks like __iter__() is looping infinitely. I can I correctly define my iterator, and get a correct string representation?

Answer 1

I'll break the steps down.

First, I rename Link to Node.

class Node(object):
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

Links aren't the same as nodes - nodes are what hold your data, and links connect two nodes together.

Next, the CircularList class, needs some changes.

__init__ will need to initialise an empty list. That means no nodes at all. For the sake of convenience, I define self.last to greatly simplify the code (note, greatly, you will have a harder time of things otherwise).

class CircularList(object):
    def __init__(self):
        self.first = self.last = None

For insert_first, you will need to take care of a corner case when the list is empty, and the general case. Update self.first and self.last accordingly.

def insert_first(self, item):
    if self.first is None:
        self.first = self.last = Node(item)
        self.first.next = self.first
    else:
        self.first = Node(item, self.first)
        self.last.next = self.first

Your __iter__ method should also respond in kind. Comments inlined.

def __iter__(self):
    # corner case - yield empty list
    if not self.first:
        yield []
    else:
        # start by yielding the head node
        yield self.first
        cur = self.first.next
        # iterate as long as you do not see the head node again 
        while cur is not self.first:
            yield cur
            cur = cur.next

The other methods remain the same. Test code:

a = CircularList()
for i in [5, 4, 3, 2, 1]:
    a.insert_first(i)

print(a)
[1, 2, 3, 4, 5]

---

Full Code Listing

class Node(object):
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class CircularList(object):
    def __init__(self):
        self.first = self.last = None

    def insert_first(self, item):
        if self.first is None:
            self.first = self.last = Node(item)
            self.first.next = self.first    
        else:
            self.first = Node(item, self.first)
            self.last.next = self.first

    def __iter__(self):
        if not self.first:
            yield []
        else:
            yield self.first
            cur = self.first.next
            while cur is not self.first:
                yield cur
                cur = cur.next

    def __str__(self):
        return str([Link.data for Link in self])

    def __repr__(self):
        return self.__str__()