Linked List

Introduction:

• A linked list is a data structure which contains a list of elements.
• The elements of the list can be placed anywhere in memory and these elements are linked with each other using an explicit link field (ie) by storing the address of the next element. 
• Linked list are used when the quantity of data is not known prior to execution
• Data is stored in the form of nodes and at run time memory is allocated for creating nodes.
• Due to overhead in memory allocation and deallocation the speed of the program is lower.
• Data is accessed using the starting pointer of the list.

Types of Linked List:   

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked LIst

 1. Singly Linked List

• Singly Linked List is normally called as Linked list.
• each node has a data field and a link field.
• data field contains data and the link field contains the address of the next node.
• The last elements link field points to NULL.

Inserting a node in to a singly linked list.
     To insert a new node (say X) after the node (say N),

1. Create the node X (Allocate memory for the new node X, update the node's data field properly and set the link-field for the node to NULL) 
2. Set the link-field of node X to the same as that of node N's link-field 
3. Set the link-field of node N to point to X 

Deleting a specified node in a Singly Linked List:
    To delete a node(say X)

1. Determine the previous node of the node X to be deleted by traversing the linked list 
2. Set the link field of the previous node to the same as the node X's link field 

Problems with Singly Linked List

1. Singly Linked list allows traversal of the list in only one direction.
2. Deleting a node from a list requires keeping track of the previous node (ie) the node whose link points to the node to be deleted.
3. If the link in any node gets corrupted,the remaining nodes of the list become unusable.

The problems of singly linked lists can be overcome by adding one more link to each node, which points to the previous node. This type of linked list is called a Doubly Linked List.


2.Doubly Linked List:

• A Doubly Linked List is a linked list in which every node contain two links, called left link and right link 
• The left link of the node points to the previous node and the right link points to the next node
• The left link of the first node and the right link of the last node will be NULL. 

Application of Doubly Linked List:

1. In memory management, a doubly linked list is used to maintain both the list of allocated blocks and the list of free blocks by the memory manager of the operating system. 
2. A doubly linked list can be traversed in both directions.
3. Having 2 pointers in a doubly linked list provides safety, because even if one of the pointers get corrupted the node still remains linked.
4. Deleting a particular node from a list does not require keeping track of the previous node. 

 3.Circular Linked List:

• A Circular Linked list is a list in which the link field of the last node is made to point to the start/first node of the list.
• In Circular Linked List all nodes are linked in a continuous circle without using NULL.
• Circular Linked List can be either singly or doubly linked list.
• The list can be traversed fully beginning at any given node   

Application of Circular Linked List:

1. Circular linked list are used to represent arrays that are naturally circular.
2. for a pool of buffers that are used and released in FIFO order
3. for a set of processes that should be time-shared in round robin order 
4. Applications that require access to both ends of the list(eg implementation of a queue)

Programs Based on Linked List