How to Implement a Linked List in Python from Scratch

Introduction

If you’re learning Python, you’ve almost certainly used the built-in list. It’s versatile, powerful, and one of the most common data structures you’ll encounter. But have you ever wondered how it works under the hood, or what alternatives exist? Understanding fundamental data structures is a cornerstone of becoming a proficient developer, and the linked list is one of the most important.

Unlike Python’s list, which stores data in a contiguous block of memory, a linked list is a collection of individual elements, called nodes, that are “linked” together in a sequence. Each node contains data and a reference (or pointer) to the next node in the chain.

This coding tutorial will serve as a beginner’s guide to linked lists. We’ll demystify the theory and walk you through a step-by-step implementation of a fully functional linked list in Python from scratch.

Prerequisites

Before we dive in, make sure you have the following:

• Software: Python 3.x installed on your machine.
• Knowledge: A basic understanding of Python syntax, including classes, objects (__init__ constructor), and while loops.

That’s it! No special libraries are needed.

Core Concepts: What is a Linked List?

Imagine a scavenger hunt. You start with a single clue (the head). This clue contains some information (data) and tells you where to find the next clue (next pointer). You follow this chain of clues until you reach the final one, which tells you the hunt is over (next pointer is None).

That’s a linked list in a nutshell! It consists of two main components:

1. The Node: The basic building block of the list. Each node holds:

   • Data: The actual value we want to store (e.g., a number, string, or any other object).
   • Next: A pointer that references the next Node in the sequence. For the last node in the list, this pointer is None.

2. The LinkedList: The container that holds the entire structure together. It only needs to keep track of one thing: the head, which is the very first node in the list. From the head, we can traverse the entire list by following the next pointers.

Why use a linked list instead of a regular Python list?

• Efficient Insertions/Deletions: Adding or removing elements from the beginning of a linked list is extremely fast (a constant time operation, O(1)). With a Python list, this is slow (O(n)) because all subsequent elements need to be shifted.
• Dynamic Size: Linked lists can grow and shrink dynamically without needing to reallocate memory for the entire list.
• Slow Random Access: The main trade-off is that accessing an element by its index is slow (O(n)), as you have to traverse the list from the head.

Step-by-Step Implementation

Let’s build our linked list. We’ll start with the Node and then create the LinkedList class to manage the nodes.

Step 1: Creating the Node Class

The Node is the simplest part. It’s a small class that holds our data and the reference to the next node.

class Node:
    """
    An object for storing a single node of a linked list.
    Models two attributes: data and the link to the next node in the list.
    """
    def __init__(self, data):
        self.data = data  # The value stored in the node
        self.next = None  # The reference to the next node, initialized to None

Step 2: Creating the LinkedList Class

Now, let’s create the LinkedList class. Initially, it will just have a head attribute. An empty list has a head of None.

class LinkedList:
    """
    A class for creating and managing a linked list.
    """
    def __init__(self):
        self.head = None # The head of the list, initialized to None for an empty list

Step 3: Implementing Traversal (Displaying the List)

To see what’s in our list, we need a way to traverse it from head to tail. We’ll create a display method to print the data of each node.

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

    def display(self):
        """
        Traverses the linked list and prints the data of each node.
        """
        elements = []
        current_node = self.head
        while current_node:
            elements.append(str(current_node.data))
            current_node = current_node.next
        print(" -> ".join(elements))

This method starts at the head and moves from one node to the next using current_node = current_node.next until it reaches the end (where current_node becomes None).

Step 4: Implementing Insertion

Let’s add methods to insert new nodes. We’ll cover two common cases: adding to the end (append) and adding to the beginning (prepend).

Appending a Node (to the end)

To append a node, we need to traverse to the last node and point its next reference to our new node.

# Add this method inside the LinkedList class
def append(self, data):
    """
    Appends a new node with the given data to the end of the list.
    """
    new_node = Node(data)
    
    # If the list is empty, the new node is the head
    if self.head is None:
        self.head = new_node
        return

    # Otherwise, traverse to the last node
    last_node = self.head
    while last_node.next:
        last_node = last_node.next
    
    # Set the next of the last node to the new node
    last_node.next = new_node

Prepending a Node (to the beginning)

