Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why exactly do we need a "Circular Linked List" (singly or doubly) data structure?

Why exactly do we need a "Circular Linked List" (singly or doubly) data structure?

What problem does it solve that is evident with simple Linked Lists (singly or doubly)?

like image 461
user366312 Avatar asked Aug 28 '10 06:08

user366312


People also ask

Which is better singly linked list or doubly linked list or circular linked list?

In case of better implementation, while searching, we prefer a doubly linked list. A singly linked list consumes less memory as compared to the doubly linked list. The doubly linked list consumes more memory as compared to the singly linked list.

Why do we need linked list give a difference between singly and doubly linked list?

Doubly linked list allows element two way traversal. On other hand doubly linked list can be used to implement stacks as well as heaps and binary trees. Singly linked list is preferred when we need to save memory and searching is not required as pointer of single index is stored.

Why do we need doubly linked list?

The most common reason to use a doubly linked list is because it is easier to implement than a singly linked list. While the code for the doubly linked implementation is a little longer than for the singly linked version, it tends to be a bit more “obvious” in its intention, and so easier to implement and debug.


2 Answers

A simple example is keeping track of whose turn it is in a multi-player board game. Put all the players in a circular linked list. After a player takes his turn, advance to the next player in the list. This will cause the program to cycle indefinitely among the players.

To traverse a circular linked list, store a pointer to the first element you see. When you see that element again, you have traversed the entire list.

void traverse(CircularList *c) {   if (is_empty(c)) {     return;   }   CircularList start = c;   do {     operateOnNode(c);     c = c->next;   } while(c != start); } 
like image 195
Andrew Cone Avatar answered Oct 05 '22 23:10

Andrew Cone


Two reasons to use them:

1) Some problem domains are inherently circular.

For example, the squares on a Monopoly board can be represented in a circularly linked list, to map to their inherent structure.

2) Some solutions can be mapped to a circularly linked list for efficiency.

For example, a jitter buffer is a type of buffer that takes numbered packets from a network and places them in order, so that (for example) a video or audio player can play them in order. Packets that are too slow (laggy) are discarded.

This can be represented in a circular buffer, without needing to constantly allocate and deallocate memory, as slots can be re-used once they have been played.

It could be implemented with a linked-list, but there would be constant additions and deletions to the list, rather than replacement to the constants (which are cheaper).

like image 43
Oddthinking Avatar answered Oct 06 '22 01:10

Oddthinking