Linked Lists vs Python Lists: When to Use Each

Ever wish your list items could tell you not only a value but also where to go next? If so, linked lists might be the thing for you. In addition to storing a value at each node, linked lists store a reference to the next node, helpfully pointing you in the right direction.

In this article, you’ll not only learn more about the foundational components and common operations of linked lists, but we’ll also show you how to implement various types of linked lists in Python. Starting with a brief comparison with classic lists, we’ll link you up with some classic linked-list interview questions and give you alternatives that are already built-in to Python so you’re not chained to a single way of doing things.

What is a Linked List?

A linked list is a linear data structure that’s core to computer science. It’s one approach to data organization that uses a sequence of items called nodes. Each node contains:

• A specific data value

• A reference/pointer to the next node in the chain

You can travel from the head, or first node, of a linked list through its tail, or last node, by going from one node to the next. The last node points to None in a regular, singly linked list.

A linked list does not need to occupy contiguous memory like an array. Instead, each node uses its next reference to connect to the following node.

Python does not have a built-in linked list data structure. You can implement your own, though, often by using custom classes.

Linked List vs Lists

Before we move on to the way to create linked lists in Python, it's important to distinguish them from traditional lists.

Python’s built-in list and a linked list are both used for storing ordered collections of items, but they work very differently under the hood. Regular lists use a contiguous array in memory, providing fast and simple access to their elements by using their index. However, lists need to allocate a fixed block of continuous memory beforehand, which can result in resizing when additions or deletions happen, which can affect performance. However, this only happens occasionally, as Python's list over-allocates extra capacity, so most append() calls don't trigger a resize

By contrast, linked lists use nodes linked with pointers. This makes them unsuitable for random access like arrays (i.e., you cannot access a particular node directly given its index), yet they are more flexible and efficient when adding or removing elements, for these operations only require rewiring a couple of pointers.

The following diagram illustrates the differences:

Building Blocks for Creating a Linked List

You’re now ready to create your own Python linked list. This is commonly done with two main classes:

• Node, for each individual node

• LinkedList, for the overall data structure

Building these classes helps separate the individual node behavior from the list-level behavior, which proves critical for traversing, inserting new elements, deleting items, and searching.

Individual Nodes

The Python class Node represents a single element in the linked list. Each node is a separate object that stores its own data and a reference to the next node in the sequence.

Here’s the definition of Node. The def __init__(self, data) line defines the constructor, which helps store the attributes:

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

The next attribute has a reference to the next node in the chain; however, it’s initialized as None until you establish a link to another node.

To start creating Node objects, provide a value upon initialization. Then set the next property to make a connection between the nodes:

head = Node(100)second_node = Node(200)head.next = second_node

Initializing an Empty List

Once you’ve got your Node going, it’s time to make a LinkedList class:

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

You can then start an empty linked list:

linked_list = LinkedList()print(linked_list.head)# Expected result:# None

This list doesn’t have any nodes yet, but you can append them with a class method. The next step is to write code to add, remove, or search through nodes as part of your standard linked list operations.

Core Methods for Linked Lists

You’ve already got the skeleton of a Python linked list consisting of two classes: Node for the individual nodes and LinkedList for the overall list structure. You’ll typically want to write methods, or specialized functions that live within the class and describe the actions the class can perform.

Adding New Nodes

To start, you can create a method called append() to add nodes to the end of your Python linked list. This method should accept a new value, create a new node, and add it to the end of your list. If your list is empty, the new node becomes the head, but if you already have nodes in your list, this method sets the new node as the next node after the current tail node. Note that this function should be a part of the LinkedList class:

def append(self, value):    new_node = Node(value)    # Set as head if empty list    if self.head is None:        self.head = new_node        return    current = self.head    # Traverse linked list looking for the tail node    while current.next is not None:        current = current.next        # Append new_node at the end of the list    current.next = new_node

Since this implementation doesn’t store the tail separately, append() must start at the head and traverse the entire list to find the last node. Once you reach the tail, set its next reference to the new node.

You may now append new nodes to your Python linked list like this:

linked_list.append(100)linked_list.append(200)linked_list.append(300)

Traversing the Linked List

