Why Linked List Exists and What Problem It Solves in DSA Typescript - Challenge Your Understanding

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why use a linked list instead of an array?

Imagine you have a list of items that can grow or shrink often. Which problem does a linked list solve better than an array?

A Linked lists allow easy insertion and deletion anywhere without shifting elements.

B Linked lists provide faster access to elements by index than arrays.

C Linked lists use less memory than arrays because they store elements contiguously.

D Linked lists automatically sort elements as you add them.

💡 Hint

Think about what happens when you add or remove items in the middle of an array.

Arrays store elements in continuous memory, so inserting or deleting in the middle requires shifting elements, which is slow. Linked lists use nodes connected by pointers, so insertion and deletion anywhere is quick without shifting.

❓ Predict Output

intermediate

Output of linked list after insertions

What is the printed state of the linked list after these insertions?

DSA Typescript

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

class LinkedList {
  head: Node | null = null;

  insertAtHead(value: number) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head = newNode;
  }

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

const list = new LinkedList();
list.insertAtHead(3);
list.insertAtHead(5);
list.insertAtHead(7);
list.printList();

A 5 -> 7 -> 3 -> null

B null -> 7 -> 5 -> 3

C 7 -> 5 -> 3 -> null

D 3 -> 5 -> 7 -> null

💡 Hint

Remember that insertAtHead adds new nodes at the start of the list.

Each new value is added at the head, so the last inserted value is first in the list. The order is 7 (last inserted), then 5, then 3.

🔧 Debug

advanced

Why does this linked list insertion cause a runtime error?

What error does this code cause when inserting a node, and why?

DSA Typescript

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

class LinkedList {
  head: Node | null = null;

  insertAtTail(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
  }

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

const list = new LinkedList();
list.insertAtTail(1);
list.insertAtTail(2);
list.insertAtTail(3);
list.insertAtTail(null as any);
list.printList();

A SyntaxError: Unexpected token 'null'

B No error, prints: 1 -> 2 -> 3 -> null

C TypeError: Cannot read property 'value' of undefined

D TypeError: Cannot read property 'next' of null

💡 Hint

Look at what happens when inserting null as a node value and how the code handles it.

Inserting null as a value creates a node with null value but valid next pointer. The code does not check for null values, so no error on insertion. However, if null is cast incorrectly or used as a node, it can cause a TypeError when accessing next on null. Here, the cast null as any bypasses type safety but the node is created. The error occurs if code tries to access next of null directly, which can happen if the list is corrupted.

❓ Predict Output

advanced

Result of removing a node from linked list

What is the linked list state after removing the node with value 2?

DSA Typescript

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

class LinkedList {
  head: Node | null = null;

  insertAtTail(value: number) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
  }

  remove(value: number) {
    if (!this.head) return;
    if (this.head.value === value) {
      this.head = this.head.next;
      return;
    }
    let current = this.head;
    while (current.next && current.next.value !== value) {
      current = current.next;
    }
    if (current.next) {
      current.next = current.next.next;
    }
  }

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

const list = new LinkedList();
list.insertAtTail(1);
list.insertAtTail(2);
list.insertAtTail(3);
list.remove(2);
list.printList();

A 1 -> 3 -> null

B 1 -> 2 -> 3 -> null

C 2 -> 3 -> null

D 1 -> null

💡 Hint

Think about how the remove method updates the links to skip the removed node.

The remove method finds the node before the one with value 2 and changes its next pointer to skip the node with value 2, effectively removing it. The list becomes 1 -> 3 -> null.

🧠 Conceptual

expert

Why linked lists are preferred for implementing stacks and queues?

Which reason best explains why linked lists are often used to implement stacks and queues instead of arrays?

A Linked lists provide faster random access to elements by index.

B Linked lists allow dynamic size changes without resizing or copying elements.

C Linked lists automatically keep elements sorted for stacks and queues.

D Linked lists use less memory than arrays because they store elements contiguously.

💡 Hint

Consider what happens when a stack or queue grows beyond the initial array size.

Stacks and queues often grow or shrink dynamically. Arrays require resizing and copying when full, which is costly. Linked lists grow dynamically by adding nodes without resizing or copying, making them efficient for these data structures.

Practice

1. Why do we use a linked list instead of an array in some cases?

easy

A. Because linked lists allow easy insertion and deletion without shifting elements

B. Because linked lists use less memory than arrays always

C. Because linked lists store elements in contiguous memory locations

D. Because linked lists are faster for accessing elements by index

Solution

1. Step 1: Understand array limitations

