Sign in to follow this  
GDKnight

When to use a circular linked list?

Recommended Posts

I was just wondering if some people could give me some examples of when they have used a circular linked list. The only area I can think of is perhaps for bullets in a game but I am not fully sure might almost be better to just use a vector or an array in that case. Can anyone give me an example?

Share this post


Link to post
Share on other sites
Um, they're elegant. But that's about the only real thing I can see a circular linked list being good for.


Ring-buffers or ciruclar arrays are quite common for consumer/producer relationships and pop up from time to time in various fields.

Share this post


Link to post
Share on other sites
Do you mean a circular linked list instead of a "normal" linked list, or a linked list instead of some other data structure? Or do you mean a ring buffer (which is a queue)?

Share this post


Link to post
Share on other sites
Quote:
Original post by GDKnight
"In a circular linked list the first and final nodes are linked together."

That is what I mean.


Well basicly they're convinent if you want to loop through all elements starting at a random position. Not a very common requirement.

But also they're neat in that their implmenetation can become very neat, it actually makes sense to use them even when doing a plain old boring list you simply hide the "first" node internally and thus get rid of some special cases during insertion and deletion.

Share this post


Link to post
Share on other sites
I've used circular lists in the past, and they're can be very convenient especially for node reuse. One is if you need to set up a ring-buffer that is not in an array, for whatever reason.

One example is if you have some sort of customized output display in your game (like a console), that only displays a maximum of say, 100 lines. Let's also say that each "line" in the output could be text, graphical objects, sounds, etc. Iow, complex structures. This then removes the obvious solution of simply having a "char szTextBuffer[100][1024]" buffer :)

When you reach the end of your "line buffer" you need to dump the first "line", to make space for the next. Well, one thing you could do is pre-create a circular linked list that would contain the lines. When you add lines, it's simply modifying the tail node's "next node's" data in the list (no need to fix the "next" pointer, since it's circular it's done already). If the "next" pointer points to the current head of the list, simply progress the "head" one node down, and make the new tail point to different complex data.

That way you don't ever have to deal with strange memory copies and buffer checks and whatnot. Since it's circular the only case you have to look out for is when the current tail's next node is the head.

At least that's one example I think of :) A little contrived, and I hope it made sense, but I hope it illustrated a practical use =)

Graf

Share this post


Link to post
Share on other sites
Once I was making a class that was actually a very specialized hash table

Well the hash table has a rather small array and each index you pass to it (could be a string or an int) is converted to a number between the range of that array.

The array is supposed to be a linked list where the real index - entry is and you have to iterate through it till finding the index's entry.

But what I found out is that in my implementation, and most likelly there are many possibilities that the same index will be accessed 2 consecutive times.

So using a circular linked list and saving the pointer of the last accessed entry on each of the array's indexes improved performance a bit for tables with a small quantity of entries but quite a lot for hash tables that had a lot of entries

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by GDKnight
What exactly is a ring buffer? No defintion on wikipedia...


A ring buffer is a kind of queue.

You use circular lists in queueing situations and scheduling. The best example I could give, would be in a low level sound driver. You would have a circular list (or array) for reading and writing samples to the sound card in real-time.

Share this post


Link to post
Share on other sites
An OS's memory manager may use a circular list, search for 'clock algorithm'.
http://www.cs.utah.edu/classes/cs5460-regehr/lecs/page_replace1-4up.pdf
http://www.cs.wisc.edu/~remzi/Classes/537/Fall2005/Lectures/lecture16.pdf

If you put a dummy element into your circular list, insert/remove operations become very easy, since the list always contains an element (no check for null).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this