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

Mental Model

Arrays store items in order in one block of memory, while linked lists store items scattered but connected by pointers.

Analogy: An array is like a row of mailboxes all in a line, easy to find by number. A linked list is like a treasure hunt where each clue points to the next location.

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

Dry Run Walkthrough

Input: Compare adding a new item at the start and accessing the 3rd item in both array and linked list of 5 elements

Goal: Show how arrays and linked lists behave differently for insertion at start and access by position

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

[0][1][2][3][4][5]

Why: Arrays need to move all items to make space at the start

Step 2: Access 3rd item in array directly by index

Accessed value: 2

Why: Arrays allow direct access by index quickly

Step 3: Insert 0 at start of linked list by creating new node pointing to old head

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null

Why: Linked lists add at start by changing pointers, no shifting needed

Step 4: Access 3rd item in linked list by moving pointer step by step

Traverse: 0 -> 1 -> 2 (3rd item)

Why: Linked lists require walking through nodes to reach position

Result:

Array after insert: [0][1][2][3][4][5]
Accessed 3rd item in array: 2
Linked list after insert: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null
Accessed 3rd item in linked list: 2

Annotated Code

DSA Typescript

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

class LinkedList {
  head: Node | null = null;

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

  getAt(index: number): number | null {
    let current = this.head;
    let count = 0;
    while (current !== null) {
      if (count === index) {
        return current.value; // found node at index
      }
      current = current.next; // move to next node
      count++;
    }
    return null; // index out of bounds
  }
}

// Array operations
let arr = [1, 2, 3, 4, 5];
// Insert 0 at start by shifting
arr.unshift(0);
// Access 3rd item (index 2)
const arrValue = arr[2];

// Print results
console.log('Array after insert:', arr);
console.log('Accessed 3rd item in array:', arrValue);

// Linked list operations
const list = new LinkedList();
[5, 4, 3, 2, 1].forEach(v => list.insertAtStart(v));
// List: 1 -> 2 -> 3 -> 4 -> 5
// Insert 0 at start
list.insertAtStart(0);
// Access 3rd item (index 2)
const listValue = list.getAt(2);

// Function to print linked list
function printList(head: Node | null): string {
  let result = '';
  let current = head;
  while (current !== null) {
    result += current.value + ' -> ';
    current = current.next;
  }
  return result + 'null';
}

console.log('Linked list after insert:', printList(list.head));
console.log('Accessed 3rd item in linked list:', listValue);

newNode.next = this.head; // link new node to old 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

while (current !== null) { if (count === index) { return current.value; } current = current.next; count++; }

traverse nodes until reaching desired index

arr.unshift(0);

shift array elements right and insert at start

const arrValue = arr[2];

directly access array element by index

Output

Array after insert: [ 0, 1, 2, 3, 4, 5 ]

Accessed 3rd item in array: 2

Linked list after insert: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> null

Accessed 3rd item in linked list: 2

Complexity Analysis

Time: O(n) for inserting at start in array because all elements shift; O(1) for linked list insertion at start; O(1) for array access by index; O(n) for linked list access by index because traversal is needed

Space: O(n) for both to store n elements; linked list uses extra space for pointers

vs Alternative: Arrays are faster for random access but slower for insertions/deletions at start; linked lists are faster for insertions/deletions at start but slower for random access

Edge Cases

Empty array or linked list

Insertion at start works normally; access returns undefined or null

DSA Typescript

if (count === index) { return current.value; }

Access index out of bounds

Returns undefined for array, null for linked list

DSA Typescript

return null; // index out of bounds

Single element list or array

Insertion at start adds new element before existing; access works normally

DSA Typescript

newNode.next = this.head;

When to Use This Pattern

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

Common Mistakes

Mistake: Trying to access linked list elements by index directly like an array
Fix: Traverse nodes step by step to reach the desired index

Mistake: Assuming insertion at start in array is O(1)
Fix: Remember array shifts all elements, so insertion at start is O(n)

Summary

Arrays store elements contiguously for fast access; linked lists connect elements with pointers for flexible insertion.

Use arrays when you need quick access by position; use linked lists when you need frequent insertions or deletions at the start or middle.

The key insight is arrays are like mailboxes in a row for quick lookup, linked lists are like a chain of clues where you must follow links to find items.

Practice

1. Which data structure is better when you need fast random access to elements by index?

easy

A. Stack

B. Linked List

C. Array

D. Queue

