Embarking on the Data Structure Journey: Singly Linked Lists with Python

Welcome, aspiring programmer! Today, we're going to dive into one of the fundamental concepts in computer science: data structures. Think of data structures as powerful tools for organizing and storing information in a computer so that it can be accessed and modified efficiently. Just like a chef needs different containers for different ingredients, a programmer needs various data structures to handle different types of data tasks.

What are Data Structures? An Analogy to Get Started

Why Python for Data Structures?

Python is an excellent choice for learning data structures because of its readability and straightforward syntax. It allows you to focus on the core concepts of how data is organized and manipulated, rather than getting bogged down in complex language-specific details. Its dynamic nature makes it flexible, and you can quickly prototype and test your ideas.

Understanding Linked Lists: Beyond the Array

You're likely familiar with arrays or Python's built-in lists. They store data in contiguous (next to each other) memory locations. This is great for quick access to any element by its index. However, they have a couple of downsides:

• Fixed Size (often): In many languages, arrays have a fixed size; once declared, you can't easily change their capacity without creating a new, larger array and copying all elements. Python lists are dynamic, but adding/removing from the middle can still be costly.
• Costly Insertions/Deletions: If you want to insert an element in the middle of an array, you often have to shift all subsequent elements to make space. Similarly, deleting an element requires shifting elements to fill the gap. This can be slow for large arrays.

Enter Linked Lists! Imagine a chain of paper notes, where each note contains some information and a pointer (an arrow) to the *next* note in the sequence. This is the essence of a linked list.

Singly Linked List: One-Way Street

A Singly Linked List is the simplest form of a linked list. As the name suggests, each node only contains a pointer to the next node. You can only traverse this list in one direction: forward. Think of it like a one-way street or a treasure map where each clue leads you only to the next clue, never back to the previous one.

Building a Singly Linked List in Python

Let's start by defining our fundamental building block: the Node class.

The Node Class

This class will represent each element in our linked list.

class Node:
    def __init__(self, data):
        self.data = data  # The data the node holds
        self.next = None  # A pointer to the next node, initialized to None

Now, let's build the SinglyLinkedList class, which will manage the entire list, primarily by keeping track of its head.

The SinglyLinkedList Class

class SinglyLinkedList:
    def __init__(self):
        self.head = None  # The head of the list, initially empty

    def is_empty(self):
        """Checks if the list is empty."""
        return self.head is None

Essential Operations on Singly Linked Lists

Now that we have our basic structure, let's implement common operations. Each operation demonstrates how we manipulate the next pointers to manage the sequence of nodes.

1. Insertion Operations

Adding new nodes to our linked list.

a) Prepending (Adding to the Beginning)

This is one of the easiest insertions. We simply create a new node and make it the new head, pointing to what was previously the head.

    def prepend(self, data):
        """Adds a new node at the beginning of the list."""
        new_node = Node(data)
        new_node.next = self.head  # New node points to the current head
        self.head = new_node      # Make the new node the head

b) Appending (Adding to the End)

To add to the end, we need to traverse the list until we find the last node (the one whose next pointer is None) and then link our new node to it.

    def append(self, data):
        """Adds a new node at the end of the list."""
        new_node = Node(data)
        if self.head is None:
            self.head = new_node  # If list is empty, new node becomes the head
            return

        current = self.head
        while current.next:
            current = current.next  # Traverse until current.next is None (last node)
        current.next = new_node     # Link the last node to the new node

c) Inserting After a Specific Node

This requires finding the node after which we want to insert. If found, we adjust the pointers.

    def insert_after_node(self, prev_node_data, data):
        """Inserts a new node after a node with specific data."""
        if self.head is None:
            print("List is empty. Cannot insert.")
            return

        current = self.head
        found = False
        while current:
            if current.data == prev_node_data:
                found = True
                break
            current = current.next

        if found:
            new_node = Node(data)
            new_node.next = current.next # New node points to prev_node's next
            current.next = new_node      # Prev_node points to new node
        else:
            print(f"Node with data {prev_node_data} not found.")

2. Deletion Operation (By Value)

