What are the differences between arrays and linked lists?
Arrays and Linked Lists are two of the most popular linear data structures. Let’s look at some of their major differences:
Arrays
Linked Lists
1. Memory allocation
Array
The entire array is stored in a contiguous block of memory.
Linked list
Different elements are stored at different memory locations.
2. Size
Array
The size of an array is specified at the time of declaration and cannot be changed afterward.
Linked list
Data items can be added or removed from the linked list whenever desired.
3. Space utilization
Array
Due to contiguous allocation, an array can only be stored where there is a large block of free space is available.
Linked list
Different elements are stored at different locations; hence, linked lists can be made within small chunks of free space.
4. Space consumption
Array
Space consumption is overall less.
Linked list
Space is required to store pointers next to nodes.
5. Accessing elements
Array
Any element can be directly indexed in worst-case time.
Linked list
The list needs to be traversed from the first element up to the required element, taking worst-case time.
6. Search options
Array
Linear search and Binary search (if sorted).
Linked list
Linear search only.
