If you are learning data structures, a Linked List is one of the data structures you should know, albeit not so common, linked lists are similar to Lists (or arrays); you probably never heard or used them until now, but in the right context they prove to be useful.
In this article, you will learn:
- What linked lists are.
- Performance of linked lists.
- Types of linked lists.
- How to Implement your own linked list.
What are linked lists?
A linked list is a sequence of data elements, which are connected together via links. Each element (node) in a linked list contains a connection to another data element in form of a pointer.
You should know:
That every element in a linked list is called a Node, and every node contains a data (value to be stored) and next (reference to the next node) fields.
A linked list therefore is a collection of nodes, with the last node pointing to None
Performance of linked lists.
In a linked list, the time complexity for the operations is given as:
- Indexing - O(n)
- Insertion - O(1)
- Deletion - O(1)
- Search - O(n)
Space complexity however is O(n).
Types of linked lists.
There are 3 main types of linked lists;
- Singly-linked lists: Each node consists of only one pointer to the next (which we are learning)
- Doubly-linked lists: Each node contains two pointers, a pointer to the next node and a pointer to the previous node.
- Circular-linked lists: In a circular linked list the last node points to the first node or any other node before it thereby forming a loop
Implementing a linked list in Python
This comes in 2 parts, creating our list Node, and the Linked List itself. So, first thing first, create a class to represent each Node of the linked list
class Node:
def __init__(self, data):
self.data = data
self.next = None
As you can see each node contains just 2 fields, the data, and next.
Next, create a class to represent your linked list :
class LinkedList:
def __init__(self, nodes=None):
self.head = None
if nodes is not None:
node = Node(data=nodes.pop(0))
self.head = node
for n in nodes:
node.next = Node(data=n)
node = node.next
Putting it all together
Let's update each of our classes with a repr function so our new code looks like this :
class Node:
def __init__(self, data):
self.data = data
self.next = None
def __repr__(self):
return self.data
class LinkedList:
def __init__(self, nodes=None):
self.head = None
if nodes is not None:
node = Node(data=nodes.pop(0))
self.head = node
for n in nodes:
node.next = Node(data=n)
node = node.next
def __repr__(self):
node = self.head
nodes = []
while node is not None:
nodes.append(node.data)
node = node.next
nodes.append("None")
return " -> ".join(nodes)
The code above would rightly allow us to create a linked list, notice that in the LinkedList init function if the node is not passed we initialized it to None.
my_list = LinkedList()
firstNode = Node("1")
my_list.head = firstNode
secondNode = Node("2")
firstNode.next = secondNode
print(my_list)
>>> 1 -> 2 -> None
Linked Lists Methods
To help us use our linked lists even more efficiently, we would implement some methods to:
- Traverse a linked list.
- Insert a new node at the beginning.
- Insert a new node at the end.
Traverse a linked list
Traversing a linked list means iterating through the list, and we add the iter function to allow us to replicate the same behavior from regular lists (arrays)
def __iter__(self):
node = self.head
while node is not None:
yield node
node = node.next
The code above goes through the list if it does not equal to None and yields every node before re-assigning the node to the next node if it exists.
Insert node at the beginning
def add_at_beginning(self, node):
node.next = self.head
self.head = node
In the above code, you're setting the next value to the present head value before re-assigning head to the new node
Insert node at the end
def add_at_end(self, node):
if self.head is None:
self.head = node
return
for current in self:
pass
current.next = node
While inserting at the end is similar to inserting at the beginning, first, you want to traverse the whole list until you reach the end. Next, you want to set current as the last node on the list. Finally, you want to add the new node as the next value of that current.
Our final code containing our methods should look like this
class Node:
def __init__(self, data):
self.data = data
self.next = None
def __repr__(self):
return self.data
class LinkedList:
def __init__(self, nodes=None):
self.head = None
if nodes is not None:
node = Node(data=nodes.pop(0))
self.head = node
for elem in nodes:
node.next = Node(data=elem)
node = node.next
def __repr__(self):
node = self.head
nodes = []
while node is not None:
nodes.append(node.data)
node = node.next
nodes.append("None")
return " -> ".join(nodes)
# Traverse a Linked List
def __iter__(self):
node = self.head
while node is not None:
yield node
node = node.next
# Insert a new node at the beginning
def add_at_beginning(self, node):
node.next = self.head
self.head = node
# Insert a new node at the end
def add_at_end(self, node):
if self.head is None:
self.head = node
return
for current_node in self:
pass
current_node.next = node
To wrap up a final example, have a look at how it works:
my_list = LinkedList()
firstNode = Node("1")
secondNode = Node("2")
my_list .head = firstNode
firstNode.next = secondNode
my_list.add_at_beginning(Node("3"))
my_list.add_at_end(Node("4"))
print(my_list)
>>> 3 -> 1 -> 2 -> 4 -> None
Conclusion
In this article, you learned quite a few things, The most important are:
- What linked lists are
- What the other types of linked lists are
- Time and Space Complexities of a linked list
- How to implement your own linked list and node classes, plus relevant methods
I hope you enjoyed reading it as much as I enjoyed writing it :)