Last Updated on April 24, 2023 by Abhishek Sharma
Before starting with the difference between array and linked list let’s first understand what an array is and what a linked list is.
What is an Array?
An array is a famous data structure that is generally used to store data that has the same data types. We can directly access the data stored in an array using the index. There are some methods given below to define an array in various languages.
C++
int array[]={1,2,3,4};Java
int[] array = new int[] {1,2,3,4};Python
array = [1,2,3,4]
In the above picture we can see that array only contains the data and array index starts from 0. We can see that the address is continuous in the array this is one of the important difference between array and linked list.
What is a Linked List?
A Linked List is a collection of nodes that are stored at a continuous memory location. We cannot access the data stored in the linked list directly. Let’s see how to create nodes in various languages.
C++:-
Class Node{
public:
int data;
Node* next;
}Java:-
public class Node{
int data;
Node next;
Node(int data){
this.data=data;
}}Python:-
class Node:
def __init__(self,data=0,next=None):
self.data=data
self.next=next
In the above picture, you can see that node contains two items of data and a pointer. The pointer contains the address of the next node. But in the array there is no concept of a pointer this is one of the major difference between array and linked list. We will see more about array vs linked list in detail.
What are the differences between array and linked list?
Let’s discuss some major difference between array and linked list.
-
We can access the data of an array randomly using the index of an array on the other hand we cannot access the data of a linked list randomly. To access the data in a linked list we need to go through the whole linked list until we found the data we want to access sometimes we find data at the first position, in that case, we don’t need to explore the linked list anymore but when our data is at last position, in that case, we need to go through the whole linked list. This is one of the important topics of array vs linked list.
-
In terms of memory uses linked list uses more memory than an array because an array only stores the data while linked list stores data as well the address of the next node. This is one of the major difference between array and linked list in terms of memory uses.
-
An array is less flexible in size on the other hand linked list is very flexible in terms of size. We need to give the initial size while declaring the array ( ex:- int array[5] ) but in the linked list, we can as much data as we want. An array is less flexible because if we want to add more elements than the size then we have to create a new array having more size and we also need to transfer all the data in the new array so it will cost more memory and be more time consuming than the linked list.
-
Now let’s find the difference between array and linked list in terms of the time cost (time complexity) of the insertion operation.
- Insertion at the start:-
In an array if we want to insert an element at starting position then we have to shift all the elements of the array by one position to the right to make space for the first element so the time complexity to insert an element at the first position in the array is O(n). In the linked list we can insert an element at starting position by just creating a new node and assigning the next pointer to the current head of the linked list we make the head our new node so the time complexity to insert an element at the first position in linked list is O(1). - Insertion at the end:-
We can insert a new element at the end of an array with a time complexity of O(1) because we can directly assign a new element using the index but there is an exception if we want to assign a new element at the end of a whole array then it will take time complexity of O(n) because we need to transfer all the elements to the new array. In the linked list we need to traverse through all linked list to reach the last element that’s why the time complexity to insert a new node at the end of the linked list is O(n). - Insertion at the mid:-
To insert an element at the mid position of an array we need to move all the elements after the mid position to one step right and then we can insert an element at the mid position so the time complexity to insert an element in the middle position is O(n). In the linked list we need to traverse through all the elements before the mid index to reach at mid position thus the time complexity to insert the new element in the linked is at the mid position is O(n).
- Insertion at the start:-
-
In an array, values are not dependent on each other which means we can change all the elements in an array that contains different addresses and it does not contain the address of any other element (only stores data). The linked list node of the linked lists is dependent on each other as the node contains the address of the next node.
Array vs Linked lists
Let’s see some important difference between array and linked list in data structure.
| Array | Linked List |
|---|---|
| An array is collection of elements having same data types. | A Linked list is a collection of nodes that contains data and address. |
| The location of array elements is the continuous | Location of linked list nodes is not continuous. |
| Arrays are based on static memory which means the size of the array is fixed. | Linked lists are based on dynamic memory which means the size of the linked list is dynamic. |
| Memory is allocated during compile time in arrays | Memory is allocated during run-time in a linked list |
| Memory uses is lesser than linked list because an array only contains data. | Memory uses is more than array because linked stores data and address both |
| In an array, Memory is not utilized in an efficient way because if we create an array of size 10 and we only use 5 elements then it will be a waste of memory. | In a linked list, Memory is utilized in an efficient way as we create new node only there is required so no memory will be wasted. |
| Arrays are slower compared to the linked list. It takes more time to perform various operations like insert and delete | Linked lists are faster compared to an array. It takes less time to perform various operations like insert and delete |
| Insertion (Time Complexity):- i.)At the start:- O(n) ii.)At the end:- O(1) iii.)At mid:- O(n) | Insertion (Time Complexity):-i.) At the start:- O(1) ii.) At the end:- O(n) iii.) At mid:- O(n) |
| Deletion (Time Complexity):- i.) At the start:- O(n) ii.) At the end:- O(1) iii.) At mid:- O(n) | Deletion (Time Complexity):- i.) At the start:- O(1) ii.) At the end:- O(n) iii.) At mid:- o(n) |
Topics for further enhancement of your knowledge on the topic: