CODEWITHSUNDEEP
pythoncircular-list
frank lowe
frank lowe

Reputation: 29

using circular link list insert function

This is my code and every time I call the insert function I am getting an ouput of: <__main__.CircularList object at 0x10597fd68>. I am trying to use the insert function to actually create the circular linked list by calling it with a for loop.

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

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

  # Insert an element in the list
  def insert ( 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
    newLink.next = self.first

Upvotes: 1

Views: 1667

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476699

Your implementation is first of all wrong. In case you take the if loop, you should set the .next value evidently to itself, otherwise there wouldn't be a circle:

if (current == None):
    self.first = newLink
    newLink.next = newLink
    return

But next there is an important problem: by iterating over a circular list, you never will end iterating, because evidently you will do another round from the moment you returned.

So you first need to make up your mind where you wish to insert the item? As the first item? Or the last item to reach in case of iteration?

In case you want to select the last one, you first must store the first item in memory:

first = current

(You can also of course use self.first) but this will probably be a bit less efficient.)

Next you iterate over the list of items, and each time you check whether the next of the current is the first: in that case we've iterated over an entire round, so:

while (current.next != first):
    current = current.next

Now in case current.next is pointing to the first, we know we've made a complete tour. Now we only need to perform some pointer bookkeeping:

current.next = newLink
newLine.next = first

So the full code reads:

def insert ( self, item ):
    newLink = Link (item)
    current = self.first

    if (current == None):
        self.first = newLink
        newLink.next = newLink
        return

    first = current
    while (current.next != first):
        current = current.next

    current.next = newLink
    newLink.next = first

Upvotes: 2

Related Questions