Linked Lists in C

# CHAPTER 22

Linked Lists in C #

1. Introduction #

2. Learning Objectives #

• Explain what a Node is.

• Understand the difference between an Array and a Linked List.

• Create and link Nodes dynamically.

• Traverse a Linked List.

• Implement basic insertion.

3. What is a Node? #

1. 1. Data: The actual value being stored (e.g., an integer).

1. 2. Next Pointer: A pointer holding the memory address of the *next* Node in the list.

struct Node {
    int data;
    struct Node *next; // Pointer to a struct of the same type!
};

4. Creating a Linked List #

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

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

int main() {
    // 1. Declare pointers for the nodes
    struct Node *head = NULL;
    struct Node *second = NULL;
    struct Node *third = NULL;

    // 2. Allocate memory in the Heap
    head = (struct Node*) malloc(sizeof(struct Node));
    second = (struct Node*) malloc(sizeof(struct Node));
    third = (struct Node*) malloc(sizeof(struct Node));

    // 3. Assign data and link them
    head->data = 10;
    head->next = second; // Link first to second

    second->data = 20;
    second->next = third; // Link second to third

    third->data = 30;
    third->next = NULL; // Mark the end of the list

    return 0;
}

5. Visualizing the Linked List #

HEAD (ptr) 
   |
   v
+------+---------+      +------+---------+      +------+------+
| 10   | 0x500   | ---> | 20   | 0x800   | ---> | 30   | NULL |
+------+---------+      +------+---------+      +------+------+
 Address: 0x200          Address: 0x500          Address: 0x800

6. Traversing the List #

void printList(struct Node *n) {
    while (n != NULL) {
        printf("%d -> ", n->data);
        n = n->next; // Move to the next node
    }
    printf("NULL\n");
}
// Call inside main: printList(head);
// Output: 10 -> 20 -> 30 -> NULL

7. Inserting a Node at the Beginning #

// Note: We pass a pointer to a pointer (**head_ref) because we are changing where 'head' points!
void insertAtFront(struct Node **head_ref, int new_data) {
    // 1. Allocate new node
    struct Node *new_node = (struct Node*) malloc(sizeof(struct Node));
    
    // 2. Put in the data
    new_node->data = new_data;
    
    // 3. Make next of new node as head
    new_node->next = (*head_ref);
    
    // 4. Move the head to point to the new node
    (*head_ref) = new_node;
}

// Call inside main: insertAtFront(&head, 5);

8. Array vs. Linked List #

9. Common Mistakes #

• Losing the Head: If you do head = head->next; to traverse the list, you have permanently lost the start of your list (Memory Leak!). Always use a temporary pointer struct Node *temp = head; for traversal.

• Forgetting NULL: If the last node's next pointer isn't set to NULL, traversal loops will run off into garbage memory and crash.

• Not passing pointer-to-pointer: If a function needs to change the head pointer itself, you must pass &head (a struct Node ).

12. Interview Questions #

• Q: Explain the difference between Singly, Doubly, and Circular linked lists.

• Q: How would you detect a cycle (infinite loop) in a linked list? (Hint: Floyd's Tortoise and Hare algorithm).

• Q: Write code to reverse a linked list.

13. Summary #

14. Next Chapter Recommendation #