Singly Linked List Operations: CRUD & Reversal

The Anatomy of a Linked List

An array lets you access any element instantly if you know its index, but changing the array's structure is costly. A linked list makes the opposite trade-off. It excels at structural changes (insertions and deletions) but requires sequential traversal to access elements.

This fundamental difference arises from its structure. A linked list is composed of nodes. Each node contains two pieces of information:

1. Data: The actual value being stored.
2. Next: A reference (or "pointer") to the next node in the sequence. The final node's next pointer is None (or null), signaling the end of the list.

The video below provides an excellent conceptual overview, contrasting array inefficiencies with the flexibility of linked lists.

As the video explains, this structure gives linked lists their characteristic performance:

• Access by index/value: $O(N)$, because you must traverse the list from the head.
• Insertion/deletion at the beginning: $O(1)$, as it only requires updating the head pointer.
• Insertion/deletion at the end/middle: $O(N)$, because you must first traverse to the desired position.

Building a Linked List in Python

Let's translate this concept into Python code. Your experience with object-oriented programming in Django will be helpful here, as we'll define classes to represent the list's structure.

We'll start with the Node, the basic building block.

Here is the essential code for our Node and SinglyLinkedList classes. We will build upon the SinglyLinkedList class by adding methods for its core operations.

class Node:
    """An object for storing a single node of a linked list."""
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    """A class for the linked list itself."""
    def __init__(self):
        self.head = None




    # We will add other methods like print, insert, delete, etc. here.

Insertion Operations

Insertion involves creating a new node and carefully rearranging pointers to place it correctly within the list.

1. Inserting at the Beginning (Prepend)

This is the most efficient insertion operation in a singly linked list.

1. Create a new node with the given data.
2. Set the next pointer of the new node to point to the current head of the list.
3. Update the list's head to be the new node.

This sequence of pointer updates takes constant time, $O(1)$.

The following video demonstrates a practical implementation of this method.

2. Inserting at the End (Append)

To insert at the end, you must first traverse the list to find the last node.

1. If the list is empty, the new node simply becomes the head.
2. If the list is not empty, start at the head and follow the next pointers until you reach the last node (the one whose next is None).
3. Set the next pointer of this last node to the new node.

Because this requires traversing the entire list, its time complexity is $O(N)$.

3. Inserting at a Specific Position

This is a generalization of the previous two cases and is also an $O(N)$ operation.

1. Handle edge cases: check for an invalid index or insertion at the beginning (index 0).
2. Traverse the list to the node just before the target position (i.e., to index i-1).
3. Create the new node.
4. Set the new node's next pointer to the next of the node at i-1.
5. Update the next pointer of the node at i-1 to point to the new node.

Deletion Operation

Deleting a node also requires careful pointer manipulation to "bypass" the node being removed. To delete a node at index i, you must traverse to the node at i-1 and set its next pointer to the node at i+1 (which is node_i.next).

Key steps for deleting a node at a given index:

1. Handle edge cases: invalid index or deleting the head node (index 0).
2. Traverse to the node at index i-1.
3. Update the next pointer of this node to current.next.next, effectively unlinking the node at index i.

Python's garbage collector will automatically reclaim the memory of the unlinked node.

Reversal: The Classic Interview Problem

Reversing a singly linked list is a quintessential coding interview question. It tests your grasp of pointer manipulation under pressure. You need to be ableto solve it both iteratively and recursively.

1. Iterative Reversal

The iterative approach is generally preferred in an interview setting because it's more space-efficient. It uses a three-pointer technique to walk down the list and reverse the links one by one.

• prev: Tracks the previous node, which will become the next node for curr. Initially None.
• curr: The current node being processed. Initially the head.
• temp_next: A temporary variable to store the next node before we overwrite curr.next.

The process within the loop is:

1. temp_next = curr.next (Save the next node)
2. curr.next = prev (Reverse the pointer)
3. prev = curr (Advance the prev pointer)
4. curr = temp_next (Advance the curr pointer)

The loop continues until curr becomes None. The new head of the reversed list will be prev.

2. Recursive Reversal

The recursive solution can be more concise but is less intuitive for many. It also uses more memory due to the function call stack. The core idea is to solve a subproblem:

1. Base Case: If the list is empty or has only one node, it's already reversed. Return the head.
2. Recursive Step:
   • Recursively call the function on the rest of the list (head.next). This will reverse the entire tail of the list and return its new head (new_head).
   • Now, head is a single node pointing to the last node of the original list. The reversed tail is disconnected.
   • To connect head to the end of the reversed tail, we set head.next.next = head.
   • Finally, we must break the original forward link by setting head.next = None.
   • Return new_head up the call stack.

To solidify these two approaches, the following article provides a direct comparison.

Conclusion

In this lesson, we took a deep dive into the implementation of singly linked lists, one of the most fundamental data structures. You learned how its node-based, pointer-linked structure provides flexibility for insertions and deletions at the cost of slower, sequential access compared to an array.

Key Takeaways:

• A singly linked list consists of nodes, each containing data and a next pointer to the subsequent node.
• Insertion and deletion at the beginning are $O(1)$ operations, as they only require updating the head pointer.
• Operations in the middle or at the end are $O(N)$ because they require traversing the list from the head.
• Reversing a linked list is a classic problem with two main solutions:
  • Iterative: Uses a three-pointer approach (prev, curr, temp_next), has $O(1)$ space complexity, and is generally preferred.
  • Recursive: Solves the problem by reversing a sub-list and re-attaching the head. It is often more concise but has $O(N)$ space complexity due to the call stack.

You now have the foundational skills for manipulating linked lists. In our next lesson, we will build upon this by exploring the fast and slow pointer technique, a powerful pattern for solving common linked list problems like cycle detection and finding the middle element.