Linked Lists: Types, Operations, and Applications

TAKEAWAYS:

• Linked lists store data in nodes (data + pointer), enabling dynamic memory allocation without contiguous storage.
• Singly linked lists have one-way traversal (O(n) for random access), while doubly linked lists allow bidirectional traversal (O(1) for backward access).
• Insertion/deletion at the head is O(1) in linked lists (vs. O(n) in arrays), but searching remains O(n) in both.
• Circular linked lists loop back to the first node, useful for round-robin scheduling (e.g., CPU processes).
• Polynomials can be represented as linked lists, where each node stores a coefficient and exponent.
• Memory leaks and dangling pointers are common pitfalls; always update pointers correctly during operations.

---

1. Introduction to Linked Lists

A linked list is a linear data structure where elements (called nodes) are stored in non-contiguous memory locations. Each node contains:

• Data: The value stored (e.g., integer, string).
• Pointer/Link: Address of the next node (or NULL for the last node).

Why Use Linked Lists?

• Dynamic size: No need to preallocate memory (unlike arrays).
• Efficient insertions/deletions: O(1) at the head (vs. O(n) in arrays).
• No memory wastage: Allocates only what is needed.

Comparison: Arrays vs. Linked Lists

---

2. Types of Linked Lists

A. Singly Linked List

• Each node points to the next node.
• Traversal: Only forward (head → tail).
• Example:

  Head → |Data| → |Data| → |Data| → NULL
  

B. Doubly Linked List

• Each node has two pointers: next and prev.
• Traversal: Bidirectional (head ↔ tail).
• Example:

  Head ← |Data| → |Data| ← |Data| → NULL
  

C. Circular Linked List

• The last node points back to the head, forming a loop.
• Types:
  • Singly circular: Only next pointers loop.
  • Doubly circular: Both next and prev loop.
• Use Case: Round-robin scheduling (e.g., CPU task allocation).

---

---

3. Operations on Linked Lists

A. Traversal

• Visit each node sequentially from the head to the tail.
• Time Complexity: O(n).

Example (Singly Linked List):

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

Trace:

---

B. Insertion

1. At the Head (O(1)):

   • Create a new node.
   • Point its next to the current head.
   • Update head to the new node.

2. At the Tail (O(n) for singly, O(1) for doubly):

   • Traverse to the last node.
   • Insert the new node after it.

3. After a Given Node (O(1) if node is known):

   • Adjust pointers of the given node and the new node.

Example (Insert at Head):

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

State After Insertion (10 → 20 → 30):

Before: NULL
After:  |20| → |10| → |30| → NULL

---

---

C. Deletion

1. At the Head (O(1)):

   • Move head to head->next.
   • Free the old head.

2. At the Tail (O(n) for singly, O(1) for doubly):

   • Traverse to the second-last node.
   • Free the last node.

3. After a Given Node (O(1) if node is known):

   • Bypass the node to delete by updating pointers.

Example (Delete at Head):

void deleteAtHead(Node** head) {
    if (*head == NULL) return;
    Node* temp = *head;
    *head = (*head)->next;
    free(temp);
}

State After Deletion (Original: 10 → 20 → 30):

Before: |10| → |20| → |30| → NULL
After:  |20| → |30| → NULL

---

4. Applications of Linked Lists

A. Real-World Examples

1. eSewa (Nepal):

   • Undo/Redo Operations: Linked lists store transaction history, allowing users to revert to previous states efficiently.
   • How: Each transaction is a node. undo() moves to the previous node; redo() moves forward.

2. Pathao (Ride-Hailing App):

   • Driver Assignment Queue: A circular linked list manages drivers in a round-robin fashion to assign rides fairly.
   • How: Each driver is a node. The system picks the next node in the loop for assignment.

3. Music Playlists (Spotify, Gaana):

   • Song Sequencing: Doubly linked lists allow shuffling (bidirectional traversal) and skipping songs.
   • How: prev and next pointers enable O(1) jumps between songs.

