Linked Lists: Nodes, Types, Operations & Applications

TAKEAWAYS:

• Linked lists store data in nodes linked via pointers, enabling dynamic resizing and efficient insertions/deletions at arbitrary positions.
• Singly linked lists have forward-only traversal, while doubly linked lists allow bidirectional movement, and circular variants loop back to the head.
• Operations like insertion/deletion at the head/tail/nth position require pointer manipulation, with time complexity O(1) for head/tail and O(n) for nth position.
• Applications include browser history (stack-like), undo/redo (stack), and implementing queues (FIFO) or graphs (adjacent nodes).
• Doubly linked lists improve traversal speed but use extra memory for backward pointers.
• Circular linked lists eliminate null terminators, useful in round-robin scheduling (e.g., NTC call centers).

---

1. Introduction to Linked Lists

Linked lists are linear data structures where elements (called nodes) are stored in non-contiguous memory locations. Each node contains:

• Data (value)
• Pointer (address of the next node)

Unlike arrays, linked lists dynamically allocate memory, allowing efficient insertions/deletions without shifting elements.

---

1.1 Node Structure

A node in a linked list typically has:

• data: Stores the value.
• next: Pointer to the next node (for singly linked lists) or prev/next (for doubly linked lists).

---

1.2 Why Linked Lists?

---

2. Types of Linked Lists

2.1 Singly Linked List

• Each node points only to the next node.
• Traversal is unidirectional (head → tail).
• Tail node’s next is null (terminator).

Example: Browser History

• Each visited page is a node.
• Clicking "back" moves to the previous node (LIFO stack-like behavior).

---

2.2 Doubly Linked List

• Each node has two pointers: prev (previous node) and next (next node).
• Enables bidirectional traversal.

Advantages:

• Faster traversal in reverse (e.g., undo operations in text editors).
• Easier to delete a node (access via prev pointer).

Disadvantages:

• Extra memory for prev pointers.
• Slightly slower insertion/deletion due to pointer updates.

---

2.3 Circular Linked List

• Last node points to the head (no null terminator).
• Useful for round-robin scheduling (e.g., NTC call center queues).

a) Singly Circular Linked List

b) Doubly Circular Linked List

Applications:

• Music playlists (loop through songs).
• CPU process scheduling (round-robin).

---

3. Operations on Linked Lists

3.1 Insertion

a) At the Head

• New node’s next → old head.
• Update head to point to new node.

Example: Insert 5 at the head of 1 → 2 → 3.

Before:

1 → 2 → 3 → null

After:

5 → 1 → 2 → 3 → null

b) At the Tail

• Traverse to the last node, update its next.

Example: Insert 4 at the tail of 1 → 2 → 3.

Before:

1 → 2 → 3 → null

After:

1 → 2 → 3 → 4 → null

c) At nth Position

• Traverse to the (n-1)th node, insert new node between it and the nth node.

Example: Insert 4 at position 2 in 1 → 3 → 5.

Before:

1 → 3 → 5 → null

After:

1 → 4 → 3 → 5 → null

---

3.2 Deletion

a) Deleting Head Node

• Move head to the next node.
• Free the old head node.

Example: Delete head from 5 → 1 → 2.

Before:

5 → 1 → 2 → null

After:

1 → 2 → null

b) Deleting Tail Node

• Traverse to the second-last node, update its next to null.

Example: Delete tail from 1 → 2 → 3.

Before:

1 → 2 → 3 → null

After:

1 → 2 → null

c) Deleting nth Node

• Traverse to the (n-1)th node, bypass the nth node.

Example: Delete node at position 2 from 1 → 4 → 3 → 5.

Before:

1 → 4 → 3 → 5 → null

After:

1 → 3 → 5 → null

---

3.3 Searching

• Traverse the list from the head until the target is found or the end is reached.
• Time Complexity: O(n).

def search(node, data):
    while node:
        if node.data == data:
            return True
        node = node.next
    return False

Example: Search for 3 in 1 → 2 → 3 → 4.

Trace:

---

4. Implementing Queues Using Linked Lists

A queue follows FIFO (First-In-First-Out). Linked lists are ideal for dynamic queue operations.

Operations:

1. Enqueue (Insert at Tail):
   • Add a new node at the tail.
2. Dequeue (Remove from Head):
   • Remove the head node.

Example: NTC Call Center Queue

• Customers join the queue (enqueue) and are served in order (dequeue).
• Linked lists dynamically handle variable numbers of customers.

---

5. Advantages and Disadvantages

---

6. Real-World Applications

In the Real World

1. Browser History (Singly Linked List)

   • Each visited page is a node.
   • Clicking "back" follows the next pointer (LIFO stack).
   • Example: Chrome’s back/forward buttons use a linked list to track pages.

2. Undo/Redo in Text Editors (Stack-like Linked List)

   • Each action (e.g., typing, deleting) is a node.
   • Undo moves backward; redo moves forward.
   • Example: Microsoft Word’s undo/redo uses a doubly linked list for bidirectional traversal.

3. OS Process Scheduling (Circular Linked List)

   • Processes are nodes in a circular list.
   • CPU switches to the next process in round-robin fashion.
   • Example: Linux kernel uses circular linked lists for process scheduling.

4. Music Playlists (Circular Linked List)

   • Songs are nodes; playback loops back to the start.
   • Example: Spotify’s shuffle mode uses a circular linked list.

5. Daraz Order Queue (Queue Using Linked List)

   • Orders are enqueued (added to the tail) and dequeued (served in FIFO order).
   • Worked Example:
   • Queue State After Each Step:

     Enqueue Order 101: 101 → null
     Enqueue Order 102: 101 → 102 → null
     Dequeue Order 101: 102 → null
     Enqueue Order 103: 102 → 103 → null
     

   • Time Complexity:
     • Enqueue: O(1) (tail insertion).
     • Dequeue: O(1) (head removal).

---

7. Exam Tip

• Focus on:
  • Pointer manipulation (critical for insertions/deletions).
  • Time complexity (O(1) for head/tail, O(n) for nth position).
  • Real-world analogies (e.g., browser history, queues).
• Common Mistakes:
  • Forgetting to update next/prev pointers during insertion/deletion.
  • Misplacing the null terminator in circular lists.
• Practice:
  • Draw the linked list before/after each operation.
  • Implement insertion/deletion in code and trace it step-by-step.

---

Practice Question (From Past Exams)

Question: How can you implement a queue using a linked list? Explain with an example.

Answer: A queue can be implemented using a linked list by treating the head as the front (for dequeue) and the tail as the rear (for enqueue).

Steps:

1. Enqueue (Insert at Tail):
   • Create a new node.
   • If the queue is empty, set both head and tail to the new node.
   • Otherwise, append the new node to the tail and update tail.
2. Dequeue (Remove from Head):
   • Remove the head node.
   • If the queue becomes empty, set head and tail to null.
   • Otherwise, move head to the next node.

Example: Initialize an empty queue: head = null, tail = null.

1. Enqueue 10:

   head → 10 → null
   tail → 10
   

2. Enqueue 20:

   head → 10 → 20 → null
   tail → 20
   

3. Dequeue:

   head → 20 → null
   tail → 20
   

4. Dequeue (queue becomes empty):

   head = null, tail = null
   

Code Example:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, data):
        new_node = Node(data)
        if self.tail is None:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

    def dequeue(self):
        if self.head is None:
            return None
        temp = self.head
        self.head = temp.next
        if self.head is None:
            self.tail = None
        return temp.data

Trace: