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.

Practice

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

easy

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

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

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

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

Solution

1. Step 1: Understand array memory layout

   Arrays store elements in contiguous memory blocks, meaning all elements are next to each other.

2. Step 2: Understand linked list memory layout

   Linked list nodes are allocated separately and linked by pointers, so they can be scattered anywhere in memory.

3. Final Answer:

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

4. Quick Check:

   Array = contiguous, Linked List = scattered [OK]

Hint: Arrays use continuous memory; linked lists use scattered nodes [OK]

Common Mistakes:

• Thinking linked list nodes are stored contiguously
• Confusing array and linked list memory layouts
• Assuming both use the same memory pattern

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

easy

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

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

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

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

Solution

1. Step 1: Check pointer to next node type

   The next pointer must be of type 'struct Node*' to point to the next node's address.

2. Step 2: Validate struct syntax

   Using 'struct Node* next;' inside the struct is correct. Using 'Node* next;' without typedef before is invalid here.

3. Final Answer:

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

4. Quick Check:

   Pointer to struct Node = struct Node* [OK]

Hint: Use 'struct Node*' inside struct before typedef completes [OK]

Common Mistakes:

• Using 'int* next' instead of pointer to struct
• Using 'Node* next' before typedef is complete
• Declaring 'struct Node next' causing infinite size

3. Consider the following C code snippet:

int arr[3] = {10, 20, 30};
struct Node {
  int data;
  struct Node* next;
};
struct Node n1 = {10, NULL};
struct Node n2 = {20, NULL};
n1.next = &n2;
printf("%d %d\n", arr[1], n1.next->data);

What is the output?

medium

A. 20 20

B. 10 20

C. 20 10

D. 10 10

Solution

1. Step 1: Identify arr[1] value

   arr[1] is the second element of array, which is 20.

2. Step 2: Identify n1.next->data value

   n1.next points to n2, whose data is 20.

3. Final Answer:

   20 20 -> Option A

4. Quick Check:

   arr[1] = 20, n1.next->data = 20 [OK]

Hint: Array index 1 and linked list next node data both 20 [OK]

Common Mistakes:

• Confusing array index starting at 0
• Misreading pointer access syntax
• Assuming n1.next->data is 10 instead of 20

4. The following code attempts to create a linked list node but causes a runtime error. What is the main issue?

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

struct Node* createNode(int val) {
  struct Node node;
  node.data = val;
  node.next = NULL;
  return &node;
}

medium

A. Not initializing the data field before returning.

B. Missing memory allocation with malloc for the node.

C. Returning address of a local variable which becomes invalid after function ends.

D. Incorrect struct pointer type in return statement.

Solution

1. Step 1: Analyze variable lifetime

   The variable 'node' is local to createNode function and is destroyed when function returns.

2. Step 2: Understand pointer return issue

   Returning address of local variable leads to invalid pointer and undefined behavior.

3. Final Answer:

   Returning address of a local variable which becomes invalid after function ends. -> Option C

4. Quick Check:

   Local variable address returned = invalid pointer [OK]

Hint: Never return address of local variables from functions [OK]

Common Mistakes:

• Assuming pointer remains valid after function ends
• Ignoring need for dynamic memory allocation
• Confusing pointer types in return

5. You want to store 1000 integers and frequently insert and delete elements in the middle. Considering memory layout and performance, which data structure is better and why?

1. Array
2. Linked List

hard

A. Linked List, because it stores elements contiguously for faster access.

B. Array, because contiguous memory improves cache performance despite costly insertions.

C. Array, because it uses less memory than linked list nodes with pointers.

D. Linked List, because scattered nodes allow fast insertions and deletions anywhere.

Solution

1. Step 1: Consider insertion and deletion costs

   Arrays require shifting elements for insert/delete in middle, which is slow.

2. Step 2: Consider linked list advantages

   Linked lists allow quick insert/delete by changing pointers without shifting elements.

3. Step 3: Consider memory layout tradeoff

   Linked list nodes are scattered, which may reduce cache speed but improve insertion/deletion speed.

4. Final Answer:

   Linked List, because scattered nodes allow fast insertions and deletions anywhere. -> Option D

5. Quick Check:

   Fast insert/delete middle = Linked List [OK]

Hint: Linked list excels at fast insert/delete in middle despite scattered memory [OK]

Common Mistakes:

• Choosing array for fast insert/delete in middle
• Ignoring pointer overhead in linked list
• Assuming linked list stores elements contiguously