Generally, when studying data structures, we usually start with two types of common data structures: contiguous and linked. Each of them comes with its drawbacks, so it’s crucial to understand what is your problem before going deeper into the data structures.
The objective of this article is to help shine a light on how those structures are implemented in Python, what kind of drawbacks, advantages, and even how you would implement some of them by yourself. Even though they all have implementations from Python’s standard library, getting to know how they work, might help you understand when and how to maximize its usage.
Python’s List a Contiguous Data Structure
Contiguously allocated structures are composed of single slabs of memory, some examples are Python’s lists, matrices, heaps, and hash tables.
Advantages
 Memory locality: physical continuity in memory can make use of highly optimized cache mechanisms
 O(1) complexity to access given the index
 Eﬃcient random access to items in arrays
Disadvantages
 Removing from the beginning is too costly due to resize
 Space efficiency: Python always allocates a larger size than the elements it has, to avoid calling realloc each time a new element is appended to the list
Usages
 Stacks (LIFO), good fit since we will always be inserting and removing the last element at a constant time
 Heaps, since each element is a node and the children can be accessed with a defined relationship. For example, in binary heaps the index of left_child is always given by 2 * parent_index + 1 and right_child as 2*parent_index + 2
 Hash Tables, since an arraylike list can be used to store the keys after computing the hash
 DepthFirst Search (DFS) Algorithm, generally, implementing a DFS involves using a stack to store the nodes visited
Implementation in Python Standard Library:
 Lists: https://docs.python.org/3/tutorial/datastructures.html#moreonlists
 CPython ref: https://github.com/python/cpython/blob/5c22476c01622f11b7745ee693f8b296a9d6a761/Include/listobject.h#L22 For a more indepth analysis of how lists are implemented in CPython, check Laurent Luce’s article.
Linked Lists in Python
A linked list is a type of linked data structure, which are structures composed of different chunks of memory that are linked by pointers. Some examples are trees, graphs (adjacency list), and linked lists.
Linked data structures have basic operations such as search, insert, and deletion. Also, they share some common properties:
 Each element contains a data field, which can have any type
 Each element contains a pointer to another node
Linked lists can be implemented as:
 SinglyLinked List: each element points to one successor element, generally called next
 DoublyLinked List: each element points to one successor and one predecessor element
 Circular Linked List: first element points to the last element and the last element points to the first
Advantages
 O(1) to access the first element
 Insertions put less pressure on memory since it involves only changing the address in memory that elements point to  avoiding resizing and shuffling
 Deletion is more efficient than in lists since it does not involve reallocations and shuffles
 Overﬂow on linked structures never occurs unless the memory is actually full
 With large records, moving pointers is easier and faster than moving the items themselves
Disadvantages
 O(n) at the worst case for accessing
 O(n) at the worst case for insertion
 Always O(n) for searching, whereas for lists we can use binary search if ordered, which has O(log n)
Usages
 Queues (FIFO), good fit since we have constant time at removing the first element
 BreadthFirst Search (BFS) Algorithm, generally, implementing a BFS involves using a queue to store the nodes visited
 AdjacencyList in Graphs, to store the connections of a vertice
 Hash Table, may use linked lists to store the chains of items that hash to the same position in the hash table
Implementation in Python Standard Library:

collections.deque
(pronounced “deck”): https://docs.python.org/3/library/collections.html#collections.deque
Custom Implementation of a Singly Linked List
Below you will find an example of how to implement a custom singly linked list in Python, this code helped me prepare for coding interviews. Having a good understanding of how it works, makes it easier to derivate a DoublyLinked or Circular list implementation.
NOTE: The methods are named after collections.deque API, which supports:
 append(x): Add x to the right side of the linked list
 appendleft(x): Add x to the left side of the linked list
 pop(x): Remove and return an element from the right side of the linked list
 popleft(x): Remove and return an element from the left side of the linked list
