Define Linked List
Linked List is a dynamic Data Structure. It is a sequence of data structures, which are connected together via Nodes. A node is basically a collection of two sub-elements . A data part that stores the element and a next part that stores the link or the address to the next node. A linked list is formed when many such nodes are linked together to form a chain. This nodes are stored randomly in the memory. All of the nodes (except the last node) in the linked list points towards the other node while the last node of the list contains pointer to the null.
Advantage of using linked list
Linked list is a dynamic data structure so it can expand and shrink in the runtime by allocate and deallocate the memory.
As mentioned in the first point we can remove the memory which is not in use and no memory is wasted.
Insertion and Deletion are efficient compared to Arrays as no shifting of elements is required in the LinkedList. Here we only need to update the required pointer.
It is very useful in implementing data structure like stack and queue.
Disadvantage of using linked list
In a Linked List more memory is required in the linked list as compared to an array. Because in a linked list a pointer is also required to store the address of the next element and it requires extra memory for itself.
Reversal of linked list is not possible in single linked list.
We cannot access element directly in a linked list. If we want to access the element then we need to traverse till that element.
Types of Linked List
There are 5 types of linked list :-
Singly Linked List
Doubly Linked List
Circular Linked List
Doubly Circular Linked List
Header Linked List .
Singly Linked List:- It is the simplest type of linked list in which every node contains some data and a pointer to the next node of the same data type. The node contains a pointer to the next node means that the node stores the address of the next node in the sequence. A single linked list allows the traversal of data only in one way.
Doubly Linked List:- A doubly linked list or a two-way linked list that contains a pointer to the next node as well as the previous node in sequence. Therefore, it contains three parts of data, a pointer to the next node, and a pointer to the previous node. This would enable us to traverse the list in the backward direction as well.
Circular Linked List:-A circular linked list is a type of linked list in which the last node contains the pointer to the first node of the list. While traversing a circular linked list, we can begin at any node and traverse the list in any direction forward and backward until we reach the same node we started. Thus, a circular linked list has no beginning and no end
Doubly Circular Linked List:-A Doubly Circular linked list or a circular two-way linked list is a more complex type of linked list that contains a pointer to the next as well as the previous node in the sequence. The circular doubly linked list does not contain null in the previous field of the first node.
Header Linked List:-A header linked list is a special type of linked list that contains a header node at the beginning of the list. So in a header linked list Start will not point to the first node of the list but Start will contain the address of the header node.