Wednesday, 5 August 2015

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.

One way direction
Two way direction
One way direction in a circle
Has head
No-because tail will refer to first node
Has tail
No of Node
1-next node
2-next node & previous node
1-next node
require small space for each element
allow to traverse the list in both directions
execute to the end can be quickly.

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...