Real World Applications of linked lists

Applications of Doubly linked list can be
- A great way to represent a deck of cards in a game.
- The browser cache which allows you to hit the BACK button (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 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

Comments