4. Memory Management (Operating Systems):

   • Free Memory Blocks: Linked lists track available memory chunks for dynamic allocation (e.g., malloc in C).
   • How: Each block is a node. The OS merges adjacent free blocks to reduce fragmentation.

5. Polynomial Representation (Math Applications):

   • Example: Represent $3x^2+5x+7$ as:

     |5| → |7| → |3| (coefficients)
     |2| → |1| → |0| (exponents)
     

   • Operations: Addition/subtraction merges like terms by traversing lists.

---

B. Polynomial Representation

A polynomial like $P(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+...+a_0$ can be stored as:

• Node Structure:

  struct PolyNode {
      int coeff;
      int exp;
      struct PolyNode* next;
  };
  

• Example:

  3x² + 5x + 7 → |3| → |5| → |7|
                   |2|   |1|   |0|
  

Addition of Two Polynomials:

PolyNode* addPoly(PolyNode* poly1, PolyNode* poly2) {
    PolyNode* result = NULL;
    while (poly1 && poly2) {
        if (poly1->exp > poly2->exp) {
            insertAtTail(&result, poly1->coeff, poly1->exp);
            poly1 = poly1->next;
        } else if (poly1->exp < poly2->exp) {
            insertAtTail(&result, poly2->coeff, poly2->exp);
            poly2 = poly2->next;
        } else {
            int sum = poly1->coeff + poly2->coeff;
            if (sum != 0) insertAtTail(&result, sum, poly1->exp);
            poly1 = poly1->next;
            poly2 = poly2->next;
        }
    }
    // Add remaining terms
    while (poly1) { insertAtTail(&result, poly1->coeff, poly1->exp); poly1 = poly1->next; }
    while (poly2) { insertAtTail(&result, poly2->coeff, poly2->exp); poly2 = poly2->next; }
    return result;
}

Trace (Add $3x^2+5x+7$ and $2x^2+4x+1$):

Final Result: $5x^2+9x+8$

---

5. Advantages and Disadvantages

---

6. Common Pitfalls and Best Practices

1. Memory Leaks:

   • Forgetting to free() deleted nodes.
   • Fix: Always free memory after deletion.

2. Dangling Pointers:

   • Losing the head pointer (e.g., head = head->next without saving the old head).
   • Fix: Use temporary pointers during operations.

3. Incorrect Pointer Updates:

   • Example: Forgetting to update prev in doubly linked lists.
   • Fix: Write helper functions for common operations.

4. Off-by-One Errors:

   • Traversal loops that miss the last node or go out of bounds.
   • Fix: Use while (current != NULL) and test edge cases.

---

7. Exam Tip

1. Understand Pointer Arithmetic:

   • Exams often test pointer updates (e.g., "After inserting 5 at the tail, what is head->next->data?").
   • Tip: Draw the linked list before and after each operation.

2. Time Complexity Questions:

   • Compare linked lists vs. arrays for operations like insertion, deletion, and search.
   • Example Question: "Why is insertion at the head O(1) in linked lists but O(n) in arrays?" Answer: Arrays require shifting all elements; linked lists only update one pointer.

3. Code Implementation:

   • Be ready to write insertion/deletion code for singly/doubly linked lists.
   • Common Exam Scenarios:
     • Insert a node after a given node.
     • Delete the nth node from the end.
     • Reverse a linked list.

4. Applications:

   • Link real-world examples (e.g., Pathao’s driver queue) to theoretical concepts.
   • Example Question: "How would you implement an undo feature in a text editor using linked lists?" Answer: Use a doubly linked list where each node represents a state. undo() moves to the previous node; redo() moves forward.

5. Polynomials:

   • Expect questions on adding/subtracting polynomials represented as linked lists.
   • Tip: Practice merging two sorted linked lists (similar to polynomial addition).

6. Edge Cases:

   • Test your code with:
     • Empty lists.
     • Single-node lists.
     • Inserting/deleting at the head/tail/middle.

---

---