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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of memory addresses in array vs linked list

Given the following C++ code, what is the output pattern of the printed memory addresses?

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

int main() {
    int arr[3] = {10, 20, 30};
    cout << "Array addresses:\n";
    for (int i = 0; i < 3; i++) {
        cout << &arr[i] << " ";
    }
    cout << "\nLinked list addresses:\n";
    Node* n1 = new Node{10, nullptr};
    Node* n2 = new Node{20, nullptr};
    Node* n3 = new Node{30, nullptr};
    n1->next = n2;
    n2->next = n3;
    Node* current = n1;
    while (current != nullptr) {
        cout << current << " ";
        current = current->next;
    }
    cout << endl;
    return 0;
}

A Array addresses are contiguous and increasing; linked list addresses are scattered and not contiguous

B Array addresses are scattered; linked list addresses are contiguous and increasing

C Both array and linked list addresses are contiguous and increasing

D Both array and linked list addresses are scattered and random

💡 Hint

Think about how arrays and linked lists store elements in memory.

Arrays store elements in contiguous memory locations, so their addresses increase sequentially. Linked list nodes are allocated separately on the heap, so their addresses are scattered and not contiguous.

🧠 Conceptual

intermediate

Memory usage difference between array and linked list

Which statement correctly describes the memory usage difference between arrays and linked lists?

A Arrays use less memory overall because they store only data elements; linked lists use extra memory for pointers

B Linked lists use less memory because they allocate nodes only when needed; arrays always allocate fixed size

C Arrays and linked lists use the same amount of memory for the same number of elements

D Linked lists use less memory because pointers are smaller than array elements

💡 Hint

Consider the extra pointer stored in each linked list node.

Each linked list node stores data plus a pointer to the next node, which adds extra memory overhead compared to arrays that store only data elements.

🔧 Debug

advanced

Why does this linked list traversal cause a segmentation fault?

Consider this code snippet for traversing a linked list. Why does it cause a segmentation fault?

DSA C++

struct Node {
    int data;
    Node* next;
};

void printList(Node* head) {
    while (head->next != nullptr) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << head->data << endl;
}

int main() {
    printList(nullptr);
    return 0;
}

A The print statement should be before the loop to avoid null pointer access

B The loop condition should be 'while (head != nullptr)' to avoid dereferencing null pointer

C The code is correct and will not cause segmentation fault

D The linked list nodes are not dynamically allocated, causing invalid memory access

💡 Hint

Check what happens when head points to the last node.

The loop condition 'head->next != nullptr' causes the loop to stop before the last node. Then accessing 'head->data' outside the loop is safe only if head is not null. But if the list is empty or head is null, it causes a segmentation fault. Using 'while (head != nullptr)' safely traverses all nodes.

❓ Predict Output

advanced

Output of inserting elements in array vs linked list

What is the output after inserting element 15 at index 1 in an array and inserting element 15 after the first node in a linked list?

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

