Why bother with this when Python already has lists?

It's a fair question. In the real world, you'll almost always use Python's built-in list. But here's the catch: Python lists are actually dynamic arrays. When you pop(0) or insert(0, item), Python has to shift every single other element in memory one spot over. If your list has a million items, that's a million operations just to add one thing to the front.

A linked list doesn't care about shifting. It's just a chain of objects where each object points to the next one. If you want to add something to the front, you just create a new node and tell it to point to the current head. It's a constant-time operation, regardless of whether you have ten items or ten billion. I usually recommend thinking of it like a scavenger hunt: you don't know where the third clue is until you find the first and second.

How do I actually structure the classes?

You can't do this with a single class. You need a Node class to hold the data and a LinkedList class to manage the "head" (the first node). If you lose the head, you lose the entire list because Python's garbage collector will see the rest of the chain as unreachable.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None  # This is our pointer to the next node

class LinkedList:
    def __init__(self):
        self.head = None  # The list starts empty

I like to think of the LinkedList class as the "manager" and the Node as the "container." The manager doesn't need to know every node's location; it only needs to know where the first one is.

What's the trick to adding nodes without breaking the chain?

This is where most people trip up. If you're adding to the end of the list, you have to "walk" the chain until you find the node where next is None. If you just overwrite the head, you've effectively deleted your entire list.

Let's use a music playlist as an example. Each song is a node. To add a song to the end, you start at the first song and keep following the next pointer until you hit the end of the playlist.

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        
        # Walk the chain
        current = self.head
        while current.next:
            current = current.next
        
        # Now we're at the last node, attach the new one
        current.next = new_node

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

How do I delete a node without creating a gap?

You can't actually "delete" a node in the way you might imagine. Instead, you just "bypass" it. To remove a specific song from our playlist, you find the node immediately before the one you want to kill. You then tell that previous node to point to the one after the target.

It's like cutting a link out of a physical chain and welding the two remaining ends together. If you're deleting the head, it's even easier: just move the head pointer to self.head.next.

def delete(self, key):
    current = self.head
    
    # Case 1: The head is the one to delete
    if current and current.data == key:
        self.head = current.next
        return

    # Case 2: Search for the key, keeping track of the previous node
    prev = None
    while current and current.data != key:
        prev = current
        current = current.next

    # If we reached the end and didn't find the key
    if not current:
        return

    # Bypass the current node
    prev.next = current.next

📋 Practical Task

Exercise: Implementing a "Priority Insert" for a Music Queue

You are building a music queue manager. You already have the Node and LinkedList classes from the lesson. Your task is to implement a new method called insert_after(self, target_data, new_data).

This method should search the list for a node containing target_data. Once found, it should insert a new node containing new_data immediately after it. If the target_data is not found, the method should do nothing.

Requirements:

• Implement the insert_after method within the LinkedList class.
• Ensure the next pointers are updated correctly so no nodes are lost.
• Test your code by creating a list with "Song A" and "Song C", then inserting "Song B" after "Song A".