Linear linked list is a sequential data structure where each element contains the address of its next element by storing it in a pointer within element.
Why we need Linear Linked List when we have Array?
Array data structure is easy to create and manipulate. But, there are certain limitations with Array to store elements
- Insertion in array needs all elements after the position of insertion to move one place backwards .
- Deletion in array requires all elements to move one place forward after the deleted element to fill the hole thus created.
- Array size once defined cannot be increased or decreased ( In theory, but implementation may be programming language specific)
- Array elements must be stored in contiguous memory locations.
Linear Linked list overcomes the Array problems
- Insertion does not require movement of the elements after the position of insertion.
- Deletion needs no forward movement of all elements after the deleted element.
- Linked list size is limited only by the memory available. It is a dynamic data structure.
- Linked list elements need not be stored in contiguous memory locations.
Node of a Linear Linked List element
An element in a linear linked list is called a node. It consists of two parts- data and link (pointer). The data part contains the data that the element is supposed to hold for the program implementation. The Link or the pointer contains the address of next element.
Linear Linked List Example
Let’s assume that you are creating a program to store roll numbers and marks of students enrolled in a class. To do this with a linked list, you will create linked list with this node
The required data is stored in this way.
In this example each node has data part divided into Roll No. and Marks. The link part of each node contains the address of next node as indicated by a pointer in the image. The ‘X’ (defined an NULL or no value) in the last node indicates the end of the linked list.
Each Linked list is identified by a special pointer called ‘Start’. It stores the address of the first node of the linked list. Every operation that involves traversing through the linked list starts from ’Start’ Pointer. The link part is used to follow the next node. You can understand it like a treasure hunt. Each clue that is given to you will in turn give you the location of the next clue. By following the clues you can reach the treasure. In linked list by following the link part of the nodes you can reach to the end of the linked list.
We have already discussed the benefit of linear liked list. There are some limitations too.
- Linear linked list is a sequential data structure. You need to follow the links to reach a specific node.
- The process of reaching to the next node from the address given in current node may slightly delay the operations.
- If link part of any node gets damaged the linked list will not be accessed.