Both Array and Linked List are used to store the data having a similar type, but the difference is that array takes memory locations in contiguous fashion at compile-time, i.e. when we declare of an array, while elements of the linked list take memory, not in contiguous fashion and takes memory at runtime.
Array VS Linked List
- An array is a data structure that contains elements of similar data type elements. Whereas the Linked list is a data structure that contains a collection of unordered linked elements known as nodes.
- In an array, we can perform random access of the element, but in a linked list we cannot perform the random access, we have to do it sequentially.
- In an array, each element has an index number, So that we can access any element by its index number. But in a linked list all elements are connected sequentially, so we have to traverse each element until we find a similar match.
- Element access in an array is fast, but in a Linked list, it takes more time, so it is a little bit slower.
- Operations like insertion and deletion of an element in arrays take more time as compared to the Linked lists. We can perform this operation in a linked list faster.
- The size of an array is fixed, and we cannot increase it at runtime, but the size of the linked list is dynamic we can expand it at runtime as per requirement.
- In an array, memory is assigned during the compile time so that size of an array is fixed during the execution of the program while in a Linked list memory is allocated during execution or runtime.
- In array memory to the elements of the array is allocated sequentially in the memory whereas in Linked list memory is assigned to the node of linked list is random.
- If our requirement of memory is defined or fixed initially, then an array is a better option for our program, but when it is not decided, then a linked list is a better option.
- In array memory utilization is inefficient whereas in linked list memory utilization is efficient.
Array vs Linked list in table
| Factor | Array | Linked List |
|---|---|---|
| Structure | Fixed-size, contiguous memory allocation. | Dynamic-size, non-contiguous memory allocation. |
| Memory Usage | Efficient if size is known in advance. | Additional memory for storing pointers. |
| Access Time | Constant time access (O(1)) for elements. | Linear time access (O(n)) required to traverse. |
| Insertion/Deletion | Expensive, especially at the beginning or middle. | Efficient, as it involves changing pointers. |
| Resizing | Requires creating a new array and copying elements. | No resizing needed; elements can be added/removed dynamically. |
| Memory Allocation | Generally statically allocated (though dynamic arrays exist). | Dynamically allocated. |
| Search | Efficient for indexed access. | Sequential access required, less efficient. |
| Usage | Preferred for static data storage, direct element access. | Preferred for dynamic data where insertion/deletion operations are frequent. |
| Element Size | Homogeneous size (elements are of the same type). | Heterogeneous size possible (each node can hold different data types). |
| Memory Waste | No extra memory apart from the array itself. | Extra memory for pointers in each element (node). |
| Cache-Friendliness | More cache-friendly due to contiguous memory allocation. | Less cache-friendly due to scattered nodes. |