Linked List vs Array When to Choose Which in DSA Javascript - Trade-offs & Analysis

Mental Model

Arrays store items in order in one block of memory, making access fast but changes slow. Linked lists store items scattered in memory, connected by pointers, making changes fast but access slower.

Analogy: Think of an array like a row of mailboxes all in a line, easy to find any mailbox quickly. A linked list is like a treasure hunt where each clue points to the next location, so you must follow clues to find the treasure.

Array: [1] -> [2] -> [3] -> [4]
Linked List: 1 -> 2 -> 3 -> 4 -> null

Dry Run Walkthrough

Input: Array: [10, 20, 30], Insert 15 at start; Linked List: 10 -> 20 -> 30 -> null, Insert 15 at start

Goal: Show how insertion at start differs in arrays and linked lists

Step 1: Insert 15 at start of array by shifting elements right

[15] -> [10] -> [20] -> [30]

Why: Array elements must move to make space at the start

Step 2: Insert 15 at start of linked list by creating new node pointing to head

15 -> 10 -> 20 -> 30 -> null

Why: Linked list just changes head pointer, no shifting needed

Result:

Array after insertion: [15] -> [10] -> [20] -> [30]
Linked List after insertion: 15 -> 10 -> 20 -> 30 -> null

Annotated Code

DSA Javascript

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  insertAtStart(value) {
    const newNode = new Node(value);
    newNode.next = this.head; // link new node to current head
    this.head = newNode; // update head to new node
  }

  toString() {
    let result = '';
    let current = this.head;
    while (current) {
      result += current.value + ' -> ';
      current = current.next;
    }
    return result + 'null';
  }
}

// Array insertion at start
function insertAtStartArray(arr, value) {
  arr.unshift(value); // shifts elements and inserts at start
  return arr;
}

// Driver code
const array = [10, 20, 30];
const linkedList = new LinkedList();
linkedList.insertAtStart(30);
linkedList.insertAtStart(20);
linkedList.insertAtStart(10);

// Insert 15 at start
const newArray = insertAtStartArray(array, 15);
linkedList.insertAtStart(15);

console.log('Array after insertion:', newArray.join(' -> '));
console.log('Linked List after insertion:', linkedList.toString());

newNode.next = this.head; // link new node to current head

link new node to current head to insert at start

this.head = newNode; // update head to new node

update head pointer to new node

arr.unshift(value); // shifts elements and inserts at start

shift array elements right and insert new value at start

Output

Array after insertion: 15 -> 10 -> 20 -> 30

Linked List after insertion: 15 -> 10 -> 20 -> 30 -> null

Complexity Analysis

Time: O(n) for array insertion at start because all elements shift; O(1) for linked list insertion at start because only pointers change

Space: O(n) for array due to storage; O(n) for linked list due to nodes, but insertion uses O(1) extra space

vs Alternative: Linked list insertion is faster at start than array because array shifts elements, but array access is faster due to direct indexing

Edge Cases

Empty array or linked list

Insertion at start works normally; linked list head becomes new node; array adds first element

DSA Javascript

newNode.next = this.head; // link new node to current head

Single element array or linked list

Insertion at start shifts array element or links new node before existing node

DSA Javascript

arr.unshift(value); // shifts elements and inserts at start

When to Use This Pattern

When a problem needs frequent insertions or deletions at the start or middle, linked lists are better; when fast access by index is needed, arrays are better.

Common Mistakes

Mistake: Trying to insert at start of linked list without updating head pointer
Fix: Always update the head pointer to the new node after insertion

Mistake: Assuming array insertion at start is O(1)
Fix: Remember array insertion at start is O(n) because elements must shift

Summary

Compares when to use linked lists or arrays based on insertion and access needs.

Use linked lists for fast insertions/deletions; use arrays for fast indexed access.

Linked lists change pointers to insert quickly; arrays shift elements making insertion slower.

Practice

1. Which data structure is generally better for frequent insertions and deletions in the middle of the collection?

easy

A. Array

B. Neither is suitable

C. Both are equally efficient

D. Linked List

Solution

