Memory Layout Comparison Array vs Linked List in DSA Javascript - Complexity Comparison

Time Complexity: Memory Layout Comparison Array vs Linked List

O(1) for array access, O(n) for linked list access

Understanding Time Complexity

We want to understand how accessing elements differs between arrays and linked lists.

How does the memory layout affect the speed of operations?

Scenario Under Consideration

Analyze the time complexity of accessing an element at index i in an array and a linked list.

// Access element at index i in an array
function accessArray(arr, i) {
  return arr[i];
}

// Access element at index i in a linked list
function accessLinkedList(head, i) {
  let current = head;
  let count = 0;
  while (current !== null && count < i) {
    current = current.next;
    count++;
  }
  return current ? current.value : null;
}
    

The first function accesses an element directly by index in an array.

The second function traverses nodes one by one to reach the desired index in a linked list.

Identify Repeating Operations

Look at what repeats when accessing the element.

• Primary operation in array: Direct access by index, no repetition.
• Primary operation in linked list: Loop through nodes one by one until index i.
• How many times: For linked list, loop runs i times; for array, zero loops.

How Execution Grows With Input

Access time in array stays the same no matter the index.

Access time in linked list grows as index i grows.

Index (i)	Array Access Operations	Linked List Access Operations
10	1 (direct)	10 (loop 10 times)
100	1 (direct)	100 (loop 100 times)
1000	1 (direct)	1000 (loop 1000 times)

Pattern observation: Array access time stays constant; linked list access time grows linearly with index.

Final Time Complexity

Time Complexity: O(1) for array access, O(n) for linked list access

This means accessing an element by index is instant in arrays but takes longer as the index grows in linked lists.

Common Mistake

[X] Wrong: "Accessing any element in a linked list is as fast as in an array because both store data."

[OK] Correct: Linked lists store elements scattered in memory, so you must follow links one by one, making access slower as you go further.

Interview Connect

Understanding how memory layout affects access speed helps you choose the right data structure for your needs.

This skill shows you can think about performance beyond just code correctness.

Self-Check

"What if the linked list was doubly linked? How would that affect the time complexity of accessing an element by index?"

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