Linked List vs Array When to Choose Which in DSA Typescript - Visual Comparison

Concept Flow - Linked List vs Array When to Choose Which

Start: Need to store data

↓

Decide data size known?

Yes→Use Array: fixed size, fast access

No↓

Need frequent insert/delete?

Yes→Use Linked List: flexible size, easy insert/delete

No↓

Need fast random access?

Yes→Use Array

No↓

Use Linked List

↓

End

This flow shows how to choose between array and linked list based on data size knowledge, insertion/deletion needs, and access speed.

Execution Sample

DSA Typescript

const arr = [1, 2, 3];
arr.push(4);
// Array size fixed or dynamic

class Node {
  value: number;
  next: Node | null = null;
}
// Linked list nodes linked dynamically

Shows array creation and push, and linked list node structure for dynamic linking.

Execution Table

Step	Operation	Data Structure	Action Detail	Visual State
1	Initialize array	Array	Create array with elements [1, 2, 3]	[1, 2, 3]
2	Add element	Array	Push 4 to array	[1, 2, 3, 4]
3	Initialize linked list	Linked List	Create head node with value 1	1 -> null
4	Add node	Linked List	Create node with value 2, link to head	1 -> 2 -> null
5	Add node	Linked List	Create node with value 3, link to previous	1 -> 2 -> 3 -> null
6	Insert node	Linked List	Insert node with value 4 after node 2	1 -> 2 -> 4 -> 3 -> null
7	Decision: Access element at index 2	Array	Direct access arr[2] = 3	[1, 2, 3, 4] (access 3)
8	Decision: Access element at index 2	Linked List	Traverse nodes to index 2, value 4	1 -> 2 -> 4 -> 3 -> null (access 4)
9	Decision: Delete element at index 1	Array	Remove element at index 1, shift elements	[1, 3, 4]
10	Decision: Delete node after head	Linked List	Change head.next to head.next.next	1 -> 4 -> 3 -> null
11	End	-	-	-

💡 All operations done to compare array and linked list behaviors.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 6	After Step 9	After Step 10	Final
Array	[]	[1, 2, 3, 4]	[1, 2, 3, 4]	[1, 2, 3, 4]	[1, 3, 4]	[1, 3, 4]	[1, 3, 4]
LinkedList Head	null	1 -> null	1 -> 2 -> 3 -> null	1 -> 2 -> 4 -> 3 -> null	1 -> 2 -> 4 -> 3 -> null	1 -> 4 -> 3 -> null	1 -> 4 -> 3 -> null

Key Moments - 3 Insights

Why is accessing an element by index faster in an array than in a linked list?

In the execution_table at steps 7 and 8, array access is direct using the index, while linked list access requires traversal from the head node to the desired position, making it slower.

Why is insertion easier in a linked list compared to an array?

At step 6, inserting a node in the linked list only requires changing pointers, while in arrays (step 9), elements must be shifted to make space, which is more costly.

What happens to the array when an element is deleted?

At step 9, deleting an element causes all subsequent elements to shift left to fill the gap, changing the array size and order.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the visual state of the linked list?

A 1 -> 2 -> 3 -> 4 -> null

B 1 -> 2 -> 4 -> 3 -> null

C 1 -> 4 -> 2 -> 3 -> null

D 1 -> 3 -> 4 -> null

💡 Hint

Check the Visual State column at step 6 in the execution_table.

At which step does the array remove an element and shift remaining elements?

A Step 7

B Step 8

C Step 9

D Step 10

💡 Hint

Look for the operation describing removal and shifting in the execution_table.

If we want fast random access, which data structure should we choose according to the concept_flow?

A Linked List

B Array

C Either works the same

D Neither is suitable

💡 Hint

Refer to the decision points in the concept_flow diagram.

Concept Snapshot

Linked List vs Array Choice:
- Use Array if size known, need fast random access.
- Use Linked List if size unknown, frequent insert/delete.
- Array: fast access, costly insert/delete.
- Linked List: slow access, easy insert/delete.
- Choose based on operation needs and data size knowledge.

Full Transcript

This lesson compares arrays and linked lists to help decide which to use. Arrays have fixed or dynamic size and allow fast direct access by index, but inserting or deleting elements requires shifting others. Linked lists store elements in nodes linked by pointers, allowing easy insertion and deletion anywhere but slower access since traversal is needed. The concept flow guides choosing based on whether data size is known and if frequent insertions or deletions happen. The execution table shows step-by-step operations on both structures, including adding, accessing, and deleting elements, with visual states. Key moments clarify why arrays have fast access and linked lists have easier insertions. The quiz tests understanding of these differences. Remember, arrays excel at fast access, linked lists excel at flexible size and easy modification.

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