int main() {
    int arr[4] = {10, 20, 30, 0};
    // Insert 15 at index 1 in array
    for (int i = 3; i > 1; i--) {
        arr[i] = arr[i-1];
    }
    arr[1] = 15;

    cout << "Array after insertion: ";
    for (int i = 0; i < 4; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // Linked list: 10 -> 20 -> 30
    Node n1 = {10, nullptr};
    Node n2 = {20, nullptr};
    Node n3 = {30, nullptr};
    n1.next = &n2;
    n2.next = &n3;

    // Insert 15 after first node
    Node n_new = {15, nullptr};
    n_new.next = n1.next;
    n1.next = &n_new;

    cout << "Linked list after insertion: ";
    Node* current = &n1;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;

    return 0;
}

A

Array after insertion: 10 15 20 30 
Linked list after insertion: 15 10 20 30 

B

Array after insertion: 10 20 15 30 
Linked list after insertion: 10 20 15 30 

C

Array after insertion: 10 20 30 15 
Linked list after insertion: 10 15 30 20 

D

Array after insertion: 10 15 20 30 
Linked list after insertion: 10 15 20 30 

💡 Hint

Check how insertion shifts elements in array and how pointers change in linked list.

In the array, elements from index 1 onwards shift right to make space for 15 at index 1. In the linked list, the new node with 15 is inserted after the first node, so the order becomes 10 -> 15 -> 20 -> 30.

🧠 Conceptual

expert

Why does linked list have slower random access than array?

Which reason best explains why linked lists have slower random access compared to arrays?

A Arrays use pointers, so they can jump directly to any element, but linked lists cannot

B Linked lists use more memory, so accessing elements takes longer due to cache misses

C Linked lists store elements non-contiguously, so accessing the nth element requires traversing nodes sequentially

D Linked lists store elements contiguously but have extra pointer overhead causing slower access

💡 Hint

Think about how memory layout affects access speed.

Arrays store elements contiguously, allowing direct access by index. Linked lists store nodes scattered in memory, so to access the nth element, you must start at the head and follow pointers sequentially, which is slower.

Practice

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

easy

A. Both array and linked list nodes are scattered randomly in memory.

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

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

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

Solution

1. Step 1: Understand array memory layout

   Arrays store elements in contiguous memory blocks, meaning elements are placed one after another in memory.

2. Step 2: Understand linked list memory layout

   Linked list nodes are allocated dynamically and can be anywhere in memory, connected by pointers.

3. Final Answer:

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

4. Quick Check:

   Array = contiguous, Linked List = scattered [OK]

Hint: Arrays are contiguous; linked lists use pointers to scattered nodes [OK]

Common Mistakes:

• Thinking linked list nodes are contiguous
• Confusing array with linked list memory layout
• Assuming both have same memory layout

2. Which C++ declaration correctly defines a linked list node struct with an integer data and a pointer to the next node?

easy

A. struct Node { int data; Node* next; };

B. struct Node { int data; Node next; };

C. struct Node { int data; Node& next; };

D. struct Node { int data; int* next; };

Solution

1. Step 1: Understand pointer usage in struct

   The next node pointer must be a pointer type to allow linking nodes dynamically.

2. Step 2: Analyze each option

   struct Node { int data; Node next; }; uses Node next (not pointer), invalid. struct Node { int data; Node* next; }; uses Node* next (correct pointer). struct Node { int data; Node& next; }; uses reference Node& next (not suitable for linked list). struct Node { int data; int* next; }; uses int* next (wrong type).

3. Final Answer:

   struct Node { int data; Node* next; }; -> Option A

4. Quick Check:

   Pointer to next node = Node* next [OK]

Hint: Use Node* for next pointer in linked list node struct [OK]

Common Mistakes:

• Using object instead of pointer for next
• Using reference instead of pointer
• Using wrong pointer type

3. Consider the following C++ code snippet that creates an array and a linked list with 3 elements each. What is the output of the memory addresses printed for the array and linked list nodes?

int arr[3] = {10, 20, 30};
struct Node { int data; Node* next; };
Node* n1 = new Node{10, nullptr};
Node* n2 = new Node{20, nullptr};
Node* n3 = new Node{30, nullptr};
n1->next = n2; n2->next = n3;

std::cout << &arr[0] << " " << &arr[1] << " " << &arr[2] << std::endl;
std::cout << n1 << " " << n2 << " " << n3 << std::endl;

medium

A. Both array and linked list addresses are contiguous

B. Array addresses are contiguous; linked list addresses are non-contiguous

C. Array addresses are non-contiguous; linked list addresses are contiguous

D. Both array and linked list addresses are non-contiguous

Solution

1. Step 1: Analyze array memory addresses

   Array elements are stored contiguously, so &arr[0], &arr[1], &arr[2] will be adjacent addresses.

2. Step 2: Analyze linked list node addresses

   The nodes are separately allocated dynamically with new; their addresses (printed as n1, n2, n3) are non-contiguous in memory.

3. Final Answer:

   Array addresses are contiguous; linked list addresses are non-contiguous -> Option B

4. Quick Check:

   Array contiguous, linked list scattered [OK]

Hint: Array addresses are adjacent; linked list nodes scattered [OK]

Common Mistakes:

• Assuming linked list nodes are contiguous
• Confusing variable addresses with pointer values
• Ignoring dynamic allocation behavior

4. The following code attempts to create a linked list of 3 nodes but has a bug related to memory layout. Identify the bug.

struct Node {
  int data;
  Node* next;
};

Node* head = new Node{1, nullptr};
Node* second = new Node{2, nullptr};
Node* third = new Node{3, nullptr};

head->next = second;
second = third;
third->next = nullptr;

medium

A. The line 'second = third;' breaks the link between first and second nodes.

B. The nodes are not allocated dynamically.

C. The next pointers are not set correctly for all nodes.

D. The head pointer is not initialized.

Solution

1. Step 1: Trace pointer assignments

   head->next = second links first node to second node correctly. Then 'second = third;' changes the local second pointer to point to third node, but node2->next remains nullptr. third->next = nullptr sets nothing new.

2. Step 2: Understand impact on linked list

   The next pointer of the second node is never set to the third node, so the list is 1 -> 2 -> null with third node unreachable from head.

3. Final Answer:

   The next pointers are not set correctly for all nodes. -> Option C

4. Quick Check:

   Missing second->next = third [OK]

Hint: Changing pointer variable breaks links; update next pointers instead [OK]

Common Mistakes:

• Confusing pointer variable with node's next pointer
• Ignoring pointer reassignment effect
• Assuming nodes are not dynamically allocated

5. You want to store 1 million integers and frequently access elements by index. Considering memory layout and access speed, which data structure is better and why?

1. Array
2. Linked List

hard

A. Array, because contiguous memory allows fast index access and better cache performance.

B. Linked List, because scattered nodes reduce memory fragmentation and improve access speed.

C. Linked List, because dynamic allocation uses less memory than arrays.

D. Array, because linked lists require extra memory for pointers making them slower.

Solution

1. Step 1: Consider access by index

   Arrays allow direct access by index in O(1) time due to contiguous memory layout.

2. Step 2: Consider memory and cache effects

   Contiguous memory improves cache locality, speeding up access. Linked lists have scattered nodes, causing cache misses and slower access.

3. Final Answer:

   Array, because contiguous memory allows fast index access and better cache performance. -> Option A

4. Quick Check:

   Fast index access = Array with contiguous memory [OK]

Hint: For fast index access, choose arrays due to contiguous memory [OK]

Common Mistakes:

• Assuming linked list is faster for index access
• Ignoring cache locality effects
• Confusing memory fragmentation with access speed