Why Linked List Exists and What Problem It Solves in DSA C - See It Work

Why Linked List Exists and What Problem It Solves

📖 Scenario: Imagine you have a row of boxes where you keep your favorite toys. Sometimes you want to add a new toy in the middle or remove one without moving all the others. Using a linked list is like having a chain of boxes where each box knows where the next one is, so you can easily add or remove toys without shifting everything.

🎯 Goal: You will create a simple linked list of toy names to understand why linked lists are useful. You will see how adding toys one by one works and how the list looks after adding them.

📋 What You'll Learn

Create a linked list node structure with a toy name and a pointer to the next node

Create the first node with the toy name "Car"

Add two more nodes with toy names "Doll" and "Ball" linked together

Print the linked list to show the order of toys

💡 Why This Matters

🌍 Real World

Linked lists are used in real life when you want to keep items in order but also want to add or remove items easily, like a playlist of songs or a chain of tasks.

💼 Career

Understanding linked lists is important for software developers because many programs use them to manage data efficiently, especially when the size of data changes often.

1

Create the first linked list node

Define a struct called Node with a char array toy[20] and a pointer next to Node. Then create a variable head of type Node* and allocate memory for it. Set head->toy to "Car" and head->next to NULL.

DSA C

#include 
#include 
#include 

// Define struct Node
// Create head node with toy "Car"
// Your code here

Hint

Use typedef struct Node to define the node. Use malloc to create the first node. Use strcpy to copy the toy name.

2

Add two more nodes to the linked list

Create two new nodes called second and third using malloc. Set their toy values to "Doll" and "Ball" respectively. Link head->next to second and second->next to third. Set third->next to NULL.

DSA C

#include 
#include 
#include 

typedef struct Node {
    char toy[20];
    struct Node* next;
} Node;

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    strcpy(head->toy, "Car");
    head->next = NULL;

    // Create second and third nodes and link them
    // Your code here

    return 0;
}

Hint

Use malloc to create new nodes. Use strcpy to set toy names. Link nodes by setting next pointers.

3

Traverse the linked list to print toy names

Create a pointer current and set it to head. Use a while loop to go through the list until current is NULL. Inside the loop, print the toy name in current->toy followed by " -> ". Move current to current->next.

DSA C

#include 
#include 
#include 

typedef struct Node {
    char toy[20];
    struct Node* next;
} Node;

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    strcpy(head->toy, "Car");
    head->next = NULL;

    Node* second = (Node*)malloc(sizeof(Node));
    strcpy(second->toy, "Doll");
    second->next = NULL;

    Node* third = (Node*)malloc(sizeof(Node));
    strcpy(third->toy, "Ball");
    third->next = NULL;

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

    // Traverse and print the list
    // Your code here

    return 0;
}

Hint

Use a while loop to move through the list. Print each toy name followed by an arrow. End with printing "NULL".

4

Print the final linked list output

Run the program to print the linked list showing the toys in order: "Car -> Doll -> Ball -> NULL".

DSA C

#include 
#include 
#include 

typedef struct Node {
    char toy[20];
    struct Node* next;
} Node;

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    strcpy(head->toy, "Car");
    head->next = NULL;

    Node* second = (Node*)malloc(sizeof(Node));
    strcpy(second->toy, "Doll");
    second->next = NULL;

    Node* third = (Node*)malloc(sizeof(Node));
    strcpy(third->toy, "Ball");
    third->next = NULL;

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

    Node* current = head;
    while (current != NULL) {
        printf("%s -> ", current->toy);
        current = current->next;
    }
    printf("NULL\n");

    // Run the program to see output
    // Your code here

    return 0;
}

Hint

Run the program and check the printed output matches the linked list order.

Practice

1. Why do we use a linked list instead of an array in some cases?

easy

A. Because linked lists are faster to access elements by index

B. Because linked lists allow easy insertion and deletion without shifting elements

C. Because linked lists store elements in contiguous memory locations

D. Because linked lists use less memory than arrays always

Solution

1. Step 1: Understand array limitations

   Arrays store elements in continuous memory, so inserting or deleting in the middle requires shifting elements, which is slow.

2. Step 2: Understand linked list advantages

   Linked lists store elements in nodes connected by pointers, so insertion and deletion can be done by changing pointers without shifting.

3. Final Answer:

   Because linked lists allow easy insertion and deletion without shifting elements -> Option B

