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.
Array
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.
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.no | Array | Linked List |
|---|---|---|
| 1 | An 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. |
| 2 | Array 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. |
| 3 | Array is static. Its size is fixed. | Linked List is dynamic. Its size can easily grow and shrink. |
| 4 | Array 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. |
| 5 | Each 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. |
| 6 | We can perform a Binary Search search on an array. | We cannot perform Binary Search on Linked List. |
| 7 | Insertion/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. |
| 8 | Updation is performed in O(1). | Updation is performed in O(N). |
| 9 | Array occupies memory even if no data is inserted. | Linked List is memory efficient. It occupies memory only when data is inserted. |
| 10 | Memory is assigned to arrays at Compile Time. | Memory is assigned to Linked List at Runtime. |
| 11 | Array 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. |
| 12 | The address of the first element of the array is called the Base Address. | The first node of Linked List is called it’s head. |
Comparison
| Property | Array | Linked List |
|---|---|---|
| Memory Utilization | Inefficient | Efficient |
| Searching | Linear Search, Binary Search | Only Linear Search |
| Random Access | Yes | No |
| Contiguous Memory | Yes | No |
| Cache Utilization | High | Low |
| Updation | O(1) | O(N) |
| Deletion/Insertion | O(N) | O(N) |
| Memory Use | Low | High |
| Memory Allocation | Static (Compile-time) | Dynamic (Runtime) |
| Size | Fixed-size | It can easily Grow/Shrink depending upon the number of nodes. |
References
https://en.wikipedia.org/wiki/Linked_list
https://en.wikipedia.org/wiki/Array_data_structure
What to study next?
Leave Comment if you face any problem.