You could also have a method specifically for traversing the entire linked list. This traverse() method prints each list value by starting from head and continually moving to the next node until it reaches the end of the list:

def traverse(self):    current = self.head    while current is not None:    # Continue through the tail node        print(current.data)        current = current.next      # Move to the next nodelinked_list.traverse()# Expected result:# 100# 200# 300

Searching for a Node

Unlike regular Python lists, linked lists don’t support direct access by index. You can, however, create a method to search for a particular value in a linked list. This search() method begins at the head of the list and compares each node’s value to the input. It returns the first node where the node’s data matches or None if it cannot find the value:

def search(self, value):    current = self.head    while current is not None:        if current.data == value:            return current        current = current.next    return Nonemy_node = linked_list.search(200)print(my_node.data)# Expected result:# 200

Removing Nodes

You can remove a node by value by skipping over the target node and connecting the previous node to the next one. This remove() method helps you eliminate the first node that matches your input value. If no nodes match, it raises a ValueError:

def remove(self, value):    # Raise error if list is empty    if self.head is None:        raise ValueError(f"{value} not found in linked list")    # Handle removing the head as a special case    if self.head.data == value:        self.head = self.head.next        return    current = self.head    # Look for value, connect around it if found    while current.next is not None:        if current.next.data == value:            current.next = current.next.next            return        current = current.next   # Move on if value doesn’t match    # Raise error if value not found    raise ValueError(f"{value} not found in linked list")linked_list.remove(200)linked_list.traverse()# Expected result:# 100# 300

Just make sure to update the next attribute of the current node in the above code. Forgetting to change the pointers of your nodes is a very common misstep when adding new nodes or deleting elements.

These core methods give you the basic tools for working with Python linked lists; however, their implementation can vary depending on the type of linked list you choose.

Implementing Linked Lists: Python Singly, Doubly, Circular

Seemingly straightforward thus far, linked lists actually come in a few different varieties, each with its own benefits and drawbacks. You’ve been working on singly linked lists throughout this article, but you may also encounter doubly or circular linked lists.

Singly linked lists follow a linear path from one node to the next. Each node has exactly one reference that points to the next node in the chain. You traverse the list from its head to its tail in only one direction.

The Python implementation you saw in the previous sections features a singly linked list. Code for the other types of linked lists shares many of the same features but differs in a few important ways.

Doubly Linked Lists

The main difference between a singly linked list and a doubly linked list is that doubly linked lists have two references per node. Each node points to both the previous and next node in the chain. That means, unlike a singly linked list where you can only move forward, you can progress through the list in a forward or backward direction. While being able to move backward through the list may prove beneficial for some use cases, storing data for the extra references does increase memory usage.

Here’s how your Python class Node changes for a doubly linked list:

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

Notice the new prev attribute. This attribute points to the previous node in the linked list and helps you move through the list backward.

When you create a node with this class, you can set both next and prev:

head = Node(100)second = Node(200)head.next = secondsecond.prev = head

The LinkedList class usually also receives one major update when building a doubly linked list. In addition to tracking head, it now has a tail reference, which serves as a starting point for backward traversal:

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

The methods you wrote for a singly linked list then change in a few important ways:

• append(): Set next for the old tail and prev for the new node at the tail

• traverse(): Add an option to follow the list forward or backward

• search(): Add an option to search starting from the front or back of the list

• remove(): Update the next and prev references of the neighboring nodes

Circular Linked Lists

When you create a circular linked list, the tail of your list connects back to the head rather than pointing to None. You can therefore think of a circular linked list as a loop. Circular linked lists can be singly or doubly linked, and their implementations share much of the same basic structure.

The Node class for a circular linked list follows the same structure as the one for a singly or doubly linked list, just make sure that your last node points back around to the first node of your list. You can create a singly linked example like this:

head = Node(100)second = Node(200)third = Node(300)head.next = secondsecond.next = thirdthird.next = head    # Tail points to head

The constructor of the LinkedList class remains the same, but the method for traversing your circular linked list changes since this type of list has no natural None endpoint. In particular, you’ll need an explicit stopping condition to travel through a circular linked list:

def traverse(self):    # Detect empty list    if self.head is None:        return    current = self.head    while True:        print(current.data)        current = current.next        # Stop when reaching head once more        if current == self.head:            break

