Singly Linked Lists

# CHAPTER 8

Singly Linked Lists #

1. Introduction #

2. Learning Objectives #

• Write a while loop to traverse a Singly Linked List.

• Execute pointer manipulation to insert new Nodes at the Head, Tail, and Middle.

• Securely delete a Node without breaking the memory chain.

• Solve the "Reverse a Linked List" FAANG interview problem.

3. Traversal (Printing the List) #

// Java Example: Traversal Algorithm
public void displayList(Node head) {
    // 1. Create a temporary pointer! NEVER MOVE THE HEAD!
    Node current = head;
    
    // 2. Loop until the pointer falls off the end (NULL)
    while (current != null) {
        System.out.print(current.data + " -> ");
        
        // 3. The most important line: Move pointer to the next node
        current = current.next; 
    }
    System.out.println("NULL");
}

Time Complexity: O(n). We must visit every single node once.

4. Insertion Algorithms #

#### 4.1 Inserting at the Front (The Head) This is the superpower of Linked Lists. It is instantaneously O(1).

# Python Example: Insert at Head
def insert_at_beginning(self, new_data):
    # 1. Create the new node
    new_node = Node(new_data)
    
    # 2. Point new node's 'next' to the current Head
    new_node.next = self.head
    
    # 3. Officially declare the new node as the permanent Head
    self.head = new_node

#### 4.2 Inserting at the End (The Tail) To insert at the end, you must traverse the entire list to find the final node. This takes O(n) time! *(Note: If you maintain a separate Tail pointer variable in your class, this drops to O(1)!)*

// C++ Example: Insert at End O(n)
void insertAtEnd(Node** head_ref, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = NULL;

    // Edge Case: If list is empty, make new node the head
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }

    // Traverse to the last node
    Node* last = *head_ref;
    while (last->next != NULL) {
        last = last->next;
    }

    // Point the old last node to the brand new node
    last->next = new_node;
}

5. Deletion Algorithms #

Deleting a specific value (e.g., delete the node with data '20'):

1. 1. Traverse the list to find the node *immediately before* the target.

1. 2. Change the previous node's pointer to point to the node *after* the target.

1. 3. The target is now completely disconnected.

// Java Example: Delete by Value
public void deleteNode(int key) {
    Node temp = head, prev = null;

    // Edge Case: If the Head itself holds the key
    if (temp != null && temp.data == key) {
        head = temp.next; // Change head
        return;
    }

    // Traverse to find the key
    while (temp != null && temp.data != key) {
        prev = temp;
        temp = temp.next;
    }

    // If key was not present
    if (temp == null) return;

    // Unlink the node from linked list (Skip it!)
    prev.next = temp.next;
}

6. The Ultimate Interview: Reversing a Linked List #

You need three pointers: prev, current, and next.

# Python Example: Reverse a Linked List (FAANG Standard)
def reverse_list(self):
    prev = None
    current = self.head
    
    while current is not None:
        # 1. Save the next node before we break the link
        next_node = current.next 
        
        # 2. Reverse the pointer! (Point backward to prev)
        current.next = prev 
        
        # 3. Slide the prev pointer forward one step
        prev = current 
        
        # 4. Slide the current pointer forward one step
        current = next_node 
        
    # After loop, 'prev' is sitting on the old Tail. Make it the new Head!
    self.head = prev

7. Complexity Analysis #

8. Common Mistakes #

• Null Pointer Exceptions: The most common error in pointer logic. If you try to execute current.next but current is already NULL, the program will instantly crash. Always check if (current != null) before accessing properties!

• Breaking the Chain during Insertion: If you are inserting B between A and C, and you change A.next = B first, you have lost the memory address of C forever. You must do B.next = C first, and then A.next = B. Order matters absolutely.

9. Best Practices #

• Use a Dummy Node: When solving complex linked list algorithms (like merging two lists), creating a temporary "Dummy" head node drastically simplifies the code and prevents edge-case crashes when dealing with empty lists.

10. Exercises #

1. 1. Write a function to find the exact middle node of a Linked List in a single O(n) pass. *(Hint: Use a Slow Pointer and a Fast Pointer that moves twice as fast).*

1. 2. Walk through the Reversal algorithm on paper with three nodes. Track the prev, curr, and next variables at each step.

11. MCQs with Answers #

13. Interview Preparation #

• *Algorithmic Coding:* "Write an algorithm to detect a 'Cycle' in a Linked List. (A Cycle occurs if the Tail node maliciously points back to a node in the middle of the list, creating an infinite loop)." *(Answer: Use Floyd's Tortoise and Hare algorithm. If the Fast pointer ever equals the Slow pointer, a cycle exists!).*

• *Algorithmic Coding:* "Write an O(n) algorithm to merge two sorted Linked Lists into a single, perfectly sorted Linked List without creating any new Nodes."

Common Pitfalls:

• In whiteboard interviews, constantly talking about updating pointers but forgetting to actually return the *new Head* at the very end of the function! If the calling program doesn't get the new Head, the data is useless.

14. FAQs #

15. Summary #

16. Next Chapter Recommendation #