4. Quick Check:

   Linked list insertion/deletion is easier than array shifting [OK]

Hint: Linked lists avoid shifting elements on insert/delete [OK]

Common Mistakes:

• Thinking linked lists use less memory always
• Believing linked lists store elements contiguously
• Assuming linked lists have faster index access

2. Which of the following is the correct way to declare a node structure for a singly linked list in C?

easy

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

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

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

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

Solution

1. Step 1: Check pointer usage in struct

   In C, to refer to the same struct type inside itself, we use 'struct Node* next;' as a pointer to next node.

2. Step 2: Identify correct syntax

   struct Node { int data; struct Node* next; }; correctly declares 'struct Node* next;' while others either use wrong types or missing 'struct' keyword.

3. Final Answer:

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

4. Quick Check:

   Use 'struct Node* next;' for linked list node pointer [OK]

Hint: Use 'struct Node* next;' to link nodes in C [OK]

Common Mistakes:

• Omitting 'struct' keyword before Node pointer
• Using 'int' instead of pointer for next
• Declaring next as struct instead of pointer

3. What will be the output of the following C code snippet that creates a linked list with two nodes and prints their data?

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

int main() {
  struct Node node1, node2;
  node1.data = 10;
  node1.next = &node2;
  node2.data = 20;
  node2.next = NULL;

  struct Node* ptr = &node1;
  while (ptr != NULL) {
    printf("%d ", ptr->data);
    ptr = ptr->next;
  }
  return 0;
}

medium

A. Compilation error

B. 20 10

C. 10

D. 10 20

Solution

1. Step 1: Understand linked list creation

   node1 points to node2, node2 points to NULL. So list is 10 -> 20 -> NULL.

2. Step 2: Trace the print loop

   Pointer starts at node1, prints 10, moves to node2, prints 20, then NULL ends loop.

3. Final Answer:

   10 20 -> Option D

4. Quick Check:

   Prints nodes in order: 10 then 20 [OK]

Hint: Follow next pointers to print nodes in order [OK]

Common Mistakes:

• Confusing order of nodes
• Forgetting to set node2.next to NULL
• Assuming compilation error due to struct

4. Identify the error in the following code snippet that tries to insert a new node at the beginning of a linked list:

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

void insertAtBeginning(struct Node* head, int value) {
  struct Node* newNode = malloc(sizeof(struct Node));
  newNode->data = value;
  newNode->next = head;
  head = newNode;
}

medium

A. head is passed by value, so the original list head is not updated

B. malloc is not used correctly to allocate memory

C. newNode->next should be NULL instead of head

D. Function should return void* instead of void

Solution

1. Step 1: Check parameter passing

   head is passed by value, so changing head inside function does not affect original head pointer outside.

2. Step 2: Understand pointer update requirement

   To update head, function should take pointer to pointer (struct Node** head) or return new head pointer.

3. Final Answer:

   head is passed by value, so the original list head is not updated -> Option A

4. Quick Check:

   Pointer changes inside function must affect caller [OK]

Hint: Pass pointer to pointer to update head outside function [OK]

Common Mistakes:

• Assuming malloc usage is wrong
• Thinking newNode->next should be NULL
• Confusing function return type

5. You want to store a list of unknown size where frequent insertions and deletions happen anywhere in the list. Which data structure is best and why?

hard

A. Linked list, because it allows efficient insertions and deletions without shifting

B. Array, because it provides fast random access

C. Stack, because it supports last-in-first-out operations

D. Queue, because it supports first-in-first-out operations

Solution

1. Step 1: Analyze requirements

   Unknown size and frequent insertions/deletions anywhere require flexible size and efficient updates.

2. Step 2: Compare data structures

   Arrays have fixed size or costly resizing and require shifting on insert/delete. Stack and queue have restricted access patterns.

3. Step 3: Choose linked list

   Linked list nodes can be inserted or deleted by changing pointers without shifting, and size can grow dynamically.

4. Final Answer:

   Linked list, because it allows efficient insertions and deletions without shifting -> Option A

5. Quick Check:

   Linked list suits dynamic size and frequent insert/delete [OK]

Hint: Use linked list for dynamic size and easy insert/delete [OK]

Common Mistakes:

• Choosing array despite costly shifting
• Confusing stack/queue with general list
• Ignoring dynamic size needs