How to implement a linked list in Python

Linked lists are a fundamental data structure in computer science. They offer dynamic memory allocation and efficient insertions or deletions, which makes them a powerful alternative to Python's built-in lists.

Here, you'll explore implementation techniques, real-world applications, and debugging advice. These tips help you master linked lists and apply them effectively in your own Python projects.

Basic implementation with dictionaries

# Simple linked list using dictionaries
node1 = {"data": 1, "next": None}
node2 = {"data": 2, "next": None}
node3 = {"data": 3, "next": None}
node1["next"] = node2
node2["next"] = node3

current = node1
while current:
   print(current["data"], end=" -> ")
   current = current["next"]
print("None")--OUTPUT--1 -> 2 -> 3 -> None

This approach uses dictionaries to simulate nodes, which is a straightforward way to build a linked list without custom classes. It's a great example of leveraging Python's built-in types for a classic data structure. Each dictionary represents a node with two essential keys:

• "data": Stores the actual value of the node.
• "next": Acts as a pointer to the following node in the sequence.

You link the nodes by assigning one dictionary to another's "next" key. The while loop then iterates through the list, moving from one node to the next until it finds a "next" value of None, which marks the end.

Basic linked list implementations

To build on the dictionary method, you can create dedicated Node and LinkedList classes, which allow for more complex operations like searching through the list.

Using a Node class

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

head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

current = head
while current:
   print(current.data, end=" -> ")
   current = current.next
print("None")--OUTPUT--1 -> 2 -> 3 -> None

Defining a Node class offers a more formal, object-oriented approach than using dictionaries. It bundles the node's structure and behavior into a reusable blueprint, which keeps your code organized. Each Node object you create has two key attributes:

• data: Stores the value for that specific node.
• next: Points to the following node in the chain, defaulting to None.

You build the list by creating instances of your Node class and linking them together through the next attribute.

Creating a LinkedList class with methods

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
       current = self.head
       while current.next:
           current = current.next
       current.next = new_node

llist = LinkedList()
for i in range(1, 4):
   llist.append(i)

current = llist.head
while current:
   print(current.data, end=" -> ")
   current = current.next
print("None")--OUTPUT--1 -> 2 -> 3 -> None

A dedicated LinkedList class neatly bundles the logic for managing your nodes. It holds a single reference, head, which points to the first node and serves as the entry point to the entire list.

• The __init__ method creates an empty list by setting head to None.
• The append method simplifies adding new nodes. It automatically finds the end of the list and attaches the new node, so you don't have to manage the pointers manually.

Implementing search functionality

class LinkedList:
   def __init__(self):
       self.head = None
   
   def search(self, key):
       current = self.head
       while current:
           if current.data == key:
               return True
           current = current.next
       return False

llist = LinkedList()
llist.head = Node(1)
llist.head.next = Node(2)
llist.head.next.next = Node(3)
print(f"Found 2: {llist.search(2)}")
print(f"Found 5: {llist.search(5)}")--OUTPUT--Found 2: True
Found 5: False

Adding a search(key) method lets you check if a value exists in your list. It works by traversing the list node by node, starting from the head.

• The loop continues as long as the current node isn’t None.
• Inside the loop, it compares the node’s data with the search key.
• If they match, the method returns True and stops.
• If the loop finishes without finding the key, it returns False, signaling the value isn't present.

Advanced linked list structures

With the fundamentals in place, you can now build more powerful variations like doubly and circular linked lists and enhance your classes with modern Python features.

Implementing a doubly linked list

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

head = DoublyNode(1)
middle = DoublyNode(2)
tail = DoublyNode(3)

head.next = middle
middle.prev = head
middle.next = tail
tail.prev = middle

# Forward traversal
print("Forward:", end=" ")
current = head
while current:
   print(current.data, end=" -> ")
   current = current.next
print("None")

# Backward traversal
print("Backward:", end=" ")
current = tail
while current:
   print(current.data, end=" -> ")
   current = current.prev
print("None")--OUTPUT--Forward: 1 -> 2 -> 3 -> None
Backward: 3 -> 2 -> 1 -> None

A doubly linked list enhances the standard linked list by allowing you to move in both directions. This is possible because each node keeps track of both the next and the previous node in the sequence.

• The DoublyNode class adds a prev attribute alongside data and next.
• This prev pointer creates a two-way link between nodes, enabling backward traversal.
• You can now start from the tail and move to the head, which is impossible in a singly linked list.

Creating a circular linked list

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

head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = head  # Make it circular

current = head
count = 0
while current and count < 5:
   print(current.data, end=" -> ")
   current = current.next
   count += 1
print("...")--OUTPUT--1 -> 2 -> 3 -> 1 -> 2 -> ...

