Circular Linked List
I recently managed to finally understand linear linked list. However, now I'm supposed to figure out to make a circular linked list with a dummy node. I am completely lost. I've already written methods for regular linear linked lists like the constructors, insert, and delete, but I have no idea how to go about working with circular linked lists.
Can someone please point me in the right direction by showing a good tutorial or some good sample code? I've tried searching on Google, but I couldn't really find anything.
[537 byte] By [
Lava_Javaa] at [2007-11-26 18:37:20]
> I've tried searching on Google, but I couldn't really
> find anything.
I'd be pretty sure it's been done to death and the whole implementation posted somewhere. But since hardly anyone researches first and just posts yet another question, all the questions (like this one too now) end up muddying up the search hits.
Anyway, I'm not going to spend my time researching it for you, other than to state the obvious that a circular linked list is basically the same as a regular linked list except that the tail node points back to the head instead of to null. If you've supposedly implemented a 'regular' linked list, this should be pretty much a cake-walk.
Linear and circular lists are really very similar. The only difference is that with circular lists, there's no way to tell where the end of the list is. So when you're iterating over the list (for example to find an element to delete), you have to compare the current element against the one you started with, instead of comparing it to the end node, or null (you need to compare against the node you started with so you don't risk looping around the list forever).
Yea, thanks for being nice in your first paragraph. I already searched the forum, and it only turned up 3 threads, none of which were really relevant to what I want.
I understand parts of the circular linked list, but I'd like to see an implementation or more indepth explanation of it so I can fully understand it. At the moment, I'm still pretty lost.
http://www.google.com/search?q=circularly+linked+list
Oh. Then you'll have to Google it probably. But really, if you have a linear linked list implementation already, why bother? There's only that one tiny difference that I mentioned, everything else should be pretty much identical.Edit: oops. Must remember to refresh the page...
sd4139,
so the only difference between linear and circular is when I'm looping through the nodes? Could you or someone else provide a quick code sample?
HEre is what I have for insertion. How would this be used in a circular linked list?
//Insert
public void insert(int newItem, int index)
{
if (index >=1 && index <= numItems+1 && isDuplicates(newItem) == false)
{
if (index == 1)
{
Node newNode = new Node(newItem, head);
head = newNode;
}
else
{
Node prev = find(index-1);
Node newNode = new Node(newItem, prev.getNext());
prev.setNext(newNode);
}
numItems++;
}
}
//Find the node located before the insertion/deletion point
private Node find(int index)
{
int count;
Node curr = head;
//use while loop instead
for (count=1; count < index; count++)
{
curr = curr.getNext();
}
return curr;
}
This is really easy:
http://en.wikipedia.org/wiki/Linked_list#Circularly-linked_list
There's only a very small difference between a regular and circularly linked list. Just point the next element of the tail at the head. When you insert, point the tail's next at the new node, and the node's next at the head.
Ah, well. Indexes also don't really make much sense in a circular list, unless you pick an arbitrary node and call it the header. Actually, they don't make a whole lot of sense in linked lists full stop, when you consider that every time you delete something the index of all the elements after it changes. But oh well.
I don't think you need to change any of that code, really. It should work fine. You'll have to change a couple of other things though. Maybe if you just sat down and drew a few diagrams? They always help when you're dealing with linked lists :-)
