1

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
Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
frank lowe
  • 19
  • 2
  • 7

1 Answers1

2

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
Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555
  • The output is still coming out at <__main__.CircularList object at 0x10592dd68>. I'm calling it in the main function like this: Clist = CircularList() for i in range(1,int(num)): Clist.insert(i) – frank lowe Apr 05 '15 at 23:24
  • @franklowe: evidently, you didn't override the print function and the instance of `CircularList` remains the same, regardless of how you modify it. You should ask how to **print** the list, not how to **insert an item** if that's the objective. – Willem Van Onsem Apr 05 '15 at 23:25
  • I am given different values for num that I read in and am supposed to make the circularlist that length of nodes. – frank lowe Apr 05 '15 at 23:29
  • @franklowe: well you can wrap this in a `for` loop. In order to print an object properly (so no `<__main__...>`), you should override [these methods](http://stackoverflow.com/a/1535375/67579). – Willem Van Onsem Apr 05 '15 at 23:31