Removing a node from the list requires careful handling of pointers to ensure the chain remains intact. We need to consider three cases: deleting the head, deleting a node in the middle, or deleting a node at the end.

    def delete_node(self, key_data):
        """Deletes the first occurrence of a node with the given data."""
        current = self.head

        # Case 1: Deleting the head node
        if current and current.data == key_data:
            self.head = current.next # Head moves to the next node
            current = None           # Remove reference to old head
            print(f"Deleted {key_data} from head.")
            return

        # Case 2: Deleting a node not at the head
        prev = None
        while current and current.data != key_data:
            prev = current
            current = current.next

        # If key was not present in the list
        if current is None:
            print(f"Node with data {key_data} not found.")
            return

        # Found the node to be deleted
        prev.next = current.next # Link previous node to current's next node
        current = None           # Remove reference to the deleted node
        print(f"Deleted {key_data}.")

3. Traversal and Display

To see what's in our list, we start at the head and follow the next pointers until we reach None.

    def print_list(self):
        """Prints all data in the list from head to tail."""
        if self.is_empty():
            print("The list is empty.")
            return

        current = self.head
        elements = []
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" -> ".join(elements))

4. Search Operation

To find if an element exists, we traverse the list, comparing each node's data with the target.

    def search(self, key_data):
        """Searches for a node with the given data."""
        current = self.head
        while current:
            if current.data == key_data:
                print(f"Node with data {key_data} found!")
                return True
            current = current.next
        print(f"Node with data {key_data} not found.")
        return False

5. Get Size Operation

To count the number of nodes in the list, we traverse and increment a counter.

    def get_size(self):
        """Returns the number of nodes in the list."""
        count = 0
        current = self.head
        while current:
            count += 1
            current = current.next
        return count

Putting It All Together: A Simple Demo

Let's see our singly linked list in action!

# Create a new linked list
my_list = SinglyLinkedList()

print("Is list empty?", my_list.is_empty()) # Expected: True

# Append elements
my_list.append(10)
my_list.append(20)
my_list.append(30)
print("After appending 10, 20, 30:")
my_list.print_list() # Expected: 10 -> 20 -> 30

# Prepend an element
my_list.prepend(5)
print("After prepending 5:")
my_list.print_list() # Expected: 5 -> 10 -> 20 -> 30

# Insert after a node
my_list.insert_after_node(20, 25)
print("After inserting 25 after 20:")
my_list.print_list() # Expected: 5 -> 10 -> 20 -> 25 -> 30

# Search for elements
my_list.search(10)  # Expected: Found
my_list.search(100) # Expected: Not found

# Get size
print("Size of the list:", my_list.get_size()) # Expected: 5

# Delete an element (middle)
my_list.delete_node(20)
print("After deleting 20:")
my_list.print_list() # Expected: 5 -> 10 -> 25 -> 30

# Delete an element (head)
my_list.delete_node(5)
print("After deleting 5 (head):")
my_list.print_list() # Expected: 10 -> 25 -> 30

# Delete an element (non-existent)
my_list.delete_node(99)
print("After trying to delete 99:")
my_list.print_list() # Expected: 10 -> 25 -> 30

# Delete the last element
my_list.delete_node(30)
print("After deleting 30:")
my_list.print_list() # Expected: 10 -> 25

# Delete the remaining elements
my_list.delete_node(10)
my_list.delete_node(25)
print("After deleting all elements:")
my_list.print_list() # Expected: The list is empty.
print("Is list empty?", my_list.is_empty()) # Expected: True

When to Use Linked Lists?

Linked lists shine in scenarios where:

• Frequent insertions and deletions are needed, especially in the middle of a sequence, as it only involves changing a few pointers, not shifting large blocks of memory. This is a $$O(1)$$ (constant time) operation *once the insertion point is found*.
• The size of the data collection is unpredictable and can grow or shrink significantly. Linked lists can dynamically allocate memory for new nodes as needed.
• Memory efficiency is important, as linked lists only occupy memory for the nodes they currently hold, unlike arrays which might pre-allocate more than needed.

However, they are not ideal for random access (e.g., getting the 5th element directly), as you must traverse from the head. This makes random access a $$O(n)$$ (linear time) operation.

Conclusion: Your First Step into Data Structures

Congratulations! You've just taken a significant step in understanding fundamental data structures by learning about singly linked lists. You've seen how to build them from scratch in Python and perform essential operations like adding, deleting, traversing, and searching for elements. This knowledge forms a crucial foundation for more complex data structures and algorithms, opening up a world of possibilities in efficient programming. Keep practicing, keep exploring, and you'll master these powerful concepts in no time!