Memory Layout Comparison Array vs Linked List in DSA Javascript - Trade-offs & Analysis

Mental Model

Arrays store items one after another in memory, while linked lists store items scattered in memory with pointers connecting them.

Analogy: Imagine a row of mailboxes (array) all side by side on a street versus houses spread out in a neighborhood connected by roads (linked list).

Array: [1][2][3][4][5]
Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> null

Dry Run Walkthrough

Input: Compare memory layout of array [1, 2, 3] and linked list 1 -> 2 -> 3 -> null

Goal: Understand how elements are stored and connected in memory for both structures

Step 1: Visualize array elements stored contiguously in memory

[1][2][3]

Why: Array elements are placed one after another for fast access by index

Step 2: Visualize linked list nodes scattered in memory with pointers linking them

1 -> 2 -> 3 -> null

Why: Linked list nodes can be anywhere in memory but use pointers to connect

Step 3: Note that array uses less memory overhead, linked list uses extra space for pointers

Array: [1][2][3]
Linked List: 1(ptr) -> 2(ptr) -> 3(ptr) -> null

Why: Pointers add extra memory cost in linked lists

Result:

Array: [1][2][3]
Linked List: 1 -> 2 -> 3 -> null

Annotated Code

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 curr = this.head;
    while (curr.next) {
      curr = curr.next; // advance curr to next node
    }
    curr.next = newNode; // link new node at end
  }

  print() {
    let curr = this.head;
    let result = '';
    while (curr) {
      result += curr.value + ' -> ';
      curr = curr.next; // advance curr to next node
    }
    result += 'null';
    console.log(result);
  }
}

// Array example
const array = [1, 2, 3];
console.log('Array:', array);

// Linked list example
const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
console.log('Linked List:');
list.print();

curr = curr.next; // advance curr to next node

advance curr to next node to reach the end

curr.next = newNode; // link new node at end

attach new node at the end of the list

curr = curr.next; // advance curr to next node

traverse nodes to print all values

Output

Array: [1,2,3]

Linked List:

1 -> 2 -> 3 -> null

Complexity Analysis

Time: O(n) to traverse linked list because we visit each node once; O(1) to access array element by index

Space: Array uses O(n) space for elements only; linked list uses O(n) plus extra O(n) for pointers

vs Alternative: Arrays use less memory and allow fast random access; linked lists use more memory but allow easy insertions/deletions without shifting

Edge Cases

Empty array and empty linked list

Both have no elements; linked list head is null, array length is zero

DSA Javascript

if (!this.head) { this.head = newNode; return; }

Single element array and linked list

Array has one element at index 0; linked list has head node with next null

DSA Javascript

if (!this.head) { this.head = newNode; return; }

When to Use This Pattern

When a problem asks about memory use or access speed differences between data structures, think about arrays vs linked lists because their memory layouts affect performance.

Common Mistakes

Mistake: Assuming linked list elements are stored next to each other in memory like arrays
Fix: Remember linked list nodes can be anywhere in memory and are connected by pointers

Mistake: Ignoring extra memory used by pointers in linked lists
Fix: Account for pointer size when comparing memory usage

Summary

Shows how arrays store elements contiguously while linked lists store nodes scattered with pointers.

Use when you want to understand memory and access differences between arrays and linked lists.

The key insight is arrays have fast index access due to contiguous memory, linked lists have flexible memory use due to pointers.

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