1. Step 1: Understand insertion and deletion costs in arrays

   Arrays require shifting elements when inserting or deleting in the middle, which is costly.

2. Step 2: Understand linked list insertion and deletion

   Linked lists can insert or delete nodes by changing pointers without shifting elements.

3. Final Answer:

   Linked List -> Option D

4. Quick Check:

   Insert/delete middle = Linked List [OK]

Hint: Choose linked list for fast middle insert/delete [OK]

Common Mistakes:

• Thinking arrays handle middle insertions efficiently
• Confusing array resizing with insertion cost
• Assuming linked lists have faster access

2. Which of the following is the correct way to declare an empty linked list node in JavaScript?

easy

A. const node = { value: null, next: null };

B. const node = [null, null];

C. const node = null;

D. const node = new Array();

Solution

1. Step 1: Understand linked list node structure

   A linked list node typically has a value and a pointer to the next node, represented as an object with 'value' and 'next' properties.

2. Step 2: Check each option

   const node = { value: null, next: null }; correctly creates an object with 'value' and 'next' set to null. Others do not represent a linked list node properly.

3. Final Answer:

   const node = { value: null, next: null }; -> Option A

4. Quick Check:

   Linked list node = object with value and next [OK]

Hint: Linked list nodes are objects with value and next [OK]

Common Mistakes:

• Using arrays instead of objects for nodes
• Assigning null directly without properties
• Confusing array declaration with node

3. What will be the output of the following JavaScript code?

const arr = [1, 2, 3];
arr.splice(1, 1, 4);
console.log(arr);

medium

A. [1, 4, 3]

B. [1, 2, 3]

C. [4, 2, 3]

D. [1, 3]

Solution

1. Step 1: Understand splice parameters

   arr.splice(1, 1, 4) means start at index 1, remove 1 element, then insert 4 at that position.

2. Step 2: Apply splice to array

   Original array is [1, 2, 3]. Removing element at index 1 (which is 2) and inserting 4 results in [1, 4, 3].

3. Final Answer:

   [1, 4, 3] -> Option A

4. Quick Check:

   splice replaces element at index 1 with 4 [OK]

Hint: splice(start, deleteCount, item) replaces elements [OK]

Common Mistakes:

• Thinking splice inserts without deleting
• Confusing splice with slice
• Expecting original array unchanged

4. Identify the error in the following linked list insertion code snippet:

function insertAtHead(head, value) {
  const newNode = { value: value, next: head };
  head = newNode;
  return head;
}

let head = null;
insertAtHead(head, 5);
console.log(head);

medium

A. newNode is not created correctly

B. The head variable is not updated outside the function

C. The function should not return head

D. The next pointer should be null

Solution

1. Step 1: Understand variable scope in JavaScript

   Inside the function, head is a local parameter. Assigning head = newNode changes only local copy.

2. Step 2: Check effect on external head variable

   Outside the function, head remains null because the updated head inside the function is not reflected outside.

3. Final Answer:

   The head variable is not updated outside the function -> Option B

4. Quick Check:

   Function parameter reassignment doesn't affect external variable [OK]

Hint: Return and assign new head to update linked list [OK]

Common Mistakes:

• Assuming head changes globally without return
• Not returning the new head
• Misunderstanding pointer assignment

5. You need to store a large collection of items where you frequently add elements at the end and access elements by index quickly. Which data structure should you choose and why?

hard

A. Linked List, because it allows fast access by index

B. Linked List, because it uses less memory than arrays

C. Array, because it allows fast access by index and efficient append

D. Array, because it allows fast insertion and deletion in the middle

Solution

1. Step 1: Analyze access by index requirement

   Arrays provide constant time access by index, linked lists require traversal which is slower.

2. Step 2: Analyze frequent append requirement

   Arrays can append efficiently if capacity allows; linked lists also append efficiently but slower access is a drawback.

3. Final Answer:

   Array, because it allows fast access by index and efficient append -> Option C

4. Quick Check:

   Fast index access + append = Array [OK]

Hint: Use array for fast index access and appending [OK]

Common Mistakes:

• Choosing linked list for fast index access
• Assuming linked list uses less memory always
• Confusing insertion in middle with append