Why Linked List Exists and What Problem It Solves in DSA C - Challenge Your Understanding

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why Use a Linked List Instead of an Array?

Imagine you want to store a list of items but you don't know how many items there will be, and you want to add or remove items often. Why might a linked list be better than an array in this case?

A Because linked lists can grow and shrink easily without moving other items, while arrays have fixed size or need costly resizing.

B Because arrays use pointers to connect items, making them slower to access than linked lists.

C Because arrays cannot store numbers, only linked lists can.

D Because linked lists store items in continuous memory, making them faster to access than arrays.

💡 Hint

Think about what happens when you add or remove items in an array versus a linked list.

Arrays have a fixed size or need to be resized, which involves copying all items to a new space. Linked lists use nodes connected by pointers, so adding or removing nodes is easy and does not require moving other items.

❓ Predict Output

intermediate

Output of Adding Nodes in a Linked List

What will be the printed linked list after running this C code that adds nodes at the front?

DSA C

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

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

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

int main() {
    Node* head = NULL;
    for (int i = 1; i <= 3; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = i;
        newNode->next = head;
        head = newNode;
    }
    printList(head);
    return 0;
}

A 1 -> 2 -> 3 -> NULL

B NULL -> 1 -> 2 -> 3

C 3 -> 2 -> 1 -> NULL

D 3 -> 1 -> 2 -> NULL

💡 Hint

Nodes are added at the front, so the last added node becomes the new head.

Each new node is added before the current head, so the list order is reversed from insertion order: 3, then 2, then 1.

🔧 Debug

advanced

Why Does This Linked List Code Crash?

Consider this code snippet that tries to traverse a linked list. Why does it crash?

DSA C

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

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

A Because the loop condition skips printing the last node, and accessing head->next when head is NULL causes a crash.

B Because the code uses printf incorrectly without a format specifier.

C Because the struct Node is missing a semicolon after its definition.

D Because the function traverse is missing a return statement.

💡 Hint

Think about what happens when the list has only one node or when head becomes NULL.

The loop condition checks head->next != NULL, so when head is the last node, it stops before printing it. Also, if head is NULL, accessing head->next causes a crash. The loop should check head != NULL instead.

❓ Predict Output

advanced

Result of Removing a Node from a Linked List

What is the linked list after removing the node with value 2 from this list?

DSA C

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

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

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

Node* removeNode(Node* head, int val) {
    Node* temp = head;
    Node* prev = NULL;
    while (temp != NULL && temp->data != val) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return head;
    if (prev == NULL) {
        head = temp->next;
    } else {
        prev->next = temp->next;
    }
    free(temp);
    return head;
}

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 1;
    head->next = (Node*)malloc(sizeof(Node));
    head->next->data = 2;
    head->next->next = (Node*)malloc(sizeof(Node));
    head->next->next->data = 3;
    head->next->next->next = NULL;

    head = removeNode(head, 2);
    printList(head);
    return 0;
}

A 1 -> NULL

B 1 -> 2 -> 3 -> NULL

C 2 -> 3 -> NULL

D 1 -> 3 -> NULL

💡 Hint

Removing node with value 2 means it should no longer appear in the list.

The node with value 2 is found and removed by adjusting the previous node's next pointer. The list becomes 1 -> 3 -> NULL.

🧠 Conceptual

expert

Why Linked Lists Solve Memory Fragmentation Problems

Memory fragmentation happens when free memory is split into small pieces scattered around. How does a linked list help solve this problem compared to arrays?

A Because linked lists use continuous memory blocks, they prevent fragmentation by keeping data together.

B Because linked lists store nodes anywhere in memory and connect them with pointers, they do not require continuous memory blocks like arrays do.

C Because arrays can grow dynamically without moving data, they solve fragmentation better than linked lists.

D Because linked lists store all data in a single large block, they avoid fragmentation.

💡 Hint

Think about how linked list nodes are stored in memory compared to arrays.

Linked lists allocate nodes individually anywhere in memory and link them with pointers. This flexibility avoids the need for large continuous memory blocks, reducing fragmentation issues common with arrays.