   Arrays store elements in continuous memory, so inserting or deleting in the middle requires shifting many elements, which is slow.

2. Step 2: Understand linked list advantage

   Linked lists store elements as nodes with pointers, so insertion or deletion only changes pointers without shifting elements.

3. Final Answer:

   Because linked lists allow easy insertion and deletion without shifting elements -> Option A

4. Quick Check:

   Linked list insertion/deletion = easy [OK]

Hint: Linked lists avoid shifting elements on insert/delete [OK]

Common Mistakes:

• Thinking linked lists always use less memory
• Believing linked lists store elements contiguously
• Assuming linked lists have fast random access

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

easy

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

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

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

D. class Node { value: number; next: any; constructor(value: number) { this.value = value; this.next = undefined; } }

Solution

1. Step 1: Check next pointer type

   In a singly linked list, next can be another Node or null if it's the last node.

2. Step 2: Verify constructor initialization

   The constructor sets value and initializes next to null correctly.

3. Final Answer:

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

4. Quick Check:

   Node next type = Node or null [OK]

Hint: Next pointer must allow null for last node [OK]

Common Mistakes:

• Not allowing next to be null
• Setting next to undefined instead of null
• Using any type for next pointer

3. What will be the output of the following TypeScript code that uses a linked list?

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 values: number[] = [];
while (current !== null) {
  values.push(current.value);
  current = current.next;
}
console.log(values);

medium

A. []

B. [3, 2, 1]

C. [1, 2]

D. [1, 2, 3]

Solution

1. Step 1: Build linked list nodes

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

2. Step 2: Traverse linked list and collect values

   Loop visits nodes in order: 1, then 2, then 3, pushing values into array.

3. Final Answer:

   [1, 2, 3] -> Option D

4. Quick Check:

   Traversal order = [1, 2, 3] [OK]

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

Common Mistakes:

• Confusing order and reversing output
• Stopping traversal too early
• Not initializing next pointers correctly

4. The following TypeScript code tries to insert a new node with value 4 at the end of the linked list but has a bug. What is the bug?

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);

function insertAtEnd(head: Node, value: number) {
  let current = head;
  while (current.next !== null) {
    current = current.next;
  }
  current = new Node(value);
}

insertAtEnd(head, 4);

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

medium

A. The function should return the new head node

B. The new node is not linked to the last node; assignment should be current.next = new Node(value)

C. The while loop condition should be current !== null

D. The new node value should be assigned before the loop

Solution

1. Step 1: Analyze insertion logic

   The code moves current to last node, but then assigns current = new Node(value), which only changes local variable, not the list.

2. Step 2: Correct pointer assignment

   To link new node, must assign current.next = new Node(value) so last node points to new node.

3. Final Answer:

   The new node is not linked to the last node; assignment should be current.next = new Node(value) -> Option B

4. Quick Check:

   Link new node with current.next = new Node(value) [OK]

Hint: Assign new node to current.next, not current [OK]

Common Mistakes:

• Assigning new node to current variable only
• Wrong loop condition causing null errors
• Expecting function to return new head unnecessarily

5. You want to store a list of tasks where you often add or remove tasks from the middle. Which data structure is best and why? A linked list or an array? Choose the best option.

hard

A. Array, because it uses less memory than linked lists

B. Array, because it allows fast random access to any task by index

C. Linked list, because it allows efficient insertion and deletion in the middle without shifting elements

D. Linked list, because it stores elements in contiguous memory for cache efficiency

Solution

1. Step 1: Understand operation needs

   Adding/removing tasks often in the middle means many insertions and deletions not at the end.

2. Step 2: Compare array vs linked list for middle operations

   Arrays require shifting elements on insert/delete in middle, which is slow. Linked lists only change pointers, so faster for these operations.

3. Final Answer:

   Linked list, because it allows efficient insertion and deletion in the middle without shifting elements -> Option C

4. Quick Check:

   Middle insert/delete = linked list best [OK]

Hint: For frequent middle changes, linked list is faster [OK]

Common Mistakes:

• Choosing array for fast random access ignoring insert/delete cost
• Thinking linked lists use less memory always
• Believing linked lists store elements contiguously