  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Difference between Array and Linked List

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 ) 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.

1. 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).
2. 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).
3. 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).
• 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.

Let’s see some important difference between array and linked list in data structure.