Node Class
Pretty straightforward, as it is a SinglyLinked list, we only need to define a field for the next, pointing to the successor, and a field for data, which can receive any type of data.
from __future__ import annotations
from typing import Any, Optional
class SLLNode:
def __init__(self, data: Any, next: Optional[SLLNode] = None):
self.data = data
self.next = next
def __str__(self):
return f"{self.data}"
SinglyLinked List Class
The class can start with its constructor only creating the HEAD node, pointing to None
, and may receive a list of nodes to prepopulate the list. In this implementation, I will leave the HEAD as an element with a None
value that will point to the first element added.
__iter__(self)
This method will be crucial to implement the other operations, keep in mind that it is not strictly necessary for search, append, pop, etc., however, I think it makes the code more pythonic and uses Python’s generators, which are much more memoryefficient.
from __future__ import annotations
from typing import Any, List, Optional
class SLLNode:
def __init__(self, data: Any, next: Optional[SLLNode] = None):
self.data = data
self.next = next
def __str__(self):
return f"{self.data}"
class SinglyLinkedList:
""" Custom implementation of a SinglyLinked List"""
def __init__(self, nodes: Optional[List[SLLNode]] = None):
# Note: the HEAD node will only contain data as 'HEAD' to
# print the list. See: __repr__()
self.HEAD = SLLNode('HEAD', next=None)
if nodes is not None:
for node in nodes:
self.append(node.data)
def __iter__(self):
node = self.HEAD
while node is not None:
yield node
node = node.next
Queue operations
Next, we can start implementing basic operations such as insert, remove and search. For Queue, we generally want to append at the end and remove the first element added, those operations will be called append and popleft in the code.
from __future__ import annotations
from typing import Any, List, Optional
class SLLNode:
def __init__(self, data: Any, next: Optional[SLLNode] = None):
self.data = data
self.next = next
def __str__(self):
return f"{self.data}"
class SinglyLinkedList:
""" Custom implementation of a SinglyLinked List"""
def __init__(self, nodes: Optional[List[SLLNode]] = None):
# Note: the HEAD node will only contain data as 'HEAD' to
# print the list. See: __repr__()
self.HEAD = SLLNode('HEAD', next=None)
if nodes is not None:
for node in nodes:
self.append(node.data)
def __iter__(self):
node = self.HEAD
while node is not None:
yield node
node = node.next
def append(self, data: Any) > SinglyLinkedList:
node = self.HEAD
for node in self:
pass
node.next = SLLNode(data)
return self
def popleft(self) > SLLNode:
if self.HEAD.next is None:
return None
previous_first = self.HEAD.next
self.HEAD.next = previous_first.next
return previous_first
For convenience, we can also add operations to appendleft, adding an element as the first of the queue, and pop to remove the last element. Note that, while
appendleft is done in constant time O(1), the pop operation needs to traverse the
full list until it finds the last element to remove, thus O(n):
from __future__ import annotations
from typing import Any, List, Optional
class SinglyLinkedList:
""" Custom implementation of a SinglyLinked List"""
def __init__(self, nodes: Optional[List[SLLNode]] = None):
# Note: the HEAD node will only contain data as 'HEAD' to
# print the list. See: __repr__()
self.HEAD = SLLNode('HEAD', next=None)
if nodes is not None:
for node in nodes:
self.append(node.data)
def __iter__(self):
node = self.HEAD
while node is not None:
yield node
node = node.next
def append(self, data: Any) > SinglyLinkedList:
node = self.HEAD
for node in self:
pass
node.next = SLLNode(data)
return self
def pop(self) > Optional[SLLNode]:
if self.HEAD.next is None:
return None
node = self.HEAD
while node.next.next:
node = node.next
removed_node = node.next
node.next = None
return removed_node
def appendleft(self, data: Any) > SinglyLinkedList:
new_node = SLLNode(data)
if self.HEAD.next is None:
self.HEAD.next = SLLNode(data)
return self
previous_first = self.HEAD.next
self.HEAD.next = new_node
new_node.next = previous_first
return self
def popleft(self) > SLLNode:
if self.HEAD.next is None:
return None
previous_first = self.HEAD.next
self.HEAD.next = previous_first.next
return previous_first
Next, we can add methods to find and remove a node given a certain data passed as an argument. Note that in a DoublyLinked List, those processes would be simpler, since once we found the node, we can update the predecessor and successor at once. In a SinglyLinked we need to keep a reference to the predecessor, so that when removing we update the successor accordingly:
class SinglyLinkedList:
""" Custom implementation of a SinglyLinked List"""
def __init__(self, nodes: Optional[List[SLLNode]] = None):
# Note: the HEAD node will only contain data as 'HEAD' to
# print the list. See: __repr__()
self.HEAD = SLLNode('HEAD', next=None)
if nodes is not None:
for node in nodes:
self.append(node.data)
def __iter__(self):
node = self.HEAD
while node is not None:
yield node
node = node.next
def append(self, data: Any) > SinglyLinkedList:
node = self.HEAD
for node in self:
pass
node.next = SLLNode(data)
return self
def pop(self) > Optional[SLLNode]:
if self.HEAD.next is None:
return None
node = self.HEAD
while node.next.next:
node = node.next
removed_node = node.next
node.next = None
return removed_node
def appendleft(self, data: Any) > SinglyLinkedList:
new_node = SLLNode(data)
if self.HEAD.next is None:
self.HEAD.next = SLLNode(data)
return self
previous_first = self.HEAD.next
self.HEAD.next = new_node
new_node.next = previous_first
return self
def popleft(self) > SLLNode:
if self.HEAD.next is None:
return None
previous_first = self.HEAD.next
self.HEAD.next = previous_first.next
return previous_first
def find(self, data: Any) > Optional[SLLNode]:
if self.HEAD.next is None:
return None
for node in self:
if node.data == data:
return node
def remove(self, data: Any) > SinglyLinkedList:
if self.HEAD.next is None:
return None
for node in self:
if node.next.data == data:
node.next = node.next.next
return self
Container Type Methods
In Python, objects that contain references to other objects are called containers, i.e: lists, tuples, and dictionaries. As an approach to operator overloading, Python provides invokes certain methods by special syntax. For instance, accessing an object with x[i]
is equivalent to type(x).__getitem__(x, i)
.
Thus, for convenience, we can implement some of them as the code below suggests:

