Circular linked list

[girlzone]

Hello all,
I have a question:
What are the advantages & disadvantages of the circular linked list compared with:
a. Usual linked list
b. Doubled linked list
Although the implementation of the usual list functions & the circular list functions are similar…when do we have to use it?? or in which situations the circular list is better than the usual list? :rolleyes:

Thank you,
;)

[jwenting]

sounds like a homework assignment as you can find the answers in any good textbook dealing with the subject.

[ManojGupta91]

Hello all, I have a question: What are the advantages & disadvantages of the circular linked list compared with: a. Usual linked list b. Doubled linked list Although the implementation of the usual list functions & the circular list functions are similar…when do we have to use it?? or in which situations the circular list is better than the usual list? :rolleyes:

Thank you, ;)

Hi..........

Suppose the case of non circular link list. If u r at the last node of the list and u want to move to first u need to go one - one step back till u reach to first. But in circular link list from last to first u need to make only one move.

In single link list u can move only in one direction but in double link list u can move in any direction, i.e. back or forward.

Single list contain refrence to it next node but not for its backward node. But in Double link list it contain refrences for its next node as well as for its backward node.

Single list can be circular and non circular both.
Same with double link list. It can be both circular or non circular.

[babitagoyal]

Hello all, I have a question: What are the advantages & disadvantages of the circular linked list compared with: a. Usual linked list b. Doubled linked list Although the implementation of the usual list functions & the circular list functions are similar…when do we have to use it?? or in which situations the circular list is better than the usual list? :rolleyes: Thank you, ;)

hi
circular list has the biggest advantage of time saving ie when we hav e to go from last node to first node. it doesnot go back to all the inbetween nodes again rather it is the next node that is the first node.
thanks

[Amitprajapati4]

Single linked list is one directional only, So to go back in normal single linked list it becomes hard and time consuming where as in circular linked list from last node to first node it requires only one stepso faster than normal single linked list.

[Martin B]

I'm going to answer this thread, even though it is rather old, because it comes very high in the Google search results for "circular linked list", and there hasn't been a comprehensive answer.

Firstly, it isn't pertinent to compare a circular list to a singly- or doubly-linked list individually; circular lists can be singly- or doubly-linked too, and are more useful when doubly-linked for the same reasons as linear lists:

1. Double linkage allows you to traverse forwards or backwards
2. You can insert or remove a node without needing the predecessor
3. You can remove the last node without needing to walk through the list to the end to find its predecessor

Having cleared that up, what are the advantages of circular lists over linear ones?

The main advantage is simplicity of implementation. Because a circular list does not have NULL pointers at its ends, you don't need to check whether pointers are NULL.
A node always has a non-NULL predecessor and successor, and this means that you can always safely dereference its previous and next pointers.

A consequence of this is that you can implement add-head, add-tail, add-before and add-after through a single function. Similarly, you can implement remove-head, remove-tail, remove-before and remove-after through a single function.

I've implemented both linear and circular lists, and you can see the source code here:

Linear doubly-linked list
Circular doubly-linked list

If you look at the two implementations side-by-side, you will notice how the circular implemention is simpler.

The main disadvantage of a circular linked list is that iteration is less straightforward than in a linear list. For example, in a linear list you would traverse from head to tail like this:

for (node = list->head; node != NULL; node = node->next) {
}

In a circular list however, the head is the tail, so the termination condition of the loop is already true. This means that you need to use a do loop:

node = list->head;
do {
node = node->next;
} while (node != list->head);

I have written more about circular lists here: Circular linked list