Python linked list library
Linked Lists in PythonBy Dan Bader Get free updates of new posts here. Show
Learn how to implement a linked list data structure in Python, using only built-in data types and functionality from the standard library. Every Python programmer should know about linked lists: They are among the simplest and most common data structures used in programming. So, if you ever found yourself wondering, Does Python have a built-in or native linked list data structure? or, How do I write a linked list in Python? then this tutorial will help you. Python doesnt ship with a built-in linked list data type in the classical sense. Pythons list type is implemented as a dynamic arraywhich means it doesnt suit the typical scenarios where youd want to use a proper linked list data structure for performance reasons. Please note that this tutorial only considers linked list implementations that work on a plain vanilla Python install. Im leaving out third-party packages intentionally. They dont apply during coding interviews and its difficult to keep an up-to-date list that considers all packages available on Python packaging repositories. Before we get into the weeds and look at linked list implementations in Python, lets do a quick recap of what a linked list data structure isand how it compares to an array. What are the characteristics of a linked list?A linked list is an ordered collection of values. Linked lists are similar to arrays in the sense that they contain objects in a linear order. However they differ from arrays in their memory layout. Arrays are contiguous data structures and theyre composed of fixed-size data records stored in adjoining blocks of memory. In an array, data is tightly packedand we know the size of each data record which allows us to quickly look up an element given its index in the array: Linked lists, however, are made up of data records linked together by pointers. This means that the data records that hold the actual data payload can be stored anywhere in memorywhat creates the linear ordering is how each data record points to the next one: There are two different kinds of linked lists: singly-linked lists and doubly-linked lists. What you saw in the previous example was a singly-linked listeach element in it has a reference to (a pointer) to the next element in the list. In a doubly-linked list, each element has a reference to both the next and the previous element. Why is this useful? Having a reference to the previous element can speed up some operations, like removing (unlinking) an element from a list or traversing the list in reverse order. How do linked lists and arrays compare performance-wise?You just saw how linked lists and arrays use different data layouts behind the scenes to store information. This data layout difference reflects in the performance characteristics of linked lists and arrays:
Now, how does this performance difference come into play with Python? Remember that Pythons built-in list type is in fact a dynamic array. This means the performance differences we just discussed apply to it. Likewise, Pythons immutable tuple data type can be considered a static array in this casewith similar performance trade-offs compared to a proper linked list. Does Python have a built-in or native linked list data structure?Lets come back to the original question. If you want to use a linked list in Python, is there a built-in data type you can use directly? The answer is: It depends. As of Python 3.6 (CPython), doesnt provide a dedicated linked list data type. Theres nothing like Javas LinkedList built into Python or into the Python standard library. Python does however include the collections.deque class which provides a double-ended queue and is implemented as a doubly-linked list internally. Under some specific circumstances you might be able to use it as a makeshift linked list. If thats not an option youll need to write your own linked list implementation from scratch. How do I write a linked list using Python?If you want to stick with functionality built into the core language and into the Python standard library you have two options for implementing a linked list:
Now that weve covered some general questions on linked lists and their availability in Python, read on for examples of how to make both of the above approaches work. Option 1: Using collections.deque as a Linked ListThis approach might seem a little odd at first because the collections.deque class implements a double-ended queue, and its typically used as the go-to stack or queue implementation in Python. But using this class as a makeshift linked list might make sense under some circumstances. You see, CPythons deque is powered by a doubly-linked list behind the scenes and it provides a full list-like set of functionality. Under some circumstances, this makes treating deque objects as linked list replacements a valid option. Here are some of the key performance characteristics of this approach:
Using collections.deque as a linked list in Python can be a valid choice if you mostly care about insertion performance at the beginning or the end of the list, and you dont need access to the previous-element and next-element pointers on each object directly. Dont use a deque if you need O(1) performance when removing elements. Removing elements by key or by index requires an O(n) search, even if you have already have a reference to the element to be removed. This is the main downside of using a deque like a linked list. If youre looking for a linked list in Python because you want to implement queues or a stacks then a deque is a great choice, however. Here are some examples on how you can use Pythons deque class as a replacement for a linked list: >>> import collections
>>> lst = collections.deque()
# Inserting elements at the front
# or back takes O(1) time:
>>> lst.append('B')
>>> lst.append('C')
>>> lst.appendleft('A')
>>> lst
deque(['A', 'B', 'C'])
# However, inserting elements at
# arbitrary indexes takes O(n) time:
>>> lst.insert(2, 'X')
>>> lst
deque(['A', 'B', 'X', 'C'])
# Removing elements at the front
# or back takes O(1) time:
>>> lst.pop()
'C'
>>> lst.popleft()
'A'
>>> lst
deque(['B', 'X'])
# Removing elements at arbitrary
# indexes or by key takes O(n) time again:
>>> del lst[1]
>>> lst.remove('B')
# Deques can be reversed in-place:
>>> lst = collections.deque(['A', 'B', 'X', 'C'])
>>> lst.reverse()
deque(['C', 'X', 'B', 'A'])
# Searching for elements takes
# O(n) time:
>>> lst.index('X')
1
Option 2: Writing Your Own Python Linked ListsIf you need full control over the layout of each linked list node then theres no perfect solution available in the Python standard library. If you want to stick with the standard library and built-in data types then writing your own linked list is your best bet. Youll have to make a choice between implementing a singly-linked or a doubly-linked list. Ill give examples of both, including some of the common operations like how to search for elements, or how to reverse a linked list. Lets take a look at two concrete Python linked list examples. One for a singly-linked list, and one for a double-linked list. A Singly-Linked List Class in PythonHeres how you might implement a class-based singly-linked list in Python, including some of the standard algorithms: class ListNode:
"""
A node in a singly-linked list.
"""
def __init__(self, data=None, next=None):
self.data = data
self.next = next
def __repr__(self):
return repr(self.data)
class SinglyLinkedList:
def __init__(self):
"""
Create a new singly-linked list.
Takes O(1) time.
"""
self.head = None
def __repr__(self):
"""
Return a string representation of the list.
Takes O(n) time.
"""
nodes = []
curr = self.head
while curr:
nodes.append(repr(curr))
curr = curr.next
return '[' + ', '.join(nodes) + ']'
def prepend(self, data):
"""
Insert a new element at the beginning of the list.
Takes O(1) time.
"""
self.head = ListNode(data=data, next=self.head)
def append(self, data):
"""
Insert a new element at the end of the list.
Takes O(n) time.
"""
if not self.head:
self.head = ListNode(data=data)
return
curr = self.head
while curr.next:
curr = curr.next
curr.next = ListNode(data=data)
def find(self, key):
"""
Search for the first element with `data` matching
`key`. Return the element or `None` if not found.
Takes O(n) time.
"""
curr = self.head
while curr and curr.data != key:
curr = curr.next
return curr # Will be None if not found
def remove(self, key):
"""
Remove the first occurrence of `key` in the list.
Takes O(n) time.
"""
# Find the element and keep a
# reference to the element preceding it
curr = self.head
prev = None
while curr and curr.data != key:
prev = curr
curr = curr.next
# Unlink it from the list
if prev is None:
self.head = curr.next
elif curr:
prev.next = curr.next
curr.next = None
def reverse(self):
"""
Reverse the list in-place.
Takes O(n) time.
"""
curr = self.head
prev_node = None
next_node = None
while curr:
next_node = curr.next
curr.next = prev_node
prev_node = curr
curr = next_node
self.head = prev_node
And heres how youd use this linked list class in practice: >>> lst = SinglyLinkedList()
>>> lst
[]
>>> lst.prepend(23)
>>> lst.prepend('a')
>>> lst.prepend(42)
>>> lst.prepend('X')
>>> lst.append('the')
>>> lst.append('end')
>>> lst
['X', 42, 'a', 23, 'the', 'end']
>>> lst.find('X')
'X'
>>> lst.find('y')
None
>>> lst.reverse()
>>> lst
['end', 'the', 23, 'a', 42, 'X']
>>> lst.remove(42)
>>> lst
['end', 'the', 23, 'a', 'X']
>>> lst.remove('not found')
Note that removing an element in this implementation is still an O(n) time operation, even if you already have a reference to a ListNode object. In a singly-linked list removing an element typically requires searching the list because we need to know the previous and the next element. With a double-linked list you could write a remove_elem() method that unlinks and removes a node from the list in O(1) time. A Doubly-Linked List Class in PythonLets have a look at how to implement a doubly-linked list in Python. The following DoublyLinkedList class should point you in the right direction: class DListNode:
"""
A node in a doubly-linked list.
"""
def __init__(self, data=None, prev=None, next=None):
self.data = data
self.prev = prev
self.next = next
def __repr__(self):
return repr(self.data)
class DoublyLinkedList:
def __init__(self):
"""
Create a new doubly linked list.
Takes O(1) time.
"""
self.head = None
def __repr__(self):
"""
Return a string representation of the list.
Takes O(n) time.
"""
nodes = []
curr = self.head
while curr:
nodes.append(repr(curr))
curr = curr.next
return '[' + ', '.join(nodes) + ']'
def prepend(self, data):
"""
Insert a new element at the beginning of the list.
Takes O(1) time.
"""
new_head = DListNode(data=data, next=self.head)
if self.head:
self.head.prev = new_head
self.head = new_head
def append(self, data):
"""
Insert a new element at the end of the list.
Takes O(n) time.
"""
if not self.head:
self.head = DListNode(data=data)
return
curr = self.head
while curr.next:
curr = curr.next
curr.next = DListNode(data=data, prev=curr)
def find(self, key):
"""
Search for the first element with `data` matching
`key`. Return the element or `None` if not found.
Takes O(n) time.
"""
curr = self.head
while curr and curr.data != key:
curr = curr.next
return curr # Will be None if not found
def remove_elem(self, node):
"""
Unlink an element from the list.
Takes O(1) time.
"""
if node.prev:
node.prev.next = node.next
if node.next:
node.next.prev = node.prev
if node is self.head:
self.head = node.next
node.prev = None
node.next = None
def remove(self, key):
"""
Remove the first occurrence of `key` in the list.
Takes O(n) time.
"""
elem = self.find(key)
if not elem:
return
self.remove_elem(elem)
def reverse(self):
"""
Reverse the list in-place.
Takes O(n) time.
"""
curr = self.head
prev_node = None
while curr:
prev_node = curr.prev
curr.prev = curr.next
curr.next = prev_node
curr = curr.prev
self.head = prev_node.prev
Here are a few examples on how to use this class. Notice how we can now remove elements in O(1) time with the remove_elem() function if we already hold a reference to the list node representing the element: >>> lst = DoublyLinkedList()
>>> lst
[]
>>> lst.prepend(23)
>>> lst.prepend('a')
>>> lst.prepend(42)
>>> lst.prepend('X')
>>> lst.append('the')
>>> lst.append('end')
>>> lst
['X', 42, 'a', 23, 'the', 'end']
>>> lst.find('X')
'X'
>>> lst.find('y')
None
>>> lst.reverse()
>>> lst
['end', 'the', 23, 'a', 42, 'X']
>>> elem = lst.find(42)
>>> lst.remove_elem(elem)
>>> lst.remove('X')
>>> lst.remove('not found')
>>> lst
['end', 'the', 23, 'a']
Both example for Python linked lists you saw here were class-based. An alternative approach would be to implement a Lisp-style linked list in Python using tuples as the core building blocks (cons pairs). Heres a tutorial that goes into more detail: Functional Linked Lists in Python. Python Linked Lists: Recap & RecommendationsWe just looked at a number of approaches to implement a singly- and doubly-linked list in Python. You also saw some code examples of the standard operations and algorithms, for example how to reverse a linked list in-place. You should only consider using a linked list in Python when youve determined that you absolutely need a linked data structure for performance reasons (or youve been asked to use one in a coding interview.) In many cases the same algorithm implemented on top of Pythons highly optimized list objects will be sufficiently fast. If you know a dynamic array wont cut it and you need a linked list, then check first if you can take advantage of Pythons built-in deque class. If none of these options work for you, and you want to stay within the standard library, only then should you write your own Python linked list. In an interview situation Id also advise you to write your own implementation from scratch because thats usually what the interviewer wants to see. However it can be beneficial to mention that collections.deque offers similar performance under the right circumstances. Good luck andHappy Pythoning! Read the full Fundamental Data Structures in Python article series here. This article is missing something or you found an error? Help a brother out and leave a comment below. Python TricksGet a short & sweet Python Trick delivered to your inbox every couple of days. No spam ever. Unsubscribe any time. Curated by yours truly. Website x Improve Your Python with a fresh PythonTrick every couple of days No spam ever. Unsubscribe any time. Website Related Articles:
|