Memory Layout Comparison Array vs Linked List in DSA Javascript - Compare & Choose

Challenge - 5 Problems

🧠 Conceptual

intermediate

Memory layout difference between array and linked list

Which statement best describes the memory layout difference between an array and a linked list?

A Linked list nodes are stored contiguously; array elements are scattered in memory.

B Array elements are stored in contiguous memory locations; linked list nodes are scattered and connected by pointers.

C Both array and linked list elements are stored contiguously in memory.

D Array elements and linked list nodes are both stored randomly without any order.

💡 Hint

Think about how you find the next element in each data structure.

Arrays store elements next to each other in memory, making access by index fast. Linked lists store nodes anywhere in memory, each node pointing to the next, so elements are not contiguous.

❓ Predict Output

intermediate

Output of memory address simulation for array and linked list

Consider this JavaScript simulation of memory addresses for an array and a linked list. What is the printed output?

DSA Javascript

const array = [10, 20, 30];
const linkedList = [{value: 10, next: 1}, {value: 20, next: 2}, {value: 30, next: null}];

console.log('Array memory addresses:');
for(let i = 0; i < array.length; i++) {
  console.log(`Address ${100 + i * 4}: ${array[i]}`);
}

console.log('Linked list memory addresses:');
for(let i = 0; i < linkedList.length; i++) {
  console.log(`Address ${Math.floor(Math.random() * 1000)}: ${linkedList[i].value}`);
}

A Both array and linked list memory addresses are sequential starting at 100

B Array memory addresses: random addresses with values 10, 20, 30; Linked list memory addresses: 100:10, 104:20, 108:30

C Array memory addresses: 100:10, 104:20, 108:30; Linked list memory addresses: random addresses with values 10, 20, 30

D Both array and linked list memory addresses are random

💡 Hint

Look at how the addresses for array elements are calculated versus linked list nodes.

The array elements have fixed addresses increasing by 4 bytes each (simulated). The linked list nodes have random addresses to simulate scattered memory.

🔧 Debug

advanced

Why does this linked list traversal code fail?

Given this linked list traversal code, why does it cause an error?

DSA Javascript

const linkedList = { value: 1, next: { value: 2, next: { value: 3, next: null } } };
let current = linkedList;
while(current.next !== null) {
  console.log(current.value);
  current = current.next;
}
console.log(current.value);

A It does not print the last node's value inside the loop, so the last value is printed after the loop.

B It causes an infinite loop because current.next never becomes null.

C It throws a TypeError because current becomes null before accessing value.

D It skips the first node's value and starts printing from the second node.

💡 Hint

Check the loop condition and when values are printed.

The loop stops when current.next is null, so the last node's value is printed after the loop. This is intentional and does not cause an error.

❓ Predict Output

advanced

Output after inserting element in linked list vs array

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

DSA Javascript

let array = [10, 20, 30];
array.splice(1, 0, 15);

function Node(value, next = null) {
  this.value = value;
  this.next = next;
}

let head = new Node(10, new Node(20, new Node(30)));

function insertAt(head, index, value) {
  if(index === 0) return new Node(value, head);
  let current = head;
  let i = 0;
  while(current !== null && i < index - 1) {
    current = current.next;
    i++;
  }
  if(current === null) return head;
  current.next = new Node(value, current.next);
  return head;
}

head = insertAt(head, 1, 15);

function printList(head) {
  let current = head;
  let result = '';
  while(current !== null) {
    result += current.value + ' -> ';
    current = current.next;
  }
  result += 'null';
  return result;
}

console.log('Array:', array);
console.log('Linked List:', printList(head));

A

Array: [10, 15, 20, 30]
Linked List: 10 -> 20 -> 30 -> null

B

Array: [10, 20, 30, 15]
Linked List: 10 -> 15 -> 20 -> 30 -> null

C

Array: [10, 20, 15, 30]
Linked List: 10 -> 20 -> 15 -> 30 -> null

D

Array: [10, 15, 20, 30]
Linked List: 10 -> 15 -> 20 -> 30 -> null

💡 Hint

Check how splice works on arrays and how insertAt works on linked lists.

Inserting 15 at index 1 shifts elements in the array and inserts the new node in the linked list at the same position.

🧠 Conceptual

expert

Why does linked list insertion have different time complexity than array insertion?

Why is inserting an element in the middle of a linked list generally faster than inserting in the middle of an array?

A Because linked lists only change pointers without shifting elements, while arrays must shift all elements after the insertion point.

B Because arrays use pointers to connect elements, making insertion slower than linked lists.

C Because linked lists store elements contiguously, making insertion faster than arrays.

D Because arrays have fixed size and cannot insert elements without resizing, unlike linked lists.

💡 Hint

Think about what happens to elements after the insertion point in both structures.

Linked lists insert by changing pointers, no shifting needed. Arrays require shifting elements to make space, which takes more time.

Practice

1. Which of the following best describes how elements are stored in an array compared to a linked list?

easy

