A linked list is a data structure in which data is stored in structures called nodes and every node has a pointer to the next node in the list. A linked list can be visualised as a chain of nodes. A pointer usually termed as head points to the first node in the chain or list and using this head pointer, we traverse the entire list. Unlike arrays, linked List doesn’t support random data access but insertion or deletion of data elements is very efficient. It just involves some pointer manipulation. We can recall that insertion or deletion of elements in arrays involve costly shifting operations which is very inefficient if the size of the array is very large. A node is dynamically created and inserted into the list when a new data element has to be created and it is deleted when an element has to be removed.
Types of Linked List
There are three different types of linked lists which are described below :
Single Linked List consists of nodes where each node contains a data element and a pointer which points to the next element in the list.
Double Linked List consists of nodes where each node contains a data element and a two pointers pointing to the previous and next element in the list.
Circular Linked List is a simple list in which last node points to the first node in the list.
Following diagram visualizes single and double linked lists :
We can optionally use a tail pointer which points to the last node of the list but it doesn’t have real world use cases. Next, we would see some problems on linked list.