When to use a circular linked list?
Author
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?
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.
Ring-buffers or ciruclar arrays are quite common for consumer/producer relationships and pop up from time to time in various fields.
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)?
Author
"In a circular linked list the first and final nodes are linked together."
That is what I mean.
That is what I mean.
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.
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
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
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
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
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
