Code Linked List in Python: Beginner Tutorial

Python's built-in list is powerful. But learning to build your own linked list teaches core concepts. It is a fundamental data structure.

This guide will walk you through creating a linked list in Python. We will cover the theory and the code.

What is a Linked List?

A linked list is a linear data structure. It consists of a sequence of nodes. Each node holds data and a reference to the next node.

This is different from a standard Python list. A list uses a contiguous block of memory. A linked list uses scattered nodes connected by pointers.

Understanding this difference is key. For a deeper dive, see our guide on Python Lists vs Tuples: Key Differences Explained.

Why Learn Linked Lists?

You might wonder why. Python's list is highly optimized. Learning linked lists is not about replacing them.

It is about understanding pointers and dynamic memory. These concepts are vital for advanced programming and interviews.

It builds a foundation for trees and graphs. Mastering linked lists makes other structures easier to learn.

Building the Node Class

Every linked list starts with a node. A node has two parts: data and a next pointer.

We create a simple class for this. The __init__ method sets up the node.

class Node:
    """Represents a single node in the linked list."""
    def __init__(self, data):
        self.data = data  # Store the value
        self.next = None  # Pointer to the next node, starts as None

The data attribute holds the value. The next attribute points to the next Node object. It is None by default.

Creating the LinkedList Class

Now we create the main list class. It will manage the nodes. The head attribute points to the first node.

class LinkedList:
    """Manages the linked list operations."""
    def __init__(self):
        self.head = None  # The list is empty at the start

An empty list has a head of None. Let's add our first operation.

Inserting Data at the Beginning

We often add nodes at the start. This is a prepend operation. It is efficient in a linked list.

The steps are simple. Create a new node. Point its next to the current head. Update the head to the new node.

    def insert_at_beginning(self, data):
        """Inserts a new node with the given data at the beginning of the list."""
        new_node = Node(data)  # Step 1: Create the new node
        new_node.next = self.head  # Step 2: New node points to old head
        self.head = new_node  # Step 3: Update head to the new node

Let's test this. We will create a list and add two items.

# Create a new linked list
my_list = LinkedList()

# Insert elements
my_list.insert_at_beginning(20)
my_list.insert_at_beginning(10)

print("List after inserting 20, then 10 at the beginning:")
# We need a method to see the list, coming next!

List after inserting 20, then 10 at the beginning:

Traversing and Displaying the List

To see our list, we need to traverse it. We start at the head. We follow the next pointers until we hit None.

This operation is similar to iterating through a standard list to find its Python List Length: A Beginner's Guide.

    def display(self):
        """Prints all elements in the linked list."""
        current = self.head  # Start at the head
        elements = []
        while current:  # Loop until current is None
            elements.append(str(current.data))
            current = current.next  # Move to the next node
        print(" -> ".join(elements) + " -> None")

Now we can see our previous test.

my_list = LinkedList()
my_list.insert_at_beginning(20)
my_list.insert_at_beginning(10)

my_list.display()

10 -> 20 -> None

Great! The list shows 10 points to 20, which points to None. The last node's next is always None.

Inserting Data at the End

Appending to the end is common. We must traverse to the last node. Then we link the new node there.

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

        current = self.head
        while current.next:  # Traverse to the last node
            current = current.next
        current.next = new_node  # Link the last node to the new node

Let's use both insertion methods.

my_list = LinkedList()
my_list.insert_at_beginning("First")
my_list.insert_at_end("Last")
my_list.insert_at_end("Very Last")
my_list.display()

First -> Last -> Very Last -> None

Deleting a Node by Value

Deletion is a crucial operation. We find the node with the target value. We adjust the pointers to bypass it.

We must handle two cases. The node to delete is the head. Or it is somewhere else in the list.

    def delete_node(self, key):
        """Deletes the first node found containing the given key (data)."""
        current = self.head

        # Case 1: Delete the head node
        if current is not None and current.data == key:
            self.head = current.next  # Move head to the next node
            current = None  # Optional: clear the old node
            return

        # Case 2: Search for the node in the rest of the list
        prev = None
        while current is not None:
            if current.data == key:
                break
            prev = current  # Keep track of the previous node
            current = current.next

        # If key was not found
        if current is None:
            print(f"Value {key} not found in the list.")
            return

        # Unlink the node from the list
        prev.next = current.next
        current = None  # Optional cleanup

Let's see deletion in action.

my_list = LinkedList()
for num in [5, 10, 15, 20]:
    my_list.insert_at_end(num)

print("Original list:")
my_list.display()

my_list.delete_node(10)
print("After deleting 10:")
my_list.display()

my_list.delete_node(5)  # This is the head node
print("After deleting head (5):")
my_list.display()

my_list.delete_node(99)  # Not in list

Original list:
5 -> 10 -> 15 -> 20 -> None
After deleting 10:
5 -> 15 -> 20 -> None
After deleting head (5):
15 -> 20 -> None
Value 99 not found in the list.

Searching for an Element

Searching involves traversal. We check each node's data. We return True if found.

This is a linear search, similar to checking if a value is the Find Minimum in Python List: Easy Guide & Code.

    def search(self, key):
        """Returns True if a node with the given key exists, otherwise False."""
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

Testing the search function.

print("Searching for 15:", my_list.search(15))
print("Searching for 99:", my_list.search(99))

Searching for 15: True
Searching for 99: False

Conclusion

You have now built a basic linked list in Python. You learned to create nodes, insert data, delete nodes, and traverse the list.

Understanding linked lists is a major step in computer science. It teaches you about pointers, dynamic memory, and algorithm efficiency.

Remember, Python's built-in list is different. It is an array-based, dynamic sequence. Use it for most tasks. Build linked lists to learn the concepts.

From here, you can explore doubly linked lists or circular linked lists. You can also learn how to sort or merge linked lists. The foundation is now set.

Practice by adding more methods. Try reversing the list or finding its length. Keep coding and exploring.