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

What is the output of this C code that prints memory addresses of elements in an array and nodes in a linked list?

DSA C

#include <stdio.h>
#include <stdlib.h>

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

int main() {
    int arr[3] = {10, 20, 30};
    printf("Array addresses:\n");
    for (int i = 0; i < 3; i++) {
        printf("%p ", (void*)&arr[i]);
    }
    printf("\nLinked list addresses:\n");
    Node* head = malloc(sizeof(Node));
    head->data = 10;
    head->next = malloc(sizeof(Node));
    head->next->data = 20;
    head->next->next = malloc(sizeof(Node));
    head->next->next->data = 30;
    head->next->next->next = NULL;
    Node* current = head;
    while (current != NULL) {
        printf("%p ", (void*)current);
        current = current->next;
    }
    printf("\n");
    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.

🧠 Conceptual

intermediate

Memory usage difference between array and linked list

Which statement correctly describes the memory usage difference between an array and a linked list storing the same number of integers?

A Array uses more memory because it stores extra metadata for resizing

B Linked list uses less memory because nodes are allocated only when needed

C Both use the same amount of memory because they store the same number of integers

D Array uses less memory overall because it stores only data elements contiguously without extra pointers

💡 Hint

Consider the extra pointer stored in each linked list node.

Each linked list node stores an integer and a pointer to the next node, increasing memory usage. Arrays store only the data elements contiguously without extra pointers.

🔧 Debug

advanced

Why does this linked list traversal cause a segmentation fault?

Given this code snippet, why does it cause a segmentation fault when traversing the linked list? Node* current = head; while (current != NULL) { printf("%d ", current->data); current = current->next; } head->next was never initialized after malloc.

DSA C

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

Node* head = malloc(sizeof(Node));
head->data = 1;
// head->next is not set

Node* current = head;
while (current != NULL) {
    printf("%d ", current->data);
    current = current->next;
}

A malloc failed and returned NULL, causing segmentation fault

B head->next is uninitialized, so current->next points to garbage causing segmentation fault

C head->data is not initialized, causing segmentation fault

D The while loop condition should be current->next != NULL

💡 Hint

Check what happens when current->next is not set properly.

Since head->next is not initialized, it contains garbage. When current moves to current->next, it accesses invalid memory causing a segmentation fault.

❓ Predict Output

advanced

Output of inserting elements in array vs linked list

What is the output after inserting an element at the beginning of an array and a linked list?

DSA C

#include <stdio.h>
#include <stdlib.h>

int main() {
    int arr[4] = {20, 30, 40, 0};
    // Insert 10 at beginning of array by shifting
    for (int i = 3; i > 0; i--) {
        arr[i] = arr[i-1];
    }
    arr[0] = 10;

    printf("Array after insertion: ");
    for (int i = 0; i < 4; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

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

    Node* head = malloc(sizeof(Node));
    head->data = 20;
    head->next = malloc(sizeof(Node));
    head->next->data = 30;
    head->next->next = malloc(sizeof(Node));
    head->next->next->data = 40;
    head->next->next->next = NULL;

    // Insert 10 at beginning of linked list
    Node* new_node = malloc(sizeof(Node));
    new_node->data = 10;
    new_node->next = head;
    head = new_node;

    printf("Linked list after insertion: ");
    Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
    return 0;
}

A

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

B

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

C

Array after insertion: 10 20 30 0 
Linked list after insertion: 10 20 30 40 

D

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

💡 Hint

Check how insertion at beginning is done differently for array and linked list.

In the array, elements are shifted right to make space at index 0. In the linked list, a new node is created and set as head pointing to old head.

🧠 Conceptual

expert

Why is random access faster in arrays than linked lists?

Why is accessing the 5th element faster in an array than in a linked list?

A Arrays use pointers for each element, making access slower than linked lists

B Linked lists store elements contiguously but require extra pointer dereferencing

C Arrays store elements contiguously, so the address of the 5th element can be calculated directly; linked lists require traversal from the head node

D Linked lists use indexing internally, so access time is the same as arrays

💡 Hint

Think about how memory layout affects access time.

Arrays have contiguous memory, so the address of any element can be computed quickly. Linked lists store nodes scattered in memory, so to reach the 5th element, you must follow 4 pointers sequentially.