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

Mental Model

Arrays store items one after another in a single block of 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

[1][2][3]

Why: Array elements are placed next to each other in memory for fast access

Step 2: Visualize linked list nodes stored separately with pointers

1 -> 2 -> 3 -> null

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

Step 3: Note array uses index to access elements directly

[1][2][3]

Why: Indexing allows quick jump to any element in array

Step 4: Note linked list requires following pointers to reach elements

1 -> 2 -> 3 -> null

Why: Must follow links one by one to find an element in linked list

Result:

Array memory: [1][2][3] contiguous
Linked list memory: nodes scattered but linked 1 -> 2 -> 3 -> null

Annotated Code

DSA Typescript

class ListNode {
  value: number;
  next: ListNode | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
  }
}

function createLinkedList(arr: number[]): ListNode | null {
  if (arr.length === 0) return null;
  const head = new ListNode(arr[0]);
  let current = head;
  for (let i = 1; i < arr.length; i++) {
    current.next = new ListNode(arr[i]);
    current = current.next;
  }
  return head;
}

function printArray(arr: number[]): void {
  console.log(arr.map(x => `[${x}]`).join(''));
}

function printLinkedList(head: ListNode | null): void {
  let curr = head;
  let result = '';
  while (curr !== null) {
    result += curr.value + ' -> ';
    curr = curr.next;
  }
  result += 'null';
  console.log(result);
}

const array = [1, 2, 3];
const linkedList = createLinkedList(array);

printArray(array);
printLinkedList(linkedList);

for (let i = 1; i < arr.length; i++) { current.next = new ListNode(arr[i]); current = current.next; }

Build linked list nodes one by one, linking each to the next

console.log(arr.map(x => `[${x}]`).join(''));

Print array elements in contiguous format

while (curr !== null) { result += curr.value + ' -> '; curr = curr.next; }

Traverse linked list nodes following pointers to print values

Output

[1][2][3]

1 -> 2 -> 3 -> null

Complexity Analysis

Time: O(n) because we visit each element once to print or build the linked list

Space: O(n) because both array and linked list store n elements

vs Alternative: Array uses contiguous memory for fast direct access; linked list uses scattered memory with pointers allowing flexible size but slower access

Edge Cases

empty array or empty linked list

No elements to store or print; functions handle empty input gracefully

DSA Typescript

if (arr.length === 0) return null;

When to Use This Pattern

When a problem involves understanding how data is stored or accessed in memory, compare arrays and linked lists to decide which fits best for speed or flexibility.

Common Mistakes

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

Mistake: Assuming array elements require pointers to connect
Fix: Arrays use index positions and store elements contiguously without pointers

Summary

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

Use arrays for fast direct access and linked lists for flexible size and easy insertions

The key insight is arrays use continuous memory blocks while linked lists use scattered nodes connected by pointers

Practice

1. Which of the following best describes the memory layout of an array compared to a linked list?

easy

A. Array stores elements in contiguous memory locations; linked list stores elements scattered with pointers.

B. Array stores elements scattered with pointers; linked list stores elements in contiguous memory locations.

C. Both array and linked list store elements in contiguous memory locations.

D. Both array and linked list store elements scattered randomly without pointers.

Solution

1. Step 1: Understand array memory layout

   An array stores all its elements one after another in a continuous block of memory.

2. Step 2: Understand linked list memory layout

   A linked list stores each element separately in memory, with each element pointing to the next, so elements are scattered.

3. Final Answer:

   Array stores elements in contiguous memory locations; linked list stores elements scattered with pointers. -> Option A

4. Quick Check:

   Array = contiguous, Linked list = scattered with pointers [OK]

Hint: Remember: arrays are continuous, linked lists use pointers [OK]

Common Mistakes:

• Confusing which data structure uses contiguous memory
• Thinking linked list elements are stored contiguously
• Ignoring the role of pointers in linked lists

2. Which TypeScript syntax correctly declares a linked list node with a value and a next pointer?

easy

A. class Node { value: number; next: number; }

B. class Node { value: number; next: Node | null; }

C. class Node { value: number; next: Node[]; }

D. class Node { value: number; next: undefined; }

Solution

1. Step 1: Identify correct type for next pointer

   The next pointer should be either another Node or null if it is the last node.

2. Step 2: Check each option's next type

   class Node { value: number; next: Node | null; } uses Node | null, which is correct. Others use incorrect types like number, array, or undefined.

3. Final Answer:

   class Node { value: number; next: Node | null; } -> Option B

4. Quick Check:

   Next pointer type = Node or null [OK]

Hint: Next pointer must be Node or null, not a number or array [OK]

Common Mistakes:

• Using number type for next pointer
• Using array type for next pointer
• Not allowing null for the last node

3. Consider this TypeScript code creating an array and a linked list with 3 elements each. What is the output of printing their first elements' values?

medium

A. Array first element: 10, Linked list first element: undefined

B. Array first element: undefined, Linked list first element: undefined

C. Array first element: undefined, Linked list first element: 10

D. Array first element: 10, Linked list first element: 10

Solution

1. Step 1: Understand array initialization

   The array is initialized with [10, 20, 30], so first element is 10.

2. Step 2: Understand linked list initialization

   The linked list nodes are created with values 10, 20, 30 linked properly, so first node's value is 10.

3. Final Answer:

   Array first element: 10, Linked list first element: 10 -> Option D

4. Quick Check:

   Both first elements = 10 [OK]

Hint: Both structures hold first element value directly [OK]

Common Mistakes:

• Assuming linked list first element is undefined
• Confusing array indexing with linked list pointers
• Not linking nodes correctly in linked list

4. This TypeScript code tries to traverse a linked list but throws an error. What is the mistake?

let current: Node | null = head;
while (current.next !== null) {
  console.log(current.value);
  current = current.next;
}

medium

A. The loop condition should be current !== null.

B. The code should use a for loop instead of while.

C. The variable current should not be nullable.

D. The loop misses printing the last node's value.

Solution

1. Step 1: Analyze loop condition

   The loop checks current.next !== null, so it stops before last node.

2. Step 2: Correct loop condition for full traversal

   Loop should check current !== null to include last node and avoid errors when current is null.

3. Final Answer:

   The loop condition should be current !== null. -> Option A

4. Quick Check:

   Traverse until current is null [OK]

Hint: Loop until current is null, not current.next [OK]

Common Mistakes:

• Stopping loop before last node
• Dereferencing null pointer causing error
• Confusing loop conditions for linked list traversal

5. You want to insert an element in the middle of a large dataset. Which data structure is more memory efficient and why? Array vs Linked List

hard

A. Both use the same memory because they store the same data.

B. Array is more memory efficient because it uses contiguous memory without extra pointers.

C. Linked list is less memory efficient because it stores extra pointers for each element.

D. Linked list is more memory efficient because it stores only used nodes with pointers.

Solution

1. Step 1: Understand memory use in arrays

   Arrays store elements contiguously without extra pointers, so no overhead per element.

2. Step 2: Understand memory use in linked lists

   Linked lists store each element plus a pointer to the next, adding extra memory per node.

3. Step 3: Compare memory efficiency for insertion

   Although linked lists allow easy insertion, they use more memory due to pointers, making them less memory efficient.

4. Final Answer:

   Linked list is less memory efficient because it stores extra pointers for each element. -> Option C

5. Quick Check:

   Pointers add memory overhead in linked lists [OK]

Hint: Pointers add memory overhead; arrays store data compactly [OK]

Common Mistakes:

• Assuming linked list uses less memory due to dynamic size
• Ignoring pointer memory overhead
• Confusing insertion ease with memory efficiency