Linked List is a data structure used for storing collections of data. Linked list has the following properties.
- Successive elements are connected by pointers.
- Last element points to NULL.
- Can grow or shrink in size during execution of a program.
- Can be made just as long as required (until free memory is available).
- It does not waste memory space (but takes extra memory for pointers).
A Linked List can be thought of as an Abstract Data Type (ADT). An Abstract Data Type is a user defined data type and it can be created by the user as per his needs. A Linked List is an ADT, because we are defining a separate type of data structure. In this data structure, we have one storage for our data, and the other one for our next memory location. That means we need to store the location of the next memory address as well.
Basic Structure:
A Linked List can be pictorially represented as:-
The HEAD node is of prime importance as it signifies the starting address of our Linked List. What we have here is an integer as the data, and another storage that points to the next memory location.
Its something like:-
HEAD points at -> 7
The NEXT of HEAD points at -> 15
The NEXT of 15 points at -> 42
The NEXT of 42 points at ->30
The NEXT of 30 points at -> NULL
So, we can conclude that HEAD signifies the start of a link list and NULL signifies that we have reached the end of our Linked List.
Thus, we can define the basic data structure of our Linked List as:
struct node
{
// this is the data type that we want to store
int data;
// a pointer to the next node, same type
struct node * next;
};
Code language: C/AL (cal)That means when we want to go to the next address we can do an operation that is similar to:
list = list->next;
printf("The data element is:- %d", list->data);
Code language: C/AL (cal)Why Linked Lists?
Now, the question arises why should we use Linked List, when there are so many other structures available. One of them is ARRAYS. Both of them are used to store data and serve the same purpose. But there can be some scenarios in which using a Linked List can be beneficial than arrays.
ARRAYS
One memory block is allocated for the entire array to hold the elements of the array. The array elements can be accessed in constant time using the index.
Here we can easily access array elements in constant time. For example if we want to access the 4th element we can simply do it by:
int arr[9] = { 3, 2, 1, 2, 2, 2, 3, 56, 12 };
int elem = arr[3];
printf("The 4th element is:- %d", elem); // prints the 4th element
Code language: C/AL (cal)Advantages of Arrays:-
- Simple and easy to use.
- Faster access to the elements (constant access)
Disadvantages of Arrays:-
- Fixed Size: The size of array is static (we need to specify the array size before using it). Suppose we created an array of 5 elements, and now we need to store 7 elements, its a problem.
- One block allocation: To allocate the array at the beginning itself, sometimes it may not be possible to get the memory for the complete allocation.
- Complex insertions: Suppose we created an array of 10 elements and filled it with 7 elements. Now there is a need to insert a new element at the 3rd position. What to do? We need to shift all the array elements to make space.
Linked Lists:
Thus, we come to the use of Linked Lists. It also has its own advantages and disadvantages.
- The advantage of Linked List is that they can be expanded in constant time. To create an array we must allocate memory for a certain number of elements. To add more elements to the array then we must create a new array and copy the old array to a new array.
- The main disadvantage of linked lists is the access time. It is directly proportional to the number of nodes present in the list. Longer the list, longer it will be for you to access elements. Also sometimes, list are hard to manipulate
Comparison of Linked List and arrays and different types of operations:
| Parameter | Linked List | Array |
| Indexing | O(n) | O(1) |
| Insertion/Deletion at Beginning | O(1) | – |
| Insertion/Deletion at End | O(n) | – |
| Insertion/Deletion in middle | O(n) | – |
| Wasted Space | O(n) | 0 |
Video Explanation:
