Comparison between Array
, Linked List
and List
data structures.
Array
vs Linked List
vs List
¶
Array¶
- Description: It stored in contiguous memory spaces and consist of elements of the same type.
- Size: It has fixed size and cannot be changed during runtime.
- Memory Allocation: Since it has fixed size, the memory allocated statically.
- Insertion and Deletion
- Time Complexity: O(n)
- Extra element will be lost due to it's fixed size. Therefore, we will declare a longer array but if it's not fully used, those ending
undefined
element will waste the memory space - If maintaining the order of the elements is a requirement, then it will have low efficiency when shifting operation on large set of array.
- Access Time
- Time Complexity: O(1)
- It use linear search to find element due to its linear data structure
- Cache locality: Since it is stored in contiguous memory spaces, it has better cache locality than list.
Linked List¶
- Description: It is a linear data structure where each element considered as a separate object, also known as a node. Each node has two parts: data and reference to the next node.
- Size: It has dynamic size and can be changed during runtime.
- Memory Allocation: Since it has dynamic size, the memory allocated dynamically and it will allocate more memory than
Array
due to the reference to the next node. - Insertion and Deletion
- Time Complexity: O(1)
- It has high efficiency when inserting or deleting an element at the beginning or end of the list.
- If maintaining the order of the elements is a requirement, then it will have high efficiency when shifting operation on large set of array.
- Access Time
- Time Complexity: O(n), because it must traverse from the head node to the desired node.
- Cache locality: Since it is stored in non-contiguous memory spaces, it has worse cache locality compared to
Array
.
List¶
- Size: It is dynamic size and can be changed during runtime.
- Memory Allocation: Since it has dynamic size, the memory allocated dynamically.
- Insertion and Deletion
- Time Complexity: O(1)
- Extra element will be lost due to it's fixed size. Therefore, we will declare a longer array but if it's not fully used, those ending
undefined
element will waste the memory space
Dynamically-typed
and Statically-typed
languages
Typescript is a dynamically-typed language (similar to Python, Ruby, PHP and others), which means that Array
are typically implemented as dynamic arrays, also known as resizable arrays or List
. Therefore, both of them are used interchangeably in Typescript. But in theorethical context, they are different.
Rust is a statically-typed language (similar to Dart, C, Zig and others), so Array
and List
are different. In Rust, Array
is a fixed-size array, while Vec
is a dynamic array, similar to List
in other languages.
If you want to modify the size of an array, you either need to use a Vec
or create a new array with the desired size and copy the elements from the old array to the new one.
// If you able know the size of the new array
// you can copy the elements from the old array
// to the new one with the desired size
let mut nums = [1, 2, 3, 4, 5];
let new_size = 10;
let mut new_nums = [0; new_size];
// Copy the elements from the old array to the new one
for i in 0..nums.len() {
new_nums[i] = nums[i];
}
println!("{:?}", new_nums); // [1, 2, 3, 4, 5, 0, 0, 0, 0, 0]
Extras
You may heard about Auxiliary Array
, which is an auxiliary data structure or helper1 that is used to store additional information about the elements of the main array temporarily. For example, use an auxiliary array to store the prefix sum(cumulative sum) of the elements in the main array. This way, you can find the sum of elements in a range in constant time.