This article will explain in simple terms what linked lists are, why they’re useful, and how to use them in the Python programming language.
In Python, a list is an array of data – a simple list of values where each item has a value and a position in the list.
Lists are indexed (so the positions start counting at position 0, not 1).
For more information on lists in Python, check out these LinuxScrew articles:
- Python List ‘sort()’ Method – Sorting Lists in Python Easily
- How To Remove Items From A List in Python (With Examples)
- Python Find in List: Check if an Element is Present
- Python: Find in a List and Return Values [using ‘filter’]
A list, and all values in it, are stored together in your computer’s memory as one big value.
Linked lists are just like lists – every item in them has a value and a position.
However, in linked lists, the values are not stored together in memory – the elements in the list are stored separately. This has implications for simplicity and performance.
Rather than storing each item sequentially (with a simple index and value for each item), each entry in a linked list stores the value of the item and a pointer to the next item in the list.
Storing the address of the next item in memory is important so that it can be found in the computer’s memory – remember, unlike lists, the values aren’t stored together.
Why Linked Lists?
Why is this advantageous? It makes reorganizing or modifying the list a lot less intensive for the computer. With a list, the whole array of values in it has to be reindexed if an item is added or removed, but with a linked list, the pointer for the value preceding the newly added or removed item just needs to be updated to point to the new next item in the list.
This is great for performance – but a bit more complex, so lists are still used instead of linked lists when the data isn’t expected to be changing.
How to Create a Linked List
Python doesn’t have a built-in Linked List class – but building your own is easy and is also a good demonstration of how classes can be used in Object-Oriented Programming.
Implementing a Node Class
The below code example implements a Python class. A class is a definition we can use to create variables of that class.
In this case, a Node class is defined, which will accept and store a data value and a nextNode value for an item in a linked list.
The __init__ method of the class will accept the value for the node and a location for the next node so that they can be stored when a variable of the Node class is being created:
# Define Node Class class Node(object): # Initialise a new Node object with given data and nextNode def __init__(self, data=None, nextNode=None): self.data = data # self is a reference to the variable of the class Node we are working within - it's an internal reference to itself self.nextNode = nextNode # Return the value of the data in the Node def __repr__(self): return self.data
The __repr__ method is another special Python method – it returns the value of the variable as a string. One has been added to the Node class to override the default, as we only want the node to represent the data it contains when we retrieve the node’s value.
Implementing a Linked List Class
Now that we have a class for items (nodes) in a linked list, we can define a linked list class to hold them.
A linked list only really needs one piece of information when initialized using the init method – the head – or the first item in the list. The rest of the items in the list will be found using nextNode address in each node:
# Define LinkedList Class class LinkedList(object): # Initialise a new LinkedList with an optional first Node def __init__(self, head=None): self.head = head # Return the value of all of the nodes in the list, comma separated def __repr__(self): currentNode = self.head nodes =  while currentNode is not None: # While there is a nextNode present, keep adding their values to the return value nodes.append(currentNode.data) currentNode = currentNode.nextNode return ", ".join(nodes) # Return the value of all of the nodes separated by commas # Make the linked list iterable, so it can be looped over def __iter__(self): node = self.head while node is not None: yield node node = node.nextNode # Calculate the size of the list by reading each node's nextNode value and incrementing the count for each Node that exists in the LinkedList def size(self): currentNode = self.head count = 0 while currentNode is not None: count += 1 currentNode = currentNode.nextNode return count # Insert a new value at the top of the linked list (first or head value) - a new Node is created containing data, it's nextNode value is set to the previous head of the linked list, and the head is then replaced with the new Node def insertHead(self, data): newNode = Node(data, self.head) self.head = newNode # Insert a new value at the end of the Linked List - this involves traversing the whole linked list until the last node is found, then setting its nextNode value to the new node def insertLast(self, data): if self.head is None: self.head = Node(data) return for currentNode in self: # self can be iterated due to the above __iter__ method which returns an iterable copy of the linked list pass currentNode.nextNode = Node(data)
The LinkedList class also contains a __repr__ method for reading the value of the whole list. In this case, it’s been overridden to return the values in the list by looping through them using each node’s value and the pointer to the next node, joining the values with commas separating them.
The __iter__ method presents an iterable interpretation of the linked list so that its values can be looped through.
Additional methods have been added for adding items to the linked list and calculating the size of the list. These could all be done outside of the class just as easily, but defining these functions as class methods means they’re reusable – you only have to write the code once, and it can be called from any variable of that class.
How to Use a Linked List
OK! There’s a bit of code above. Hopefully, it all makes sense, and the comments clear up any confusion. Here’s an example using the above-defined classes, creating and modifying a simple linked list:
# Create a new variable with the class LinkedList myLinkedList = LinkedList() # Add some values to the list myLinkedList.insertHead("cat") myLinkedList.insertHead("dog") myLinkedList.insertLast("bird") # Print details about the list print(myLinkedList.size()) print(myLinkedList)
As you can see, the new linked list works as intended and provides a flexible list that can grow to any size. The LinkedList class can be added to at any time to add functionality to the linked list, depending on what you need to do. For example, you could add your own sorting or formatting methods or add the ability to insert list items before or after other items in the list.