Linked Lists: Types, Operations, and Implementations

Core Concepts: What is a Linked List?

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)
• Link/Pointer (address of the next node)

Unlike arrays, linked lists allow dynamic memory allocation (no fixed size) and efficient insertions/deletions (no shifting).

Why Use Linked Lists?

Types of Linked Lists

1. Singly Linked List

• Each node points only to the next node.
• Tail node’s next is NULL.

graph LR
    A["Node1\n| Data | Next →"] --> B["Node2\n| Data | Next →"]
    B --> C["Node3\n| Data | Next →"]
    C --> D["NULL"]

Operations:

• Insert at Head: O(1)
• Insert at Tail: O(n) (traverse to end)
• Delete: O(1) if head is known, else O(n).

2. Doubly Linked List

• Each node has two pointers: next and prev.
• Tail’s next is NULL; Head’s prev is NULL.

Advantages:

• Bidirectional traversal (forward/backward).
• Easier deletion (no need to track previous node).

Disadvantages:

• Extra memory for prev pointer.

3. Circular Linked List

• Last node points back to the first node (no NULL terminator).
• Types:
  • Singly Circular: Only next pointers.
  • Doubly Circular: next and prev pointers.

Use Case:

• Round-robin scheduling (e.g., CPU task queues).

Real-World Applications

1. eSewa’s Transaction Queue

• Data Structure: Circular Linked List
• How? Transactions are processed in FIFO order. When a user pays a bill, their transaction node is added to the tail of the queue. The system deletes from the head once processed.
• Why Circular? Ensures the queue never "breaks" even after the last node is processed (e.g., wrapping around for new transactions).

2. Khalti’s Payment Processing

• Data Structure: Doubly Linked List
• How? Payments are stored with prev and next pointers to allow:
  • Rollback: If a payment fails, Khalti can traverse backward to refund.
  • Audit Logs: Quick access to previous transactions.

3. NTC’s Train Schedule Management

• Data Structure: Singly Linked List
• How? Train timings are stored as nodes. Inserting a new train (e.g., Arun Express) at the end (tail) is O(n), but deleting a cancelled train (e.g., Midnight Local) from the head is O(1).

Key Operations with Algorithms

1. Insertion in Singly Linked List

At the Beginning (Head)

Code (C):

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

Trace:

At the End (Tail)

Code:

void insertAtTail(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != NULL) temp = temp->next;
    temp->next = newNode;
}

Trace (Insert 50 at tail):

2. Deletion in Doubly Linked List

Delete from Beginning

Code:

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

Trace:

3. Circular Linked List Operations

Insert at End

Code:

void insertAtEnd(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    if (*head == NULL) {
        newNode->next = newNode;
        *head = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != *head) temp = temp->next;
    temp->next = newNode;
    newNode->next = *head;
}

Trace (Insert 30 in circular list with 10, 20):

Comparison Table: Linked List Types

Advantages and Disadvantages

✅ Advantages

1. Dynamic Size: No need to preallocate memory.
2. Efficient Insertions/Deletions: No shifting (unlike arrays).
3. Non-Contiguous Memory: Useful for large datasets.

❌ Disadvantages

1. No Random Access: Must traverse from head.
2. Extra Memory: Stores pointers (overhead).
3. Cache Unfriendly: Poor locality of reference (slower than arrays).

Exam Tip

1. Memorize Operations:
   • Insert at Head: Always O(1) for singly/doubly/circular.
   • Delete from Middle: Requires traversal (O(n)) unless it’s a doubly linked list (can use prev).
2. Draw Diagrams:
   • Examiners love before/after operation visuals. For example:
     • Show a singly linked list with 3 nodes → insert 5 at head → show updated list.
     • Show a circular linked list → delete the only node → show NULL.
3. Pseudocode > Full Code:
   • Write clear steps (like the mermaid flowcharts above) rather than verbose code.
4. Real-World Links:
   • Relate to eSewa queues, Khalti payments, or NTC train schedules in explanations.
5. Common Pitfalls:
   • Forgetting to update prev in doubly linked lists.
   • Not handling NULL cases (e.g., inserting into an empty list).
   • Circular lists with only one node: Its next points to itself.