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

Challenge - 5 Problems

🧠 Conceptual

intermediate

When to Prefer Linked List Over Array?

Which scenario best explains when a linked list is a better choice than an array?

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

B When memory usage must be contiguous and minimal overhead is required.

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

D When you want to sort elements quickly using built-in methods.

💡 Hint

Think about which data structure allows easy insertion and deletion without shifting many 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 Insertions

What is the output after inserting 99 at index 1 in both an array and a linked list?

Array starts as [10, 20, 30]

Linked list starts as 10 -> 20 -> 30 -> null

DSA Javascript

const array = [10, 20, 30];
array.splice(1, 0, 99);

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

class LinkedList {
  constructor() {
    this.head = null;
  }
  append(value) {
    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;
  }
  insertAt(index, value) {
    const newNode = new Node(value);
    if (index === 0) {
      newNode.next = this.head;
      this.head = newNode;
      return;
    }
    let current = this.head;
    let prev = null;
    let i = 0;
    while (current && i < index) {
      prev = current;
      current = current.next;
      i++;
    }
    prev.next = newNode;
    newNode.next = current;
  }
  toString() {
    let result = '';
    let current = this.head;
    while (current) {
      result += current.value + ' -> ';
      current = current.next;
    }
    return result + 'null';
  }
}

const list = new LinkedList();
[10, 20, 30].forEach(v => list.append(v));
list.insertAt(1, 99);

console.log('Array:', array);
console.log('LinkedList:', list.toString());

A

Array: [10, 99, 20, 30]
LinkedList: 10 -> 99 -> 20 -> 30 -> null

B

Array: [10, 20, 99, 30]
LinkedList: 10 -> 20 -> 99 -> 30 -> null

C

Array: [10, 99, 20, 30]
LinkedList: 10 -> 20 -> 30 -> 99 -> null

D

Array: [10, 20, 30, 99]
LinkedList: 99 -> 10 -> 20 -> 30 -> null

💡 Hint

Remember that array.splice(index, 0, value) inserts at index shifting elements right.

Linked list insertion at index 1 places new node after first node.

Array.splice inserts 99 at index 1 shifting 20 and 30 right. Linked list insertion at index 1 places 99 after 10.

🔧 Debug

advanced

Why Does This Linked List Deletion Code Fail?

Consider this code to delete a node with value 3 from a linked list. Why does it fail to delete the node?

DSA Javascript

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

class LinkedList {
  constructor() {
    this.head = null;
  }
  append(value) {
    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;
  }
  delete(value) {
    let current = this.head;
    while (current) {
      if (current.value === value) {
        current = current.next;
        return;
      }
      current = current.next;
    }
  }
}

A It only moves the current pointer but does not update the previous node's next pointer, so the node is not removed.

B It deletes the head node always regardless of value.

C It causes an infinite loop because current is never updated.

D It throws a TypeError because current.next is undefined.

💡 Hint

Think about what is needed to remove a node from a linked list.

To delete a node, you must update the previous node's next pointer to skip the node to delete. This code only moves the current pointer, so the list remains unchanged.

❓ Predict Output

advanced

Result of Accessing Middle Element in Linked List vs Array

Given an array and a linked list both containing [5, 10, 15, 20, 25], what is the time complexity to access the element at index 3?

What is the output of accessing that element?

DSA Javascript

const array = [5, 10, 15, 20, 25];

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

class LinkedList {
  constructor() {
    this.head = null;
  }
  append(value) {
    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;
  }
  getAt(index) {
    let current = this.head;
    let i = 0;
    while (current && i < index) {
      current = current.next;
      i++;
    }
    return current ? current.value : null;
  }
}

const list = new LinkedList();
[5, 10, 15, 20, 25].forEach(v => list.append(v));

const arrayValue = array[3];
const listValue = list.getAt(3);

console.log('Array element at index 3:', arrayValue);
console.log('LinkedList element at index 3:', listValue);

A

Array element at index 3: 25 (O(1))
LinkedList element at index 3: 15 (O(n))

B

Array element at index 3: 15 (O(n))
LinkedList element at index 3: 20 (O(1))

C

Array element at index 3: 20 (O(n))
LinkedList element at index 3: 25 (O(n))

D

Array element at index 3: 20 (O(1))
LinkedList element at index 3: 20 (O(n))

💡 Hint

Arrays allow direct access by index. Linked lists require walking nodes one by one.

Accessing an array element by index is fast (constant time). Accessing a linked list element requires traversing nodes (linear time). Both return the value 20 at index 3.

🧠 Conceptual

expert

Choosing Data Structure for Real-Time Insertions and Memory Constraints

You are designing a system that requires frequent insertions and deletions at unknown positions and must use memory efficiently without fragmentation. Which data structure is best?

A Array, because it uses contiguous memory and supports fast random access.