Solution

1. Step 1: Understand random access in arrays

   Arrays store elements in contiguous memory, so accessing by index is fast and direct.

2. Step 2: Understand random access in linked lists

   Linked lists require traversal from the head to reach an index, which is slower.

3. Final Answer:

   Array -> Option C

4. Quick Check:

   Fast random access = Array [OK]

Hint: Arrays give fast index access; linked lists do not [OK]

Common Mistakes:

• Thinking linked lists allow fast index access
• Confusing stack or queue with arrays
• Assuming all data structures have same access speed

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

easy

A. const node = new LinkedListNode(null);

B. const node = new LinkedListNode();

C. const node = LinkedListNode();

D. const node = LinkedListNode(null);

Solution

1. Step 1: Understand TypeScript class instantiation

   To create an instance, use the 'new' keyword with constructor parameters.

2. Step 2: Check constructor parameters

   LinkedListNode usually requires a value; null can represent empty data.

3. Final Answer:

   const node = new LinkedListNode(null); -> Option A

4. Quick Check:

   Use 'new' with constructor args for instances [OK]

Hint: Use 'new' keyword with constructor parameters to create nodes [OK]

Common Mistakes:

• Omitting 'new' keyword
• Calling class like a function without 'new'
• Passing no arguments when constructor expects one

3. Given this TypeScript code, what is the printed output?

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

const head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);

let current = head;
const result: number[] = [];
while (current !== null) {
  result.push(current.value);
  current = current.next;
}
console.log(result);

medium

A. [1, 2, 3]

B. [3, 2, 1]

C. [1, 3, 2]

D. []

Solution

1. Step 1: Build the linked list nodes

   Nodes created with values 1, 2, 3 linked in order: 1 -> 2 -> 3 -> null.

2. Step 2: Traverse and collect values

   Loop pushes values 1, then 2, then 3 into result array.

3. Final Answer:

   [1, 2, 3] -> Option A

4. Quick Check:

   Traverse linked list in order = [1, 2, 3] [OK]

Hint: Traverse linked list from head to null to get values in order [OK]

Common Mistakes:

• Confusing order of nodes
• Not updating current pointer correctly
• Expecting reversed output

4. This TypeScript code tries to insert a new node at the start of a linked list but has a bug. What is the error?

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

let head = new Node(1);
head.next = new Node(2);

function insertAtStart(newValue: number) {
  const newNode = new Node(newValue);
  newNode.next = head.next;
  head = newNode;
}

insertAtStart(0);

let current = head;
const result: number[] = [];
while (current !== null) {
  result.push(current.value);
  current = current.next;
}
console.log(result);

medium

A. head should not be reassigned inside the function

B. newNode.next should point to head, not head.next

C. Node constructor missing initialization of next

D. insertAtStart should return the new head

Solution

1. Step 1: Analyze insertion logic

   New node's next is set to head.next, skipping the current head node.

2. Step 2: Correct pointer assignment

   To insert at start, newNode.next must point to current head, preserving the list.

3. Final Answer:

   newNode.next should point to head, not head.next -> Option B

4. Quick Check:

   Insert at start = newNode.next = head [OK]

Hint: New head's next must link to old head, not old head's next [OK]

Common Mistakes:

• Setting newNode.next to head.next causes node loss
• Not updating head reference properly
• Confusing next pointers in linked list

5. You need to frequently insert and delete elements in the middle of a large collection. Which data structure is better and why? A) Array, because it allows fast random access. B) Linked List, because it supports binary search efficiently. C) Array, because it uses less memory. D) Linked List, because it allows fast insertion and deletion without shifting elements.

hard

A. Array, because it allows fast random access.

B. Linked List, because it supports binary search efficiently.

C. Array, because it uses less memory.

D. Linked List, because it allows fast insertion and deletion without shifting elements.

Solution

1. Step 1: Consider insertion and deletion in arrays

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

2. Step 2: Consider linked list advantages

   Linked lists can insert or delete nodes by changing pointers without shifting elements, making these operations faster.

3. Final Answer:

   Linked List, because it allows fast insertion and deletion without shifting elements. -> Option D

4. Quick Check:

   Frequent middle insert/delete = Linked List [OK]

Hint: Linked lists excel at middle insert/delete without shifting [OK]

Common Mistakes:

• Choosing array for frequent middle insert/delete
• Thinking linked lists support binary search efficiently
• Ignoring cost of shifting elements in arrays