Help with Circular Linked List in Python

Question

I'm trying to make a circular singly linked list. I'd like to be able to modify my code for a singly liked list but I'm have some trouble.

For my linked list I have:

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


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

  def __str__(self):
    a = "["
    current = self.first
    while current != None:
      a += str(current.data) + ', ' 
      current = current.next
    a = a[:-2] + ']'  
    return a  

  def __iter__(self):
    current = self.first
    a = []
    while current != None:
      a += [current.data]
      current = current.next
    return iter(a)

  def __len__ (self):
    current = self.first
    a = []
    while current != None:
      a += [current.data]
      current = current.next
    return len(a)

  def InsertFirst(self, item):
    NewLink = Link(item, self.first)
    self.first = NewLink

  def InsertLast(self, item):
    NewLink = Link(item)
    current = self.first

    if current == None:
      self.first = NewLink  
      return 

    while current.next != None:
      current = current.next
    current.next = NewLink 

  def Search(self, item):
    count = 0
    current = self.first
    while current != None:
      count += 1
      if current.data == item:
        return count
      else:
        pass
        current = current.next
    return -1

  def Delete(self, item):
    current = self.first
    previous = self.first

    if (current == None):
      return None

    while (current.data != item):
      if (current.next == None):
        return None
      else:
        previous = current
        current = current.next

    if (current == self.first):
      self.first = self.first.next
    else:
      previous.next = current.next

    return current

So far for my circular list I have:

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.head = Link(None, self.first)

  def __str__(self):
    a = "["
    current = self.first
    while current != None:
      a += str(current.data) + ', ' 
      current = current.next
    a = a[:-2] + ']'  
    return a  

  def InsertLast(self, item):
    NewLink = Link(item)
    current = self.first

    if current == None:
      self.first = NewLink  
      return 

    while current.next != None:
      current = current.next
    current.next = Link(item)

My question is how do I link the last element back to the first so I can transverse?

Answer 1

The point of a circular linked list is to skip all of the "if next is not None" logic. At the beginning, the head points to itself, indicating that the list is empty. There is no need to create an empty "first" - at the very start do:

self.head = Link(None, None)
self.head.next = self.head

Then to insert a node after some other node, you just do:

def insert_after(insert_node, after_node):
    insert_node.next = after_node.next
    after_node.next = insert_node

To insert at the beginning of the list, do:

insert_after(node, head)

Insert before requires iterating to find the "before" node, since the list is only singly linked:

def insert_before(node, before_node):
    loc = head
    while loc.next is not before_node:
        loc = loc.next
    insert_after(insert_node, loc)

To insert at the end of the list, do:

insert_before(node, head)

To get all elements of the list do:

current = self.head.next
while current is not self.head:
    # do something with current.data

    # advance to next element
    current = current.next

But the real power in a circular list is to make it doubly linked, so you can insert before without iterating.