Python Linked Lists : Easy Steps to Get Started
Follow this guide and you'll never need to relearn Linked Lists again.
Ever wondered how efficiently Python handles data connections? Linked lists are a powerful data structure for managing connections and dynamic memory. Unlike arrays, they store elements in separate nodes linked together. Let's explore how Python efficiently handles linked lists!
What is linked list?
Linked lists are a linear data structure to store data in a linked system. It means, the store box of data are not connected in a contiguous way in memory. These are called nodes (elements of a linked list). In a linked list, the nodes can be shuffled at any point. To relate more think of a train and it its compartments. Each compartment are connected with it's next and previous one with a link. The compartments can be removed, can be added, can be repositioned and many more. And each of them are independent nodes. The first node is called head and the last node is called tail. Head is a crucial part because we access a linked list via its head. Each node contains two parts: data and a reference. The data part holds the node's value, while the reference part(location/address of the next node) points to the next node, creating a link between the current node and the next one
Difference between Linked list and Array
In a python list, elements have indexes. But in linked list, elements don't have any. In a python list, the elements are stored contiguously in memory but in linked list, the elements are scattered and connected with the next node through link. These are the main differences of python list and linked list
Types of linked list
There are four types of linked lists -
Singly Linked list
Circular Singly Linked List
Doubly linked list
Circular Doubly Linked List
In a singly linked list, the nodes are defined with data and the reference which stores the physical memory location of the next node. The last node has null pointer which indicates the end of the list, the reference is always NULL. In a circular linkedlist, the last node points back to its first node. It store the physical location of the first node. You can see clearly in the given graph. The last node pointing to the first node basically creates a circular formation.
Moving to the next, the Doubly linked list. It is similar to a singly linked list, but the only difference is, here we have also the reference to the the previous node. This means each node has two references : one to the next node and one to the previous node. Doubly linked list allows us to traverse back too. It provides a flexibility to traverse in both direction.
A Circular doubly linked list is similar to doubly linked list, but with a key difference with the first and the last node. Notice that, in circular doubly linked list, the last node's next reference points to the physical location of the first node, and the first node's previous reference points to the physical location of the last node. This creates a circular structure where you can traverse the list continuously in both directions.
Linked list in memory
Nodes in a linked list can't be accessed via indexing like elements in a python lists.
In memory, python list elements are stored sequentially. However, in a linked list, elements are stored randomly and connected through links.
As you can see, the nodes are stored separately. Each node requires an extra memory space for a reference to the next node. This random allocation allows for a insertion as many nodes as needed without reserving contiguous specific memory location. However, as we don't know the location, finding any node requires looping through the entire linked list, which is a disadvantage of linked list.
All about Nodes and Node class constructor
To create a node class, we need to understand the characteristics of a single node. I have attached a simpler formation to visualize easily.
Each node contains two parts : data, and the reference to the next node (and prolly a reference to the first node too if it's a doubly linked list).
To create a node class, we need to define its attributes and behaviors. Each node holds data and a reference to the next node. The node class only concentrates with storing its own value and a reference to the next node. It does not know anything about the next node.
class Node:
def __init__(self, value):
self.value = value #data storing
self.next = None #reference
new_node = Node(10)
print(new_node)
Here, the Node class has two attributes:
value: Stores the data of the node.next: A reference to the next node in the linked list, initially set toNone.
It will print out no value because we have not created any method to print the value. It will just show the memory location. This class will serve as the building block for the linked list class we'll create later.
Linked list constructor - creating a Singly linked list
We will create a linked list using the Node class we defined just now where we had the value and the pointer as attributes.
Let's name the class LinkedList. The LinkedList class will include further attributes for the head and tail of the list. Let's make one for a very simple linked list with one element.
#creating linked list with one node
class LinkedList:
def __init__(self, value):
new_node = Node(value)
self.head = new_node #it's going to create a link from head to new node
self.tail = new_node #it's going to create a link from tail to new node
self.length = 1 #makes more efficient
new_linked_list = LinkedList(10)
print(new_linked_list) #memory location
print(new_linked_list.head.value) #we are accessing value from the node class
print(new_linked_list.tail.value) # accessing tail value
print(new_linked_list.length)
#creating empty linked list
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
self.length = 0
By writing self.head, we are creating the head attribute. Then, when we put self.head = new_node it is going to create a link from head to the new node that we have created. Same thing applies with the tail attribute.
And, If you want to initialize an empty linked list, in this case we won't be providing any parameters. We are going to create an empty linked list with both head and tail pointing to None.
if we just print new_linked_list it will only show us the memory location. To get the value, we have to access the object attribute using the dot. Here, by print(new_linked_list.head), we are accessing the head from LinkedLink and by adding .value, we are accessing the value from the Node class.
Insertion in Singly linked list
We can insert a node at various position within a linked list, such as -
at the beginning of a linked list [prepend]
at the end of a linked list [append]
after a node in any place in the middle of the linked list [insert]
Append method
Too add a node at the end of the linked list, we need to follow three steps :
create a new node. [ 50 --> None ]
update the current last node's next pointer to point to the new node
[
self.tailrefers to the tail's vertical arrow.self.tail.nextpoints to the yellow arrow]
update the "tail ->" to point to the new node
[
self.tail = new_node]
If you want to append an element in empty linked list, you need to create a link where head and tail pointing to none.
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
self.length = 0
def append(self, value): # time + space complexxity: o(1)
new_node = Node(value) #using Node class
if self.head = None: #o(1) time complexity
self.head = new_node #o(1) time complexity
self.tail = new_node #o(1) time complexity
else: #o(1) time complexity
self.tail.next = new_node #o(1) time complexity
self.tail = new_node #o(1) time complexity
self.lenght += 1 #o(1) time complexity
How do we know if a linked list is empty? To check if a linked list is empty, you can look at the head attribute. If the head is None, the list is empty. Another way to check is by observing the length of the list. If the length is zero, it means there are no elements in the linked list. However, if the linked list is not empty, we put else condition and here we are going to implement our logic by following the pre-stated three rules.
Proper way to print a linked list " __str__ "
To see the linked list in a proper way after appending elements, you need to implement a "__str__" method in the LinkedLink class. It will return a string representation of the linked list class.
let's create a temp_node pointing to the head. temp_node will be iterating through the entire linked list while collecting the node values in str form in the result variable unless it finds tail.next = None
Here's the code of __str__ method:
def __str__(self):
result = ''
temp_node = self.head
while temp_node is not None:
result += str(node.value)
if temp_node.next is not None:
result += "->"
temp_node = temp_node.next #it will break from the loop
return result
To continue to the next node, we set temp_node = temp_node.next and check the while loop condition. This process stores string values until we reach the last node. At the last node, it stores the final string value. When temp_node.next is None, the loop breaks, and the string representation of the linked list is returned.
Prepend method
Too add a node at the starting, we need to follow three steps :
- create a new node [50 -> None]
updating new node's next reference to point to the
head
update the
headto point to the new node
Again. if you have elements in the linked list the logics will be different. if you have no elements in the linked list the logic will be different.
class LinkedList: def __init__(self): self.head = None self.tail = None self.length = 0 def prepend(self,value): new_node = Node(value) #cons time complexity, O(1) if self.head == None: # O(1) time complexity self.head = new_node # O(1) time complexity self.tail = new_node # O(1) time complexity else: new_node.next = self.head # O(1) time complexity self.head = new_node # O(1) time complexity self.length += 1 # O(1) time complexity # they don't requires any additional space # time + space complexity = O(1)
Create a new node. check if the linked list is empty or not, write two conditions for this. Other operations are same as the append method.
Insert method
Now we will learn how to insert randomly.
First we will create a node. Let's say we want to insert it at the index of two. We will set a temp_node and start a loop to find two, and we will stop at the 1st index (index-1)
Then we will update the new nodes next reference to point to the node that is located after index-1
We are going to update the current nodes next reference to point to the new node.
Thus, the new node will be implanted at the 2nd index.
Now, for the code
def insert(self, index, value):
new_node = Node(value) # --------> O(1) time complexity
#to avoid edge case
if index < 0 or index > self.length: # --------> O(1) time complexity
return False # --------> O(1) time complexity
#if the linked list is empty
elif self.length == 0: # --------> O(1) time complexity
self.head = new_node # --------> O(1) time complexity
self.tail = new_node # --------> O(1) time complexity
elif index == 0: #if you want to add at index of 0
new_node.next = self.head # --------> O(1) time complexity
self.head = new_node # --------> O(1) time complexity
else: # --------> O(1) time complexity
temp_node = self.head # --------> O(1) time complexity
for _ in range(index-1): # --------> O(n) time complexity
temp_node = temp_node.next # --------> O(1) time complexity
new_node.next = temp_node.next # --------> O(1) time complexity
temp_node.next = new_node # --------> O(1) time complexity
self.length += 1 # --------> O(1) time complexity
return True
# Time complexity : O(n)
# space cpmplexity : O(1)
I have used _ to look instead of i. because I am not going to use the iteration variable anywhere.
Traversal method
Traversing is necessary to access or search for a specific element. Specially for linked list because we can't access directly using index, we have to traverse starting with the head.
def traverse(self):
current = self.head # --------> O(1) time complexity
# while current != None:
while current: # --------> O(n) time complexity
print(current.value) # --------> O(1) time complexity
current = current.next # --------> O(1) time complexity
# time complexity - O(n)
# space complexity - o(1)
Search method
def search(self, target):
current = self.head
while current:
if current != target:
current = current.next
else:
print(current.value)
#or
def search(self,target):
current = self.head # --------> O(1) time complexity
idx = 0 #in case if you wanna get the index
while current: # --------> O(N) time complexity
if current.value == target: # --------> O(1) time complexity
return True # --------> O(1) time complexity
current = current.next # --------> O(1) time complexity
idx += 1 # --------> O(1) time complexity
return False
# time complexity - O(n)
# space complexity - o(1), no additional space in needed
Get method
The get method in a linked list is used to retrieve the value of a node at a specific position (index) in the list. Here’s how it works:
def get(self, index):
if index == -1:
return self.tail
elif index < -1 or index > self.length: #edge case
return None
current = self.head
for _ in range(index):
current = current.next
return current
# time complexity - O(n)
# space complexity - o(1)
Set method
The set method in a linked list is used to update the value of a node at a specific position (index) in the list. This method allows you to modify the data stored in a particular node without changing the structure of the list.
def set_value(self, index, value):
temp = self.get(index)
if temp:
temp.value = value
return True
return False
# time complexity - O(n)
# space complexity - o(1)
Pop first method
Pop first method removes the first node from the linked list and returns it.
def pop_first(self):
popped_node = self.head
if self.length == 0
return None
if self.length ==1:
self.head = None
self.tail = None
else:
self.head = popped_node.next #self.head = self.head.next
popped_node.next = None
self.length -= 1
return pooped_node.value
# time complexity - O(1)
# space complexity - o(1)
Pop method
Pop method removes the last node from the linked list and returns it.
def pop(self):
popped_node = self.tail
if self.length == 0 :
return None
elif self.length == 1:
self.head = self.tail = None
else:
temp = self.head
while temp.next is not self.tail: # --------> O(N) time complexity
temp = temp.next
self.tail = temp
temp.next = None
self.length -= 1
return popped_node
# time complexity - O(N)
# space complexity - o(1)
Remove method
remove any node you want.
def remove(self, index):
if index == 0:
return self.pop_first()
if index > self.length or index < -1 :
return None
if index == self.length -1 or index == -1:
return self.pop() # --------> O(N) time complexity
prev_node = self.get(index-1) # --------> O(N) time complexity
popped_node = prev_node.next
prev_node.next = popped_node.next
popped.next = None
self.length -= 1
return popped_node
# time complexity - O(N)
# space complexity - o(1)
Delete
How to delete all nodes? Answer is simple. If you set the head and tail pointer to None, it will remove all the references to the nodes in the linked list allowing the garbage collector to reclaim the memory used by those nodes.
def delete_all(self) :
self.head = self.tail = None
self.length = 0
# time complexity - O(1)
# space complexity - o(1)
Time and space complexity
| method | Time complexity | space complexity |
| create | O(1) | O(1) |
| append | O(1) | O(1) |
| prepend | O(1) | O(1) |
| insert | O(N) | O(1) |
| search | O(N | O(1) |
| traverse | O(N) | O(1) |
| get | O(N) | O(1) |
| set | O(N) | O(1) |
| pop first | O(1) | O(1) |
| pop | O(N) | O(1) |
| remove | O(N) | O(1) |
| delete all nodes | O(1) | O(1) |
The entire code
class Node:
def __init__(self, value):
self.value = value #data storing
self.next = None #reference point to the next
# Node done!! Now head, tail creating
class LinkedList:
def __init__(self, value)
new_node = Node(value)
self.head = new_node
self.tail = new_node
self.length = 1
#OR,
class LinkedList:
def __init__(self):
self.head = None
self.head = None
self.length = 0
#you can use any of them!
def __str__(self):
result = ''
temp_node = self.head
while temp_node in not None:
result += str(temp_node.value)
if temp_node.next != None:
result += "->"
temp_node = temp_node.next #continuing to the next node
return result
#append method
def append(self,value):
new_node = Node(value)
if self.head = None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
self.length += 1
#prepend method
def prepend(self,value):
new_node = Node(value)
if self.head == None:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head = new_node
self.length += 1
#insert method
def insert(self, index, value):
new_node = Node(value)
if index < 0 or index > self.length:
return False
elif index == 0:
new_node.next = self.head
self.head = new_node
else:
temp_node = self.head
for _ in range(index-1):
temp_node = temp_node.next
new_node.next = temp_node.next
temp_node.next = new_node
self.length += 1
return True
#traversing
def traverse(self):
current = self.head
while current:
print(current.value)
current = current.next
#search method
def search(self,target):
current = self.head
idx = 0 #in case if you wanna get the index
while current:
if current.value == target:
return idx #i want to get the idx
current = current.next
idx += 1
return False
#get method
def get(self, index):
if index == -1:
return self.tail
elif index < -1 or index > self.length: #edge case
return None
current = self.head
for _ in range(index):
current = current.next
return current
#set value
def set_value(self, index, value):
temp = self.get(index)
if temp:
temp.value = value
return True
return False
#pop first method
def pop_first(self):
popped_node = self.head
if self.length == 0
return None
if self.length ==1:
self.head = None
self.tail = None
else:
self.head = popped_node.next #self.head = self.head.next
popped_node.next = None
self.length -= 1
return pooped_node.value
#pop method
def pop(self):
popped_node = self.tail
if self.length == 0 :
return None
elif self.length == 1:
self.head = self.tail = None
else:
temp = self.head
while temp.next is not self.tail: # --------> O(N) time complexity
temp = temp.next
self.tail = temp
temp.next = None
self.length -= 1
return popped_node
#remove method
def remove(self, index):
if index == 0:
return self.pop_first()
if index > self.length or index < -1 :
return None
if index == self.length -1 or index == -1:
return self.pop()
prev_node = self.get(index-1)
popped_node = prev_node.next
prev_node.next = popped_node.next
popped.next = None
self.length -= 1
return popped_node
#delete method
def delete_all(self) :
self.head = self.tail = None
self.length = 0
new_linked_list = LinkedList()
new_linked_list.append(10)
new_linked_list.append(20)
new_linked_list.append(30)
print(new_linked_list) #output: 10->20->30
new_linked_list.prepend(40) #output: 40->10->20->30
new_linked_list.insert(2,50)
new_linked_list.traverse
new_linked_list.search(70) #output False
new_linked_list.search(20) #output 1
print(new_linked_list.get(2)) #output mempry location
print(new_linked_list) #output 10 -> 20 -> 30
print(new_linked_list.set_value(2,50))
print(new_linked_list) #output 10 -> 20 -> 50