Linked List

 Before understanding the linked list concept, we first look at why there is a need for a linked list.

Suppose we want to create an array of integer type like: 

        int x[3]; 

In the above example, we have declared an array of size 3. As we know, that all the values of an array are stored in a continuous manner, so all the three values of an array are stored in a sequential fashion. The total memory space occupied by the array would be 3*4 = 12 bytes.

 

There are two major drawbacks of using array:

• We cannot insert more than 3 elements in the above example because only 3 spaces are allocated for 3 elements.
• In the case of an array, lots of wastage of memory can occur. For example, if we declare an array of 50 size but we insert only 10 elements in an array. So, in this case, the memory space for other 40 elements will get wasted and cannot be used by another variable as this whole space is occupied by an array.

 What is Linked List?

When we want to work with an unknown number of data values, we use a linked list data structure to organize that data. The linked list is a linear data structure that contains a sequence of elements such that each element links to its next element in the sequence. Each element in a linked list is called "Node".

 

A linked list can also be defined as the collection of the nodes in which one node is connected to another node, and node consists of two parts, i.e., one is the data part and the second one is the address part.

 

 

 

Advantages of using a Linked list over Array

 

The following are the advantages of using a linked list over an array:

• Dynamic data structure:
  The size of the linked list is not fixed as it can vary according to our requirements.
• Insertion and Deletion:
  Insertion and deletion in linked list are easier than array as the elements in an array are stored in a consecutive location. In contrast, in the case of a linked list, the elements are stored in a random location. The complexity for insertion and deletion of elements from the beginning is O(1) in the linked list, while in the case of an array, the complexity would be O(n). If we want to insert or delete the element in an array, then we need to shift the elements for creating the space. On the other hand, in the linked list, we do not have to shift the elements. In the linked list, we just need to update the address of the pointer in the node.
• Memory efficient
  Its memory consumption is efficient as the size of the linked list can grow or shrink according to our requirements.
• Implementation
  Both the stacks and queues can be implemented using a linked list.

Disadvantages of Linked list

 

The following are the disadvantages of linked list:

• Memory usage
  The node in a linked list occupies more memory than array as each node occupies two types of variables, i.e., one is a simple variable, and another is a pointer variable that occupies 4 bytes in the memory.
• Traversal
  In a linked list, the traversal is not easy. If we want to access the element in a linked list, we cannot access the element randomly, but in the case of an array, we can randomly access the element by index. For example, if we want to access the 3^rd node, then we need to traverse all the nodes before it. So, the time required to access a particular node is large.
• Reverse traversing
  In a linked list, backtracking or reverse traversing is difficult. In a doubly linked list, it is easier but requires more memory to store the back pointer.