You can then create and traverse your own circular linked list:

circular_linked_list = LinkedList()circular_linked_list.head = headcircular_linked_list.traverse()# Expected result:# 100# 200# 300

Note that other methods may require small changes as well. For example, append() should look for a node that points back to head rather than one that points to None. You should then set the new node’s reference to head, making the new node the tail.

Ultimately, singly linked lists offer the simplest structure, while doubly and circular linked lists give you added flexibility with the cost of additional references or more complex logic.

Classic Interview Questions with Code Examples

Questions about linked lists frequently come up during coding interviews. Oftentimes, you’ll need to think through traversal problems or those that modify the list references. Be sure to clarify what type of linked list you’re dealing with first and then think through edge cases to ensure your answer handles them correctly. While there are plenty of other questions, here we review some of the most common linked list interview topics.

How Do You Reverse a Linked List?

Of all the linked-list interview questions, this is probably the most popular one. When interviewers ask this question, they’re typically referring to a singly linked list without prev references, but be sure to double-check before getting started.

To reverse a singly linked list, traverse through your list and keep track of three items: the previous, current, and next nodes. You’ll want to switch current.next to point to the previous node instead of the next one, but be sure to temporarily save which node comes next in the list before overwriting current.next so that you don’t break the chain and lose access to the rest of the list.

Here’s a method you can add to your LinkedList class for a singly linked list:

def reverse(self):    previous = None    current = self.head    while current is not None:		# Continue through tail node        next_node = current.next		# Save next node         current.next = previous		# Switch reference to previous        previous = current			# Get ready for next iteration        current = next_node    self.head = previous			# Update head to be old tail

Once you’ve reversed all the references, the old tail becomes the new head, so set self.head to previous. By the way, this approach takes O(n) time and O(1) additional space in big-O notation since it traverses the list once while maintaining only a few references.

How Do You Detect a Cycle in a Linked List?

If reversing a linked list is #1, detecting a cycle is probably the #2 most common interview question about linked lists. The key to this question is Floyd’s cycle detection algorithm, also called the tortoise and hare algorithm.

Assuming a singly linked list, a cycle happens when a node points back to an earlier node instead of eventually reaching None. This causes an issue for normal traversal, which could continue forever.

You can detect a cycle using two pointers:

• slow, which advances only one node per iteration

• fast, which advances two nodes per iteration

If fast reaches the end of your list, your linked list does not have a cycle, but you do have a cycle if slow and fast eventually reference the same node.

Adding this method to your LinkedList class accomplishes cycle detection:

def has_cycle(self):    slow = self.head    fast = self.head    # Continue while fast can advance    while fast is not None and fast.next is not None:        slow = slow.next		# Advance one node        fast = fast.next.next	# Advance two nodes        # Cycle detected if slow and fast meet        if slow == fast:            return True    return False  # No cycle if fast reaches the end of the list

In the above code, you don’t need to store elements for every previously visited node since you just want to find out if a cycle exists. In terms of complexity, this solution takes O(n) time to travel through the nodes and O(1) intermediate storage.

How Do You Find the Middle of a Linked List?

Once again assuming a singly linked list, this problem may seem simple at first. You could traverse your list, count the number of nodes, and then just traverse again to the midpoint. While this solution works, it’s not the most efficient implementation.

Instead, you can find the middle with a single traversal by leveraging slow and fast pointers. Use the same basic technique as the cycle detection algorithm:

• slow advances one node per iteration

• fast advances two nodes per iteration

But here’s the really slick part: when fast reaches the end of the list, slow is in the middle.

This LinkedList method gives you the midpoint node, and note that for the edge case of empty lists, it simply returns None:

def find_middle(self):    slow = self.head    fast = self.head    while fast is not None and fast.next is not None:        slow = slow.next        fast = fast.next.next    # slow gives you the midpoint when fast reaches the end    return slow  

For an odd number of nodes, you have one clear midpoint; however, for an even number of nodes, there are two possible “middles.” This implementation returns the second of the two, but you should check with your interviewer to see which one they prefer. This technique also has O(n) time complexity and uses O(1) auxiliary space.

Other Common Questions

