Applications of circular and doubly link list

Circular linked list

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.

Circular linked list should be used is a timesharing problem solved by the operating system. The OS will pick a user; let it use a small amount of CPU time and then move on to the next user, etc.

Circular linked list is the basic idea of round robin scheduling algorithm.

A circularly linked list may be a natural option to represent arrays that are naturally circular, e.g. the corners of a polygon.

With a circular list, a pointer to the last node gives easy access also to the first node, by following one link. Thus, in applications that require access to both ends of the list (e.g., in the implementation of a queue), a circular structure allows one to handle the structure by a single pointer, instead of two.

A circular list can be split into two circular lists, in constant time, by giving the addresses of the last node of each piece.

Applications of doubly linked

The browser cache which allows you to hit the BACK buttons (a linked list of URLs).

Applications that have a Most Recently Used (MRU) list (a linked list of file names).

A stack, hash table, and binary tree can be implemented using a doubly linked list. 

Undo functionality in Photoshop or Word (a linked list of state).

A great way to represent a deck of cards in a game.

	Singly	Doubly	Circular
Concept	One way direction	Two way direction	One way direction in a circle
Has head	Yes	Yes	No-because tail will refer to first node
Has tail	Yes	Yes	Yes
No of Node	1-next node	2-next node & previous node	1-next node
insert()	O(n)	O(1)	O(n)
delete()	O(n)	O(1)	O(1)
Benefit	require small space for each element	allow to traverse the list in both directions	execute to the end can be quickly.