Skip to content

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]
// If you don't know the size of the new array
// you can use `Vec` to create a dynamic array
fn extend(nums: &[i32], enlarge: usize) -> Vec<i32> {
    let mut res: Vec<i32> = vec![0; nums.len() + enlarge];
    for i in 0..nums.len() {
        res[i] = nums[i];
    }
    res
}

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.

// Auxiliary Array
function calculatePrefixSums(nums: number[]): number[] {
    const prefixSums: number[] = []; // Auxiliary array to store prefix sums
    let sum = 0;

    for (let i = 0; i < nums.length; i++) {
        sum += nums[i]; // Add current element to the running sum
        prefixSums.push(sum); // Store the prefix sum for current index
    }

    return prefixSums;
}

// Example usage:
const nums = [1, 2, 3, 4, 5];
const prefixSums = calculatePrefixSums(nums);

console.log(prefixSums); // Output: [1, 3, 6, 10, 15]