In a circular linked list, the sequence of nodes forms a loop. Instead of the final node's next pointer being None, it points back to the beginning of the list. This creates a continuous cycle with no defined end.

• The key is the line head.next.next.next = head, which connects the last node back to the first.
• Because there's no null terminator, traversing the list can lead to an infinite loop if you don't set a specific condition to stop it.

Using iterators and type hints

from typing import Optional, TypeVar, Generic

T = TypeVar('T')

class Node(Generic[T]):
   def __init__(self, data: T):
       self.data: T = data
       self.next: Optional['Node[T]'] = None

class LinkedList(Generic[T]):
   def __init__(self):
       self.head: Optional[Node[T]] = None
   
   def __iter__(self):
       current = self.head
       while current:
           yield current.data
           current = current.next

ll: LinkedList[int] = LinkedList()
ll.head = Node(1)
ll.head.next = Node(2)
ll.head.next.next = Node(3)

print("Iterating:", end=" ")
for item in ll:
   print(item, end=" ")--OUTPUT--Iterating: 1 2 3

You can make your linked list more robust and Pythonic by integrating modern features like type hints and iterators. This approach enhances code clarity and makes your custom data structure behave more like Python's built-in collections.

• Type hints like Generic[T] and Optional make your code safer and easier to understand. They allow your linked list to hold any data type while explicitly marking that a next pointer can be None.
• Implementing the __iter__ dunder method turns your class into an iterable. It uses yield to return one node's data at a time, letting you use a simple for loop to traverse the list efficiently.

Move faster with Replit

Replit is an AI-powered development platform that transforms natural language into working applications. Describe what you want to build, and Replit Agent creates it—complete with databases, APIs, and deployment.

For the linked list techniques we've explored, this means you can build production-ready tools directly from a description. Examples include:

• A browser history tool that uses a doubly linked list for seamless forward and backward navigation.
• A dynamic music playlist manager where songs can be added or removed without re-indexing the entire list.
• A round-robin task scheduler that uses a circular linked list to cycle through active processes.

Describe your app idea, and Replit Agent writes the code, tests it, and fixes issues automatically, all in your browser.

Common errors and challenges

While powerful, linked lists come with unique challenges, from handling null pointers to managing complex insertions without breaking the chain.

• Handling None errors: A frequent issue is the AttributeError that occurs when your code tries to access an attribute like .next on a None object. This usually happens when you've traversed to the end of the list or if the list is empty. To avoid this, always check that a node is not None before attempting to access its properties.
• Avoiding infinite loops: Circular linked lists don't have a None terminator, so a standard traversal loop like while current: will run forever. You must define a clear stopping point—such as breaking the loop once you've returned to the starting node—to prevent an infinite loop.
• Updating pointers correctly: The order in which you update pointers during an insertion or deletion is crucial. If you reassign a node's next pointer too early, you can lose the connection to the rest of the list. For a safe insertion, always link the new node to the subsequent part of the list before connecting the previous node to your new one.

Handling None errors when traversing linked lists

A frequent bug in linked list traversal is the AttributeError. It happens when you try to access .next on a node that's actually None—a classic mistake when dealing with an empty list. The get_last_node_data function below triggers this error.

def get_last_node_data(head):
   current = head
   while current.next:  # Will cause error if head is None
       current = current.next
   return current.data

# Test with an empty list
empty_list = None
print(get_last_node_data(empty_list))

The while current.next condition doesn't account for an empty list. When head is None, current is also None, causing an immediate AttributeError. The corrected implementation below shows how to handle this edge case.

def get_last_node_data(head):
   if head is None:
       return None
   
   current = head
   while current.next:
       current = current.next
   return current.data

# Test with an empty list
empty_list = None
print(get_last_node_data(empty_list))

The corrected get_last_node_data function adds a simple guard clause: if head is None:. This check immediately returns None if the list is empty, preventing the code from ever reaching the while loop where the error would occur. It's a crucial first step before any traversal. Always anticipate empty lists or reaching the end of a list to avoid this common AttributeError when accessing a node's attributes.

Avoiding infinite loops in circular linked lists

Circular linked lists create a continuous loop, which means a standard traversal check like while current: will never end. This common mistake leads to an infinite loop because there's no None value to stop the iteration. The print_circular_list function below demonstrates this exact issue.

def print_circular_list(head):
   current = head
   while current:  # This will run forever on circular lists
       print(current.data, end=" -> ")
       current = current.next
   print("None")

The while current: condition in the print_circular_list function is always true because the list loops back on itself, creating an endless traversal. The corrected code below demonstrates how to iterate through the list without getting stuck.