A. Both array and linked list elements are stored contiguously in memory.

B. Array elements are scattered in memory, while linked list nodes are stored contiguously.

C. Array elements are stored in contiguous memory locations, while linked list nodes are scattered in memory.

D. Both array and linked list elements are scattered randomly in memory.

Solution

1. Step 1: Understand array memory layout

   Arrays store elements in contiguous memory blocks, meaning elements are next to each other in memory.

2. Step 2: Understand linked list memory layout

   Linked list nodes are allocated separately and linked by pointers, so they can be scattered in memory.

3. Final Answer:

   Array elements are stored in contiguous memory locations, while linked list nodes are scattered in memory. -> Option C

4. Quick Check:

   Array = contiguous, Linked List = scattered [OK]

Hint: Remember: arrays are like books on a shelf, linked lists like scattered notes [OK]

Common Mistakes:

• Thinking linked list nodes are stored contiguously
• Confusing array scattered storage with linked list
• Assuming both have same memory layout

2. Which syntax correctly declares an array and a linked list node in JavaScript?

easy

A. const arr = [1, 2, 3]; const node = { value: 1, next: null };

B. const arr = {1, 2, 3}; const node = [value: 1, next: null];

C. const arr = (1, 2, 3); const node = {1, null};

D. const arr = new LinkedList(); const node = [1, null];

Solution

1. Step 1: Check array declaration syntax

   Arrays in JavaScript are declared with square brackets, e.g., [1, 2, 3].

2. Step 2: Check linked list node syntax

   A linked list node is an object with properties like value and next, e.g., { value: 1, next: null }.

3. Final Answer:

   const arr = [1, 2, 3]; const node = { value: 1, next: null }; -> Option A

4. Quick Check:

   Array uses [], node uses object {} [OK]

Hint: Arrays use [], linked list nodes use objects {} [OK]

Common Mistakes:

• Using curly braces for arrays
• Using array syntax for linked list nodes
• Mixing parentheses for array declaration

3. Consider the following code snippet:

const arr = [10, 20, 30];
const node1 = { value: 10, next: null };
const node2 = { value: 20, next: node1 };
const node3 = { value: 30, next: node2 };

console.log(arr[1]);
console.log(node3.next.value);

What will be the output?

medium

A. 20 and 10

B. 20 and 20

C. 10 and 20

D. 30 and 20

Solution

1. Step 1: Evaluate array access

   arr[1] accesses the second element of the array, which is 20.

2. Step 2: Evaluate linked list access

   node3.next points to node2, whose value is 20, so node3.next.value is 20.

3. Final Answer:

   20 and 20 -> Option B

4. Quick Check:

   arr[1] = 20, node3.next.value = 20 [OK]

Hint: Array index 1 and linked list next value both give 20 [OK]

Common Mistakes:

• Confusing linked list next pointer direction
• Mixing array indices starting at 0
• Reading node values incorrectly

4. The following code attempts to traverse a linked list and print values, but it causes an error:

function printList(head) {
  let current = head;
  while (current !== null) {
    console.log(current.value);
    current = current.value;
  }
}

const node = { value: 5, next: null };
printList(node);

What is the error and how to fix it?

medium

A. Error: current is undefined; fix by initializing current = head.next;

B. No error; code works fine as is.

C. Error: console.log is incorrect; fix by using console.print instead;

D. Error: current.value is not a node; fix by setting current = current.next;

Solution

1. Step 1: Identify the traversal mistake

   The code sets current = current.value, which is a number, not the next node.

2. Step 2: Correct the pointer update

   To traverse, current should be updated to current.next, the pointer to the next node.

3. Final Answer:

   Error: current.value is not a node; fix by setting current = current.next; -> Option D

4. Quick Check:

   Traverse uses current = current.next [OK]

Hint: Traverse linked list using current = current.next [OK]

Common Mistakes:

• Assigning current = current.value instead of current.next
• Not checking for null before accessing value
• Assuming value holds next node

5. You want to insert a new element at the start of a large collection. Which data structure is more efficient in terms of memory and speed, and why?

hard

A. Linked List, because it allows quick insertion by changing pointers without shifting elements.

B. Both are equally efficient for insertion at start.

C. Array, because it stores elements contiguously and allows fast insertion at start.

D. Depends on the element value and size.

Solution

1. Step 1: Analyze array insertion at start

   Inserting at the start of an array requires shifting all elements, which is slow and uses extra memory temporarily.

2. Step 2: Analyze linked list insertion at start

   Linked list insertion at start only changes the head pointer and new node's next pointer, which is fast and uses minimal extra memory.

3. Final Answer:

   Linked List, because it allows quick insertion by changing pointers without shifting elements. -> Option A

4. Quick Check:

   Linked list insertion at start is faster and memory efficient [OK]

Hint: Linked list inserts at start fast; arrays shift all elements [OK]

Common Mistakes:

• Assuming arrays insert at start quickly
• Ignoring shifting cost in arrays
• Thinking element value affects insertion speed