Linked List Data Structure
Linked List Data Structure is a part of Learning Data Structure Series. In the last articles of Array Data Structure, we learnt Types of Array, Inserting & Deleting Elements from Array, Searching elements in Array, Sorting the Array. In this we will learn Linked List Data Structure.
Let us start with the word List. List refers to the linear collection of elements. Such collection of elements may require data processing like storing, inserting, deleting, searching, sorting. So we can use array for this. But array has certain disadvantages like
1) Inserting and deleting operation on array is comparatively expensive.
2) Array usually occupies block of memory space. So increase in memory whenever required is not possible.
Another way of storing such linear data efficiently is using Linked list. Linked list is a linear collection of data elements in which link is maintained by using pointer. So we can say linked list is collection of nodes. Each node is divided into two fields.
1) Information Field
2) Link or Pointer Field
Information field contains the element and link field contain the address of next element in the list. So next element need not to have adjacent space in memory. This makes insert and delete operation easier and efficient than array. Also we can increase number of nodes as and when required.
Types of Linked List
There are three types of linked list
1) Single Linked List
2) Circular Linked List
3) Two- Way Linked List
Single Linked List
Single linked list is a basic type of linked list. In this node is divided into two parts to hold value as well as pointer to next element. The address of first node is hold by special pointer called START. And the last node of linked list contains null address. This null address indicates that last node does not point to any other node. The linked list looks like
Circular Linked List
Circular linked list is modified version of single linked list. In single linked list, last node contains null pointer in the address field but in case of circular linked list last node hold the address of first node. So all the pointers contains valid addresses
Two-Way Linked List
In single linked list and circular linked, we can traverse in forward direction. In Two way linked list we can traverse the list in both direction forward as well as backward. The two way linked list needs two pointer to do so.