You’re likely to encounter at least one of those three questions during an interview that tests linked-list knowledge, but other popular questions include:

• How do you merge two sorted linked lists?

• How can you find the kth node from the end of a linked list?

• How do you remove duplicate values from a linked list?

• Can you determine whether or not a linked list is a palindrome?

• How do you delete a node at a particular position from a linked list?

• Compare the time complexity and space complexity of various linked-list operations.

AI Tutor: Ask me how to delete a node at a particular position from a linked list and let me work through the solution step-by-step without revealing the answer right away.

Real-World Applications

Linked lists are great for forward and backward traversal through elements, especially when you have a doubly linked list. You could set up your browser’s page history as a doubly linked list. Visiting previous pages would be as easy as advancing forward to more recent pages. The same goes for a music playlist. A listener could go back to replay a previous song or skip forward in the list when a song doesn’t suit his fancy. You could even create a circular linked list to continually repeat the playlist.

You’ll also find linked lists useful when you need to frequently insert new nodes or remove elements and already have access to the relevant nodes. Imagine tracking a user’s edits with a linked list. She could conveniently move backward to undo previous edits or forward to redo them, while adding new actions to the history. Linked lists also come in handy to represent adjacency lists in graphs or to handle collisions when implementing hash tables through a technique called separate chaining. You may use linked lists for queues and deques, though in Python you’d normally use collections.deque from the standard library for that use case.

Built-in Linked List Alternatives

Python has no built-in linked list data structure, but there are a few other pre-written options for accomplishing similar core behaviors. By leveraging these alternatives, you won’t often need to implement your own linked list.

list

Python’s generic list object can achieve most of what you’ll need to do when storing sequences of data. list is a dynamic array rather than a linked list. Unlike a linked list, you can look up items by index in O(1), or constant, time. A regular list is quite efficient at appending or removing items from its end: appending takes amortized O(1) time, while removing the final item has O(1) time complexity. Inserting elements or removing them from the front or middle parts of a list, however, takes O(n) time since you’ll need to shift items further down the list to keep the sequence intact.

collections.deque

The standard-library collections module offers another data structure called deque. deque is a double-ended queue that allows you to easily add or remove elements from the beginning or end. Insertion or deletion from either end only has O(1) time complexity, so deque is a great option for implementing queues and stacks. It was not designed for quickly finding an item by index, though, so if that’s a functionality you need, you may choose to stick with a regular list.

Comparing Time Complexity and Performance of Data Structures

Here’s how the time complexity of linked lists compares to list and deque for standard operations:

*Indexed access is O(1) at either end for deque, slowing to O(n) toward the middle.
**If you don’t maintain a tail reference, appending requires O(n) for traversing the linked list.

When Not to Use a Linked List

Some situations just don’t make sense for the linked list. If you need random access to regularly retrieve items by index, use a standard Python list. Likewise, use a list if you’ll mostly be appending to the end and iterating through your collection.

You’ll probably end up with deque for queue and stack problems since they’re efficient for those cases and deque is already implemented in Python.

Linked lists come with memory concerns because they must store data for the node references. If you don’t already know which node you need to delete or insert near, their O(1) relinking advantage gets masked by the O(n) traversal time complexity.

In general, don’t implement a Python linked list just because you can. Save them for special cases where you need to frequently travel forward and backward through your list or insert/delete at known nodes. Python developers generally prefer list and deque for everyday tasks.

Wrapping Up

Python has no built-in linked list, but you can create a linked list on your own with Node and LinkedList classes. You’ll probably want to write methods to append new nodes, traverse your list, search for nodes, and remove old nodes in the LinkedList class. You can also include methods to reverse a linked list, detect a cycle, or find the midpoint, especially when solving some of the most common linked-list interview questions.

Singly linked lists give you the classic, unidirectional chain of nodes, but you may also encounter doubly linked lists with references to next and previous elements. You can also have a circular linked list where the tail node points to the head. Just make sure that your situation actually requires a linked list in the first place. Python has pre-written list and deque data structures to save you implementation time and potentially better fit your use case.

Ready to show off your linked-list abilities? See how you fare against the AI Tutor. Use this prompt to kick off a chain reaction of knowledge: