Computer Fundamentals

Difference between Linked List and Array

The difference between the linked list and array can be explained in four factors. These factors are as follows: –

  • Memory Representation
  • Insertions
  • Deletions
  • Searching

Memory Representation

A Linked List data structure is different with respect to memory representation as compared to Arrays. In an array, all the elements of an array are stored contiguously (consecutively, in a group) in the memory. This is a feature of the array. Compilers only need the base address (memory address of the first element) of the array. The rest of the addresses (of the rest of the elements) are calculated simply by incrementing the base address. In the case of a linked list, the elements of a linked list are stored randomly and non-contiguously in the memory. This architecture has been shown in the following figure:-

Difference between Linked List and Array
Difference between Linked List and Array

The figure above is a conceptual diagram just for learning the difference between the linked list and array data structures. The actual memory addresses and number of bytes occupied by each of the elements of the array and linked list will be quite different. However, here we just want to show the difference in terms of the type of the storage of elements of both data structures in the memory.

In a linked list, we can perform the traversing operation by means of the pointer field of every node. As the figure above (b), shows that the first node is found at memory address 368, as indicated by the start variable. The data at the address no. 368 is 5 and the pointer field points to 364 for visiting the next node. The node at address 364 contains the value 64 and next node pointer 372. The process goes on, as the list ends on address no. 366, where the data is 25 and the next pointer field is null.

Insertion

Different data structures cost differently for different data structure operations, in terms of time and space. The linked lists are found to be very efficient in terms of insertions and deletions than the arrays. In arrays, as shown in the figure below, if we want to insert a new element at some location loc, then first we have to move all the elements having location loc>=1 to one index higher. It means that we have to move index no. 4 element, to index no. 5, index no. 3 element, to index no. 4 and so on. In the figure below, there are five elements in the array before insertion. We want to insert a new item 40 at loc 1. For this, first have to move the 4th element to the 5th index, 3rd to 4th, 2nd to 3rd and 1st to 2nd. When we get free space at index no. 1, then we place our new item at the desired location.

Insertion in Array
Insertion in Array

This process can be very costly, as we have to move a lot of elements in the forward location, to create a space for the new element. On the other hand, if we see the insertion process in the linked list data structure, we can see that here we have to change the pointers only.

Insertion in Linked List
Insertion in Linked List

As in the figure above, we can see that we need to insert a new node D as the first node of the list. For this, we changed only two pointers. First, we changed the next pointer field of node D to node A and then we changed the start pointer to point to node D. For simplicity, we are discussing only Singly Linked Lists. In terms of running time, we can insert a new node in a linked list in just O(1) (constant) time.

Deletion

As far as the deletion process is concerned, let us discuss an example shown in the figure below. Here, in the figure below (a), we can see the state of the linked list before deleting the element with loc=1. To delete the element 64 at loc 1, we need to move all the elements who have loc > 1 to one index lower. In this case, we have to move index no. 2 to 1, 3 to 2 and 4 to 3. It can also be a very costly process if the array consists of a large number of elements. Whereas in case of a linked list, as we can see in the figure below (Deletion in Linked List), we only have to change the pointer of the preceding node. In the linked list, we don’t need to shuffle the elements around. Therefore, this process takes only O(1) (constant) running time and it is very efficient as compared to that of the Arrays.

Deletion in Arrays
Deletion in Arrays

 

Deletion in Linked List
Deletion in Linked List

Searching

The insertion and deletion processes are very costly in arrays. However, arrays are very efficient in the case of searching for an element in it. Searching can be of two types. The first one is Linear Search and the second one is Binary Search.

Binary Search is very efficient than the Linear Search. However, Binary Search has two limitations. First it applies only on the sorted arrays, second, it needs access to the first and the last index of the list. We know that array elements are stored on an index basis. Therefore, we can apply both linear search and binary search on arrays. However, linked lists are not index based. Therefore, the binary search is inapplicable to the linked list. Therefore, it is not very efficient in searching as compared to the arrays.

Leave a Reply

Your email address will not be published. Required fields are marked *