Prepending is much simpler and is where linked lists shine. We just need to adjust the head.

# Add this method inside the LinkedList class
def prepend(self, data):
    """
    Prepends a new node with the given data to the beginning of the list.
    """
    new_node = Node(data)
    # Point the new node's next to the current head
    new_node.next = self.head
    # Update the head to be the new node
    self.head = new_node

Step 5: Implementing Deletion

To delete a node, we find it and then update the next pointer of the previous node to “skip” over the node we want to delete, effectively removing it from the chain.

# Add this method inside the LinkedList class
def delete(self, key):
    """
    Deletes the first node containing the given key.
    """
    current_node = self.head

    # Case 1: The node to be deleted is the head
    if current_node and current_node.data == key:
        self.head = current_node.next
        current_node = None # Free the old head
        return

    # Case 2: Search for the key to be deleted, keeping track of the previous node
    previous_node = None
    while current_node and current_node.data != key:
        previous_node = current_node
        current_node = current_node.next

    # If the key was not present in the list
    if current_node is None:
        print("Error: Key not found in the list.")
        return

    # Unlink the node from the linked list
    previous_node.next = current_node.next
    current_node = None # Free the node

Running the Code

Now let’s put it all together and see it in action. Save all the classes and methods into a file named linked_list_demo.py and add the following block at the end to test it.

# Full code for linked_list_demo.py

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

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

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

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

    def delete(self, key):
        current_node = self.head
        if current_node and current_node.data == key:
            self.head = current_node.next
            current_node = None
            return
        
        previous_node = None
        while current_node and current_node.data != key:
            previous_node = current_node
            current_node = current_node.next

        if current_node is None:
            print("Error: Key not found in the list.")
            return

        previous_node.next = current_node.next
        current_node = None

# --- Main execution block ---
if __name__ == "__main__":
    my_list = LinkedList()

    print("Appending elements:")
    my_list.append(10)
    my_list.append(20)
    my_list.append(30)
    my_list.display()  # Expected: 10 -> 20 -> 30

    print("\nPrepending an element:")
    my_list.prepend(5)
    my_list.display()  # Expected: 5 -> 10 -> 20 -> 30

    print("\nDeleting an element (20):")
    my_list.delete(20)
    my_list.display()  # Expected: 5 -> 10 -> 30

    print("\nDeleting the head element (5):")
    my_list.delete(5)
    my_list.display()  # Expected: 10 -> 30
    
    print("\nDeleting a non-existent element (100):")
    my_list.delete(100) # Expected: Error message
    my_list.display()   # Expected: 10 -> 30

To run this, open your terminal and execute:

python linked_list_demo.py

Common Errors & Pitfalls

When working with linked lists, especially as a beginner, you might run into a few common issues:

1. Losing the Head Reference: Be very careful when modifying self.head. If you accidentally reassign it during a traversal, you can lose the entire list. Always use a separate current_node variable for traversals.
2. Infinite Loops: Forgetting to update your traversal variable (e.g., current = current.next) inside a while loop will cause your program to hang.
3. NoneType Errors: This happens if you try to access .next on a node that is None (i.e., you’ve fallen off the end of the list). Always check if a node is not None before trying to access its attributes. For example, while current_node.next: is different from while current_node:.
4. Not Handling Edge Cases: An empty list (self.head is None) or a list with a single node often requires special handling. Always test your methods with these cases, as we did in our delete and append methods.

Conclusion & Further Learning

Congratulations! You have successfully implemented a linked list from scratch in Python. You now understand that a linked list is a chain of nodes, each containing data and a pointer to the next node. We built Node and LinkedList classes and implemented core operations like append, prepend, delete, and display.

The key takeaway is understanding the trade-offs: linked lists provide fast insertions and deletions at the beginning of a list, but they are slow for random access.

Ready for the next step? Try these challenges:

• Implement more methods: Add search(key) to find a node, or insert_after(target_node_data, new_data) to insert a node in the middle of the list.
• Explore Doubly Linked Lists: In this variant, each node has a next pointer and a prev (previous) pointer. This makes traversing backward possible and can simplify some operations.
• Learn about Circular Linked Lists: In this type, the next pointer of the last node points back to the head instead of None, forming a circle. This can be useful for applications that need to cycle through a list of items continuously.