def print_circular_list(head):
   if not head:
       print("None")
       return
       
   current = head
   print(current.data, end=" -> ")
   current = current.next
   
   while current and current != head:
       print(current.data, end=" -> ")
       current = current.next
   print("...")

The corrected print_circular_list function avoids an infinite loop by tracking its starting point. It first handles an empty list, then prints the head node's data before the loop begins.

The key is the while loop's condition: current != head. This check ensures the traversal stops once it completes a full circle and returns to the beginning. It's a simple but effective way to prevent your code from running forever when working with circular lists.

Updating pointers correctly when inserting nodes

When inserting a new node, the order of pointer updates is critical. Getting it wrong can break the list's continuity, effectively losing all subsequent nodes. This happens when you forget to link the previous node to the new one.

The insert_after function below demonstrates this common mistake. It correctly points the new node forward but fails to update the preceding node's .next pointer, leaving the list disconnected.

def insert_after(node, new_value):
   new_node = Node(new_value)
   new_node.next = node.next  # Link new node to next node
   # Missing the step to link previous node to new node!

# Example usage
head = Node(1)
head.next = Node(3)
insert_after(head, 2)

The insert_after function leaves the new node disconnected. Although it correctly points to the next item, the preceding node is never updated to point back to it. The corrected code below shows how to complete the link.

def insert_after(node, new_value):
   if node is None:
       return
       
   new_node = Node(new_value)
   new_node.next = node.next  # Link new node to next node
   node.next = new_node       # Link previous node to new node

# Example usage
head = Node(1)
head.next = Node(3)
insert_after(head, 2)

The corrected insert_after function fixes the broken link by adding one crucial line: node.next = new_node. This step connects the preceding node to the new one, fully integrating it into the list.

The order is key. First, you link the new node to the rest of the list. Then, you update the previous node's next pointer to point to the new node. This two-step process ensures you don't lose any part of the list during an insertion.

Real-world applications

Beyond the implementation details and error handling, linked lists are the backbone for familiar features like browser navigation and document versioning.

Building a browser history navigation with Node class

While a doubly linked list is ideal for full forward and backward navigation, a simple singly linked list can demonstrate the basic concept by chaining pages together.

# Create browser history nodes
home = Node("homepage.com")
search = Node("search.com")
result = Node("result.com")
home.next = search
search.next = result

# Navigate through history
current_page = result
print(f"Current page: {current_page.data}")
print(f"Going back: {search.data}")
print(f"Going back again: {home.data}")

This code models a simple browser history. It creates three Node objects, each holding a URL like homepage.com. The nodes are then linked sequentially using the .next attribute, establishing a path from the homepage to a search result.

• Each Node represents a step in the user's journey.
• The .next pointer connects one page to the next, forming the history chain.
• Navigation is simulated by starting at the result page and then manually referencing the previous nodes—search and home—to trace the path backward.

Implementing a document versioning system with dictionary-based linked nodes

A doubly linked list built with dictionaries provides a straightforward way to create a document versioning system, letting you easily move between edits.

This approach uses dictionaries to represent each version of a document. Each dictionary node contains the document's content and is linked to both its previous and next versions through prev and next keys.

• Each dictionary acts as a version snapshot, holding the content and a version number.
• The prev key is essential for navigating backward, allowing you to access earlier versions of the document.
• By starting at the latest version, you can traverse the chain backward using v3['prev'] to see the document's history.

# Create document versions with a doubly linked structure
v1 = {"content": "Hello World", "version": 1, "next": None, "prev": None}
v2 = {"content": "Hello World!", "version": 2, "next": None, "prev": v1}
v3 = {"content": "Hello Python World!", "version": 3, "next": None, "prev": v2}
v1["next"] = v2
v2["next"] = v3

# Navigate through document history
print(f"Current (v{v3['version']}): {v3['content']}")
print(f"Previous (v{v3['prev']['version']}): {v3['prev']['content']}")
print(f"First (v{v3['prev']['prev']['version']}): {v3['prev']['prev']['content']}")

This code builds a document's edit history using dictionaries. Each dictionary represents a specific version, holding its unique content and pointers to other versions.

The process involves two main steps:

• First, it defines three versions—v1, v2, and v3—as separate dictionaries.
• Next, it manually connects them into a sequence by updating their next keys, forming a chain.

This structure makes it easy to navigate through the history. The final lines demonstrate this by starting at the latest version, v3, and moving backward by accessing the ['prev'] key.

Get started with Replit

Turn your knowledge into a real tool. Describe what you want to build to Replit Agent, like “a browser history simulator with back/forward commands” or “a simple music playlist app using a doubly linked list.”

Replit Agent writes the code, tests for errors, and deploys your app directly from the browser. Start building with Replit.