Singly Linked List : Graphical and Non - Graphical Way

Follow me

If you want to understand with Graphical Representation click on it

Guide to Singly Linked List Operations

Introduction: Welcome to the World of Linked Lists!

Welcome to your first step in mastering linked lists! This guide will walk you through the essential operations of one of the most fundamental data structures in computer science: the Singly Linked List. To get started, imagine a train. Each coach is connected to the one immediately after it, but no coach knows about the ones further down the line or any that came before it. A Singly Linked List works in exactly the same way—it's a series of "coaches," called nodes, where each one only knows about the very next node in the sequence.

1.0 The Fundamental Idea: What is a Singly Linked List?

A Singly Linked List is a linear data structure composed of a sequence of elements, where each element is a Node.

Every Node in the list has two essential parts:

• DATA: The value the node holds (e.g., the number 10, a name, etc.).
• NEXT: The reference (or "pointer") to the very next node in the sequence.

A typical list might look like this: 10 -> 20 -> 30 -> 40 -> None. The special value None signifies that we've reached the end of the line; there are no more nodes to visit.

This structure gives linked lists a few key advantages over a standard array or list, which is often a developer's first choice for storing a sequence of items.

Linked List Advantage	Why It's Useful for a Developer
Dynamic Size	You don't need to define the size of the list beforehand. It can grow or shrink one node at a time as needed, offering great flexibility.
Easy Insertion/Deletion	Adding or removing elements from the middle of the list is efficient because you only need to update a couple of next pointers, rather than shifting every subsequent element like in an array.
Efficient Memory Use	Memory is allocated for each node only when it's needed. This avoids the wasted space that can occur in arrays, where a large block of memory might be allocated upfront.

Now that we understand the basic structure, let's learn how to perform the core operations that bring a linked list to life.

2.0 Core Operation #1: Inserting a New Node

Insertion is the process of adding a new node to the list. Where you add the node is important, as it affects the performance of the operation. We'll cover the two most common insertion points: the beginning and the end.

2.1 Inserting at the Beginning (insert_at_beginning)

This is the fastest and most efficient way to add a new node to a Singly Linked List. The logic is straightforward and requires just a few steps.

1. Create a new_node with the given data.
2. Point the new_node.next to the list's current head (the first node).
3. Update the head of the list to be the new_node, making it the new first item.

def insert_at_beginning(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

Insight This operation is extremely fast, with a time complexity of O(1). This means its speed is constant and doesn't depend on the size of the list. You don't have to travel through the list at all—you just rearrange the pointers at the very front.

2.2 Inserting at the End (insert_at_end)

To add a node to the end of the list, you must first find the end. This involves traveling from the head all the way to the last node.

1. Create a new_node with the given data.
2. Special Case: If the list is empty (head is None), make the new_node the new head.
3. Standard Case: Start at the head and travel down the list (while temp.next) until you find the very last node (the one whose next is None).
4. Point the last node's next reference to your new_node.

def insert_at_end(self, data):
    new_node = Node(data)
    
    if self.head is None:   # if list is empty
        self.head = new_node
        return
        
    temp = self.head
    while temp.next:
        temp = temp.next
        
    temp.next = new_node

Insight This operation is slower than inserting at the beginning. Its time complexity is O(n), where 'n' is the number of nodes in the list. This is because, in the worst case, you have to visit every single node to find the end before you can perform the insertion.

Now that we can add nodes to our list, the next step is learning how to traverse it to find a specific value.

3.0 Core Operation #2: Searching for a Node (search)

Searching is the process of checking if a specific value exists within any node in the list. This operation, like inserting at the end, requires traversing the list from the beginning.

1. Start at the head of the list.
2. Check if the current node's data matches the value you're looking for.
3. If it's a match, you're done! Return True.
4. If it's not a match, move to the next node (temp = temp.next) and repeat step 2.
5. If you reach the end of the list (None) without a match, the value isn't there. Return False.

def search(self, value):
    temp = self.head
    while temp:
        if temp.data == value:
            return True
        temp = temp.next
    return False

Insight Because searching may require you to visit every node from the beginning to the end, its time complexity is O(n). The time it takes to find an element is directly proportional to the number of nodes ('n') in the list.

Being able to find a node is useful, but the real power comes when we can use that ability to modify the list, such as by removing a specific node.

4.0 Core Operation #3: Deleting a Node (delete)

Deleting a node involves finding it and then "unlinking" it from the sequence. This is done by rerouting the previous node's next pointer to skip over the node you want to remove, effectively cutting it out of the chain.

1. First, check if the node to be deleted is the head. If so, simply update the head to be the next node in the list (self.head = temp.next).
2. If it's not the head, traverse the list, keeping track of both the current node (temp) and the previous one (prev).
3. When you find the node to delete (where temp.data == value), update the prev node's next pointer to skip the current node and point directly to temp.next.
4. If you reach the end of the list without finding the value (temp becomes None), the function simply returns, leaving the list unchanged.

def delete(self, value):
    temp = self.head
    
    # Case 1: The node to delete is the head
    if temp and temp.data == value:
        self.head = temp.next
        return
        
    # Case 2: The node is somewhere else in the list
    prev = None
    while temp and temp.data != value:
        prev = temp
        temp = temp.next
        
    if temp is None:
        return # Value was not found
        
    prev.next = temp.next

Insight Just like searching, deleting a node has a time complexity of O(n). This is because you must first find the node you want to delete, which can require traversing the entire list in the worst-case scenario.

With the ability to insert, search for, and delete nodes, we now have a complete toolkit for managing our list. Let's see these operations in action.

5.0 Putting It All Together: A Live Example

We will now walk through the example code to see how these operations build and modify a list from scratch.

1. Action: ll.insert_at_beginning(30) ll.insert_at_beginning(20) ll.insert_at_beginning(10)
   • List becomes: 10 -> 20 -> 30 -> None
2. Action: ll.insert_at_end(40) ll.insert_at_end(50)
   • List becomes: 10 -> 20 -> 30 -> 40 -> 50 -> None
3. Action: ll.search(30)
   • Result: True
4. Action: ll.search(100)
   • Result: False
5. Action: ll.delete(20)
   • List becomes: 10 -> 30 -> 40 -> 50 -> None

These examples demonstrate how a few simple pointer manipulations can create, modify, and query a flexible data structure.

6.0 Conclusion: Your Key Takeaways

After walking through the definition and core operations of a Singly Linked List, here are the most important concepts to remember.

• Nodes are the building blocks: A linked list is simply a chain of Node objects. Each node contains a piece of data and a next pointer that holds the chain together.
• Operations involve pointer manipulation: At their core, inserting, deleting, and searching are all about changing where the next pointers are aimed or following them from one node to the next.
• Performance varies by operation: Operations at the beginning of the list are incredibly fast (O(1)), while any operation that requires traveling to the end or middle of the list depends on its length (O(n)).

Congratulations on learning the fundamentals of Singly Linked Lists! You now have a solid foundation for understanding more complex data structures.