Why Linked List Exists and What Problem It Solves in DSA Typescript - Why It Works

Concept Flow - Why Linked List Exists and What Problem It Solves

Start: Need to store items

↓

Use Array?

Yes→Fixed size or resizing issues

No↓

Use Linked List

↓

Store items as nodes with pointers

↓

Add or remove nodes easily without shifting

↓

Efficient dynamic memory use

Shows decision from needing storage to choosing linked list for flexible size and easy insert/delete.

Execution Sample

DSA Typescript

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

Defines a linked list node holding a value and a pointer to the next node.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with empty list	None	head = null	null
2	Create first node with value 10	Node(10)	head -> Node(10)	10 -> null
3	Create second node with value 20	Node(10), Node(20)	Node(10).next -> Node(20)	10 -> 20 -> null
4	Create third node with value 30	Node(10), Node(20), Node(30)	Node(20).next -> Node(30)	10 -> 20 -> 30 -> null
5	Add node without shifting array	3 nodes	Pointers updated only	10 -> 20 -> 30 -> null
6	Remove node easily by changing pointers	2 nodes	Node(10).next -> Node(30)	10 -> 30 -> null
7	End	2 nodes	No changes	10 -> 30 -> null

💡 Linked list allows dynamic size and easy insert/delete without shifting elements.

Variable Tracker

Variable	Start	After 2	After 3	After 4	After 6	Final
head	null	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)
Node(10).next	null	null	Node(20)	Node(20)	Node(30)	Node(30)
Node(20).next	null	null	null	Node(30)	null	null
Node(30).next	null	null	null	null	null	null
List Size	0	1	2	3	2	2

Key Moments - 3 Insights

Why do we use pointers instead of array indexes?

Pointers let us link nodes anywhere in memory, so we can add or remove nodes without moving others, unlike arrays where indexes require shifting elements (see steps 5 and 6 in execution_table).

Why is linked list better for dynamic size than arrays?

Arrays have fixed size or need costly resizing; linked lists grow or shrink by changing pointers only, no resizing needed (see list size changes in variable_tracker).

What does 'null' mean in the visual state?

'null' means the end of the list, no next node. It marks where traversal stops (see visual state column in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the pointer change?

A head points to Node(20)

B Node(10).next points to Node(20)

C Node(20).next points to Node(10)

D Node(10).next is null

💡 Hint

Check the 'Pointer Changes' column at step 3 in execution_table.

At which step does the list size reduce from 3 to 2?

A Step 6

B Step 4

C Step 5

D Step 7

💡 Hint

Look at 'List Size' row in variable_tracker between After 4 and After 6.

If we add a new node at the start, what pointer changes would happen?

A No pointer changes needed

B head points to old head, new node.next is null

C head points to new node, new node.next points to old head

D New node.next points to null only

💡 Hint

Think about how head and next pointers update when inserting at the front.

Concept Snapshot

Linked List stores items as nodes linked by pointers.
Each node points to the next, ending with null.
Allows dynamic size without resizing.
Insert/delete by changing pointers only.
No shifting like arrays.
Good for unknown or changing data size.

Full Transcript

A linked list is a way to store items where each item is a node pointing to the next. Unlike arrays, linked lists don't need fixed size or resizing. We add or remove nodes by changing pointers, not by moving elements. This makes linked lists flexible and efficient for dynamic data. The end of the list is marked by a null pointer. This structure solves problems of fixed size and costly resizing in arrays.

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