Linked List vs Array When to Choose Which in DSA Typescript - Compare & Choose

Challenge - 5 Problems

🧠 Conceptual

intermediate

When is a linked list better than an array?

Choose the scenario where using a linked list is more efficient than using an array.

A When you frequently insert or delete elements in the middle of the collection.

B When you need to sort elements quickly using built-in array methods.

C When you want to minimize memory usage by storing elements contiguously.

D When you need fast random access to elements by index.

💡 Hint

Think about which data structure allows easy insertion and deletion without shifting elements.

Linked lists allow fast insertion and deletion anywhere because they only change pointers, unlike arrays which require shifting elements.

❓ Predict Output

intermediate

Output of array vs linked list insertion time simulation

What is the output of the following TypeScript code simulating insertion times for array and linked list?

DSA Typescript

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

class LinkedList {
  head: Node | null = null;
  insertAtStart(value: number) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head = newNode;
  }
}

const array: number[] = [];
const linkedList = new LinkedList();

// Insert 3 elements at start
array.unshift(1);
array.unshift(2);
array.unshift(3);
linkedList.insertAtStart(1);
linkedList.insertAtStart(2);
linkedList.insertAtStart(3);

console.log('Array:', array);

let current = linkedList.head;
const linkedListValues: number[] = [];
while (current) {
  linkedListValues.push(current.value);
  current = current.next;
}
console.log('LinkedList:', linkedListValues);

A Array: [1, 2, 3]\nLinkedList: [3, 2, 1]

B Array: [1, 2, 3]\nLinkedList: [1, 2, 3]

C Array: [3, 2, 1]\nLinkedList: [1, 2, 3]

D Array: [3, 2, 1]\nLinkedList: [3, 2, 1]

💡 Hint

Remember that unshift adds elements to the start of the array, and insertAtStart adds nodes at the head of the linked list.

Both array.unshift and linkedList.insertAtStart add elements at the beginning, so the newest element appears first in both.

🔧 Debug

advanced

Why does this linked list traversal code cause an error?

Given the following TypeScript code, what error will it cause and why?

DSA Typescript

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

const head: Node | null = null;

let current = head;
while (current.next !== null) {
  console.log(current.value);
  current = current.next;
}

A TypeError: Cannot read property 'next' of null because current is null initially.

B No error; code prints all node values correctly.

C SyntaxError due to missing semicolon after class definition.

D ReferenceError: head is not defined.

💡 Hint

Check what happens when current is null and you try to access current.next.

Since head is null, current is null. Accessing current.next causes a TypeError because null has no properties.

🚀 Application

advanced

Choosing data structure for frequent middle insertions

You need to design a system where you insert and delete elements frequently in the middle of a collection. Which data structure is best and why?

A Stack, because it supports fast push and pop operations.

B Queue, because it processes elements in order.

C Linked list, because it allows insertion and deletion without shifting elements.

D Array, because it allows fast random access and built-in methods for insertion.

💡 Hint

Think about which structure avoids shifting elements when inserting or deleting in the middle.

Linked lists allow insertion and deletion anywhere by changing pointers, avoiding the costly shifting needed in arrays.

❓ Predict Output

expert

Output after mixed operations on array and linked list

What is the output of this TypeScript code after performing insertions and deletions on an array and a linked list?

DSA Typescript

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

class LinkedList {
  head: Node | null = null;
  insertAtEnd(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }
  deleteAtStart() {
    if (this.head) {
      this.head = this.head.next;
    }
  }
}

const array: number[] = [];
const linkedList = new LinkedList();

// Insert 1, 2, 3 at end
array.push(1);
array.push(2);
array.push(3);
linkedList.insertAtEnd(1);
linkedList.insertAtEnd(2);
linkedList.insertAtEnd(3);

// Delete first element
array.shift();
linkedList.deleteAtStart();

// Insert 4 at end
array.push(4);
linkedList.insertAtEnd(4);

console.log('Array:', array);

let current = linkedList.head;
const linkedListValues: number[] = [];
while (current) {
  linkedListValues.push(current.value);
  current = current.next;
}
console.log('LinkedList:', linkedListValues);

A Array: [2, 3, 4]\nLinkedList: [1, 2, 3, 4]

B Array: [2, 3, 4]\nLinkedList: [2, 3, 4]

C Array: [1, 2, 3, 4]\nLinkedList: [1, 2, 3, 4]

D Array: [1, 2, 3]\nLinkedList: [2, 3, 4]

💡 Hint

Remember that shift removes the first element from the array and deleteAtStart removes the head node from the linked list.

After removing the first element and adding 4 at the end, both array and linked list contain [2, 3, 4].

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