len: Called to implement the builtin function
len()
stack = SinglyLinkedList()
print(len(stack)) # 0

contains:
Called to implement membership test operators. Should return true if item is in self,
false otherwise. Uses
__iter__()
stack = SinglyLinkedList(SLLnode('John Doe'))
print('John Doe' in stack) # True

getitem:
Called to implement evaluation of
self[key]
stack = SinglyLinkedList(SLLnode('John Doe'))
print(stack[0]) # 'John Doe'

setitem:
Called to implement assignment to
self[key]
stack = SinglyLinkedList()
stack[0] = SLLNode('Ada Lovelace')
print(stack[0]) # 'Ada Lovelace'

delitem:
Called to implement deletion of
self[key]
stack = SinglyLinkedList(SLLNode('Ada Lovelace'))
print(len(stack)) # 1
del stack[0]
class SinglyLinkedList:
""" Custom implementation of a SinglyLinked List"""
def __init__(self, nodes: Optional[List[SLLNode]] = None):
# Note: the HEAD node will only contain data as 'HEAD' to
# print the list. See: __repr__()
self.HEAD = SLLNode('HEAD', next=None)
if nodes is not None:
for node in nodes:
self.append(node.data)
def __iter__(self):
node = self.HEAD
while node is not None:
yield node
node = node.next
def __len__(self) > int:
return len([node for node in self])  1
def __contains__(self, data: Any) > bool:
for node in self:
if node.data == data:
return True
return False
def __str__(self) > str:
node = self.HEAD
nodes = []
for node in self:
nodes.append(str(node))
nodes.append('None')
return ' > '.join(nodes)
def __getitem__(self, index: int) > SLLNode:
if index < 0 and index > len(self)  1:
raise IndexError(f'Index {index} out of range')
node = self.HEAD
for _ in range(index):
node = node.next
return node.next
def __setitem__(self, index: int, data: Any) > SinglyLinkedList:
if index < 0 and index > len(self)  1:
raise IndexError(f'Index {index} out of range')
node = self.HEAD
for _ in range(index + 1):
node = node.next
node.data = data
return self
def __delitem__(self, index: int):
if index < 0 and index > len(self)  1:
raise IndexError(f'Index {index} out of range')
node = self.HEAD
for _ in range(index):
node = node.next
node.next = node.next.next if node.next else None
return
def __gt__(self, other: SinglyLinkedList) > bool:
if len(self) > len(other):
return True
def __lt__(self, other: SinglyLinkedList) > bool:
if len(self) < len(other):
return True
def __ge__(self, other: SinglyLinkedList) > bool:
if len(self) >= len(other):
return True
def __le__(self, other: SinglyLinkedList) > bool:
if len(self) <= len(other):
return True
def __eq__(self, other: SinglyLinkedList) > bool:
if len(self) != len(other):
return False
for node in self:
if node.data != other[node.data]:
return False
return True
def __ne__(self, other: SinglyLinkedList) > bool:
return not self == other
def append(self, data: Any) > SinglyLinkedList:
node = self.HEAD
for node in self:
pass
node.next = SLLNode(data)
return self
def pop(self) > Optional[SLLNode]:
if self.HEAD.next is None:
return None
node = self.HEAD
while node.next.next:
node = node.next
removed_node = node.next
node.next = None
return removed_node
def appendleft(self, data: Any) > SinglyLinkedList:
new_node = SLLNode(data)
if self.HEAD.next is None:
self.HEAD.next = SLLNode(data)
return self
previous_first = self.HEAD.next
self.HEAD.next = new_node
new_node.next = previous_first
return self
def popleft(self) > SLLNode:
if self.HEAD.next is None:
return None
previous_first = self.HEAD.next
self.HEAD.next = previous_first.next
return previous_first
def find(self, data: Any) > Optional[SLLNode]:
if self.HEAD.next is None:
return None
for node in self:
if node.data == data:
return node
def remove(self, data: Any) > SinglyLinkedList:
if self.HEAD.next is None:
return None
for node in self:
if node.next.data == data:
node.next = node.next.next
return self
The complete code can be found at this gist: https://gist.github.com/hspedro/253afbda49f383f4e7b17e9ae73ab63a
Other Resources
This code helped me through multiple code interviews, and also to revisit some basic data structures fundamentals. I strongly recommend checking on these other resources!
 List Implementation in CPython, Laurent Luce
 Official Doc for Lists, Python Docs
 Design Details on List Implementation, Python Docs
 Understanding Linked Lists, Real Python
 The Algorithm Design Manual  Chapter 3, Steven Skiena
 What's A Linked List Anyway, Vaidehi Joshi
Top comments (1)
I played around with a linked list class in Python too  stromberg.dnsalias.org/~strombrg/d...
I performance tested it against Python native lists, and found that it was much slower, even at things it had the same bigO on. I believe this is because access every element of a linked list is commonly a different cache line hit.
It's usually better to use collections.deque than a linked list in Python. Underneath it all, collections.deque is a doublylinked list of small contiguous elements.