Overview of Linked list

Definition of linked list-

A linked list is a collection of dynamically allocated nodes consisting two fields one for storing data and other is for storing the address of it's successor element and each node is connected to it's successor.
Linked list is a non-primitive and a very efficient data structure.


A simple node of linked list-
                     

Data

Reference

Operations which we can perform on linked lists are listed below-
1-Creation of linked list
2-Insertion in front of linked list
3-Insertion in middle of linked list
4-Insertion in the end of linked list
5-Deletion of front node
6-Deletion of random node
7-Deletion of End node
8-Searching of a node

Structure of a node of a linked list is as follows-
       
        struct node{
                int data;          //data of the node
                node* link;    //pointer to the next node
            };

Efficiency of linked list-
Linked list is one of the efficient data structure.It takes O(1) time for insertion and deletion at the begining of the linked list.

Application of linked list- 

There are many applications of linked list.Few are listed below-

• Linked list can be used to implement other data structure like-Stack, Queue, Graph(Adjacency list) etc.
• Hash table is also implemented using linked list as each bucket in hashing is a linked list in itself.
• Linked list is also used to implement sparse matrices.
• The cache in our browser that allows you to hit the BACK button (a linked list of URLs).
• Undo functionality in Photoshop or Word (a linked list of state).
• Applications that have an MRU(most recently used) list (a linked list of file names).
• In Dynamic Memory Management. In allocation and releasing memory at runtime.  
• Symbol table management in compiler design.

Types of linked list-

• Singly or one-way linked list
• Doubly or two-way linked list
• Circuler linked list
• Header linked list