Difference between Array and Linked List

Array and Linked List are Linear Data structures. The main difference between array and the linked list is that array occupies contiguous memory whereas linked list memory is scattered.

Contiguous memory of array makes random access possible. We can access any element directly by its index.

Scattered memory of Linked List does not support random access. To access a node, we must read all nodes from the start.


An array is a collection of elements of same datatype.

Array occupies contiguous memory.

It means that the data is stored on consequent memory locations.

The order in which data is stored is same as their order in array.

The address of first element of array is known as the Base Address.

difference between array and linked list

Linked List

Linked List is a linear data structure.

Linked List does not occupy contiguous memory. The nodes are randomly distributed in physical memory. Each node stores a pointer to the next node.

Each node in the Linked List consists of 2 fields.

One field stores the data and the other field stores the address of the next node.

The pointer to the first node of Linked List is knows as it’s head.

Difference between Array and Linked List

S.noArrayLinked List
1An array is a collection of elements of a similar data type.Linked List is a linear collection of nodes. Each node stores data and address to the next node.
2Array occupies contiguous memory. It means that the data is stored on consequent memory locations in physical memory.Linked List has scattered memory. The nodes are stored in random order in physical memory.
3Array is static. Its size is fixed.Linked List is dynamic. Its size can easily grow and shrink.
4Array supports random access. This means we can access any element of the array directly by its index.
Random access is possible because the data is stored continuously. Thus, we can calculate the physical address of any element using the index.
Linked List support sequential access. It means to access any random node in Linked List, we must sequentially read nodes from start.
This happens because the nodes are distributed randomly in physical memory. We cannot calculate the address of nodes, unlike arrays.
5Each index of the array only stores the data. No extra information is stored.Each node of Linked List stores data as well as the address of the next node. Thus, Linked List occupies more memory than an array.
6We can perform a Binary Search search on an array.We cannot perform Binary Search on Linked List.
7Insertion/Deletion of data from array maybe requires reorganization of all the elements of the array.
For example, if we delete the ith element of the array, we must shift all elements after the ith index by one.
Insertion/Deletion is simple. It doesn’t involve any movement or reorganization of nodes.
8Updation is performed in O(1).Updation is performed in O(N).
9Array occupies memory even if no data is inserted.Linked List is memory efficient. It occupies memory only when data is inserted.
10Memory is assigned to arrays at Compile Time.Memory is assigned to Linked List at Runtime.
11Array has better Cache Locality. This happens due to Spatial Locality. Spatial locality means that if the ith memory location is accessed then there’s is a high chance that (i+1)th memory location will be accessed. Several contiguous memory locations are loaded to the cache which results in faster access to data.Linked List has a weak cache locality. This is because data is scattered in memory. It means that there is a higer chance data may not be in cache. This leads to more main memeory access.
12The address of the first element of the array is called the Base Address.The first node of Linked List is called it’s head.


PropertyArrayLinked List
Memory UtilizationInefficientEfficient
SearchingLinear Search, Binary SearchOnly Linear Search
Random AccessYesNo
Contiguous MemoryYesNo
Cache Utilization HighLow
Memory UseLowHigh
Memory AllocationStatic (Compile-time)Dynamic (Runtime)
SizeFixed-sizeIt can easily Grow/Shrink depending upon the number of nodes.



What to study next?

  1. Difference between Stack and Queue

Leave Comment if you face any problem.

Leave a Comment

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