Linked List vs Array When to Choose Which in DSA Typescript - Build Both Approaches

Linked List vs Array: When to Choose Which

📖 Scenario: Imagine you are organizing a playlist of songs on your music app. You want to understand when to use an array or a linked list to store your songs efficiently.

🎯 Goal: You will create a simple playlist using an array and a linked list, then learn how to add songs and see the difference in how these data structures work.

📋 What You'll Learn

Create an array called playlistArray with 3 song names

Create a linked list class called SongNode with song and next properties

Create a linked list called playlistLinkedList with the same 3 songs

Add a new song to both playlistArray and playlistLinkedList

Print both playlists to see their contents

💡 Why This Matters

🌍 Real World

Music apps, photo galleries, and message queues use arrays or linked lists depending on how data is added or accessed.

💼 Career

Understanding when to use arrays or linked lists helps in writing efficient code for software development and technical interviews.

1

Create an array playlist

Create an array called playlistArray with these exact songs: 'Song A', 'Song B', 'Song C'

DSA Typescript

# Create an array called playlistArray with 'Song A', 'Song B', 'Song C'
// Your code here

Hint

Use square brackets [] to create an array with the songs inside quotes.

2

Create a linked list class and initial playlist

Create a class called SongNode with a song string property and a next property that can be another SongNode or null. Then create three nodes for 'Song A', 'Song B', and 'Song C' linked together, and assign the first node to playlistLinkedList.

DSA Typescript

const playlistArray: string[] = ['Song A', 'Song B', 'Song C'];
// Create class SongNode and linked list playlistLinkedList
// Your code here

Hint

Define the class with song and next. Link nodes by setting node1.next = node2 and so on.

3

Add a new song to both playlists

Add a new song 'Song D' to the end of playlistArray using push. Then add a new SongNode with 'Song D' to the end of playlistLinkedList by traversing to the last node and linking it.

DSA Typescript

const playlistArray: string[] = ['Song A', 'Song B', 'Song C'];

class SongNode {
    song: string;
    next: SongNode | null;
    constructor(song: string) {
        this.song = song;
        this.next = null;
    }
}

const node1 = new SongNode('Song A');
const node2 = new SongNode('Song B');
const node3 = new SongNode('Song C');

node1.next = node2;
node2.next = node3;

const playlistLinkedList = node1;

// Add 'Song D' to playlistArray and playlistLinkedList
// Your code here

Hint

Use push to add to the array. For the linked list, loop until next is null and then add the new node.

4

Print both playlists

Print playlistArray using console.log. Then print the linked list songs by traversing from playlistLinkedList and printing each song separated by -> and ending with null.

DSA Typescript

const playlistArray: string[] = ['Song A', 'Song B', 'Song C'];

class SongNode {
    song: string;
    next: SongNode | null;
    constructor(song: string) {
        this.song = song;
        this.next = null;
    }
}

const node1 = new SongNode('Song A');
const node2 = new SongNode('Song B');
const node3 = new SongNode('Song C');

node1.next = node2;
node2.next = node3;

const playlistLinkedList = node1;

playlistArray.push('Song D');

let current = playlistLinkedList;
while (current.next !== null) {
    current = current.next;
}
current.next = new SongNode('Song D');

// Print playlistArray and playlistLinkedList
// Your code here

Hint

Use console.log to print the array directly. For the linked list, build a string by moving through each node until null.

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