By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,403 Members | 1,089 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,403 IT Pros & Developers. It's quick & easy.

Python circular linked list

P: 1
Good afternoon all!

I have this program in Python that is really starting to make my head go crazy. It utilizes linked lists (circularly linked list).

Now, correct me if I am wrong, but a circular linked list works like this: (the number on the left represents the number of lists)
o - (Header is empty class)

1 - header.next = first element (call this EL1)
EL1.next = EL1

2 - header.next = first element (call this EL1)
EL1.next = second element (call this EL2)
EL2.next = EL1

3 - header.next = first element (call this EL1)
EL1.next = third element (call this EL3)
EL3.next = second element (call this EL2)
EL2.next = EL1

I believe that is the right definition of circular list.
Note that the header will have the next element and also the size of the array.

Currently, I am having some problems and I will show you the code and the results.

Let me define some classes and functions, first.

class list:
holds the objects header and size
initially sets the header to empty node
initially sets size to 0

class emptynode:
holds no objects, it is empty

class node:
holds the value of the element
holds the next object

A function I created was:
Expand|Select|Wrap|Line Numbers
  1. def addin(data, list):
  2.     new = Node(data, EmptyNode())
  3.     list.size += 1
  4.  
  5.     if isinstance(list.head, EmptyNode):
  6.         list.head = newNode
  7.  
  8.     elif isinstance(list.head, Node):
  9.         temporary = list.head.next
  10.         new.next = temporary
  11.         list.head.next = new
Where it takes a value and adds it to the circular list by definition seen earlier.

Works wonderfully, EXCEPT, say we have the following commands:
Expand|Select|Wrap|Line Numbers
  1. l = list()
  2. addin('A', l)
  3. addin('B', l)
  4. addin('C', l)
We get the following memory allocations returned:

Expand|Select|Wrap|Line Numbers
  1. ('0', 'A', <__main__.Node object at 0x022953D0>, <__main__.Node object at 0x02295430>)
  2.  
  3. ('1', 'C', <__main__.Node object at 0x02295430>, <__main__.Node object at 0x02295410>)
  4.  
  5. ('2', 'B', <__main__.Node object at 0x02295410>, <__main__.EmptyNode object at 0x004614C8>)
  6.  
The first memory allocation represents the current element. For instance, <__main__.Node object at 0x022953D0> is the memory allocation of A element. The second memory allocation represents the next element. So you see <__main__.Node object at 0x02295430> is the same as C (because C is the next node of A).

All works great until we get to the last element (in this case B). B points to the original header (before any adding was done). Now, B's next should point to the memory allocation of A... but it does not.

Can someone please help me with this algorithm

Thank you in advance!!
Dec 3 '10 #1
Share this question for a faster answer!
Share on Google+

Post your reply

Sign in to post your reply or Sign up for a free account.