B Linked list, because it allows dynamic memory allocation and easy insertions/deletions without shifting elements.

C Hash table, because it provides average O(1) insertions and deletions by key.

D Binary search tree, because it keeps elements sorted and allows efficient insertions.

💡 Hint

Consider which structure avoids memory fragmentation and supports dynamic size with efficient insert/delete.

Linked lists allocate memory dynamically for each node, avoiding fragmentation and allowing efficient insertions/deletions anywhere without shifting elements.

Practice

1. Which data structure is generally better for frequent insertions and deletions in the middle of the collection?

easy

A. Array

B. Neither is suitable

C. Both are equally efficient

D. Linked List

Solution

1. Step 1: Understand insertion and deletion costs in arrays

   Arrays require shifting elements when inserting or deleting in the middle, which is costly.

2. Step 2: Understand linked list insertion and deletion

   Linked lists can insert or delete nodes by changing pointers without shifting elements.

3. Final Answer:

   Linked List -> Option D

4. Quick Check:

   Insert/delete middle = Linked List [OK]

Hint: Choose linked list for fast middle insert/delete [OK]

Common Mistakes:

• Thinking arrays handle middle insertions efficiently
• Confusing array resizing with insertion cost
• Assuming linked lists have faster access

2. Which of the following is the correct way to declare an empty linked list node in JavaScript?

easy

A. const node = { value: null, next: null };

B. const node = [null, null];

C. const node = null;

D. const node = new Array();

Solution

1. Step 1: Understand linked list node structure

   A linked list node typically has a value and a pointer to the next node, represented as an object with 'value' and 'next' properties.

2. Step 2: Check each option

   const node = { value: null, next: null }; correctly creates an object with 'value' and 'next' set to null. Others do not represent a linked list node properly.

3. Final Answer:

   const node = { value: null, next: null }; -> Option A

4. Quick Check:

   Linked list node = object with value and next [OK]

Hint: Linked list nodes are objects with value and next [OK]

Common Mistakes:

• Using arrays instead of objects for nodes
• Assigning null directly without properties
• Confusing array declaration with node

3. What will be the output of the following JavaScript code?

const arr = [1, 2, 3];
arr.splice(1, 1, 4);
console.log(arr);

medium

A. [1, 4, 3]

B. [1, 2, 3]

C. [4, 2, 3]

D. [1, 3]

Solution

1. Step 1: Understand splice parameters

   arr.splice(1, 1, 4) means start at index 1, remove 1 element, then insert 4 at that position.

2. Step 2: Apply splice to array

   Original array is [1, 2, 3]. Removing element at index 1 (which is 2) and inserting 4 results in [1, 4, 3].

3. Final Answer:

   [1, 4, 3] -> Option A

4. Quick Check:

   splice replaces element at index 1 with 4 [OK]

Hint: splice(start, deleteCount, item) replaces elements [OK]

Common Mistakes:

• Thinking splice inserts without deleting
• Confusing splice with slice
• Expecting original array unchanged

4. Identify the error in the following linked list insertion code snippet:

function insertAtHead(head, value) {
  const newNode = { value: value, next: head };
  head = newNode;
  return head;
}

let head = null;
insertAtHead(head, 5);
console.log(head);

medium

A. newNode is not created correctly

B. The head variable is not updated outside the function

C. The function should not return head

D. The next pointer should be null

Solution

1. Step 1: Understand variable scope in JavaScript

   Inside the function, head is a local parameter. Assigning head = newNode changes only local copy.

2. Step 2: Check effect on external head variable

   Outside the function, head remains null because the updated head inside the function is not reflected outside.

3. Final Answer:

   The head variable is not updated outside the function -> Option B

4. Quick Check:

   Function parameter reassignment doesn't affect external variable [OK]

Hint: Return and assign new head to update linked list [OK]

Common Mistakes:

• Assuming head changes globally without return
• Not returning the new head
• Misunderstanding pointer assignment

5. You need to store a large collection of items where you frequently add elements at the end and access elements by index quickly. Which data structure should you choose and why?

hard

A. Linked List, because it allows fast access by index

B. Linked List, because it uses less memory than arrays

C. Array, because it allows fast access by index and efficient append

D. Array, because it allows fast insertion and deletion in the middle

Solution

1. Step 1: Analyze access by index requirement

   Arrays provide constant time access by index, linked lists require traversal which is slower.

2. Step 2: Analyze frequent append requirement

   Arrays can append efficiently if capacity allows; linked lists also append efficiently but slower access is a drawback.

3. Final Answer:

   Array, because it allows fast access by index and efficient append -> Option C

4. Quick Check:

   Fast index access + append = Array [OK]

Hint: Use array for fast index access and appending [OK]

Common Mistakes:

• Choosing linked list for fast index access
• Assuming linked list uses less memory always
• Confusing insertion in middle with append