In this blog, we will discuss about how to implement Linked List in Python. We will also discuss its properties, advantages, and disadvantages.
I chose Python as the primary language to implement the linked list data structure because of its readability and the ease in implementing data structures.
What is linked list?
Linked list is a linear data structure as well as a dynamic data structure. It consists of nodes where each node contains a data field(to store some data values) and a reference to the next node in the list.
You can think each of it's node as a container with two chambers. In one of the chambers you have a value, it can be an Integer or a String, and in other chamber you have an address of the next container (Node). It's that simple.
Here’s an image of a linked list:
THEORY PART:
Why use linked lists?
Linked list is often compared to arrays. Whereas an array is a fixed size of sequence, a linked list can have its elements to be dynamically allocated. What are the advantages and disadvantages of these characteristics? Here are some major ones:
Advantages:
No wastage of memory: It only allocates the memory required for values to be stored or inserted because size of the linked list increase or decrease at run time. So, there is no need to pre-allocate the memory.
Implementation of stack and queue: Linear data structures like stack and queues are often easily implemented using a linked list.
Easy to insert and delete a node: Insertion and deletion node operations are easily implemented in a linked list.
Disadvantages:
Memory Usage: More memory is required to store elements in linked list as compared to array. Because in linked list each node contains a pointer and it requires extra memory for itself.
Linear look up time: When looking for a value in a linked list, you have to start from the beginning of chain, and check one element at a time for a value you’re looking for. For example, if we want to access a node at position n then we have to traverse all the nodes before it. So, time required to access a node is large.
Reverse Traversing: In linked list reverse traversing is really difficult. In case of doubly linked list its easier but extra memory is required for back pointer hence wastage of memory.
ENOUGH TALK, LET'S IMPLEMENT IT:
CREATE A NODE CLASS:
# this Node class we will use to create multiple nodes(containers)
# for our linked lists
class Node:
def __init__(self, value=None, next=None):
self.value = value # head is the node from which your are pointing towards next node
self.next = next # next is the next node where pointer is pointing
CREATE A LINKED LIST CLASS:
class LinkedList:
# we only need head for linked list which will act
# as a starting element, all the other elements we will insert using Node class
def __init__(self):
self.head = None
METHOD TO INSERT AN ELEMENT:
def insert(self, element):
# create a new node and assign an element which we're
# receiving as an argument, to the value of that Node
# assign our current head as the next element of the newly created node
node = Node(element, self.head)
# and make newly created node as the new head of our linked list
# this method will insert the elements from left
self.head = node
In above method as soon as we get an element which we have to insert in our linked list, we will create a new Node from it then simply shift our current head and make newly created node as our new head. So, that means for our newly created head the previous head will be the next node. (read that again and try to visualize)
Before testing our insert() method we have to create a helper method which will print our linked list.
METHOD TO PRINT THE LINKED LIST:
def print(self):
# store our head in 'itr' variable
# self.head is an entire Node which has value as well as next.
itr = self.head
linked_list = '' # initialize 'linked_list' variable as type str
# until our self.head is not None this while loop will run
while itr:
# concatenate the itr.value (value of the Node) to the 'linked_list' variable
linked_list += str(itr.value) + " --> "
# assign itr as the next element
itr = itr.next
# if there is no next element, itr will become None
print(linked_list)
Let's insert some elements and print our linked list
lst = LinkedList()
lst.insert(1)
lst.insert(2)
lst.insert(3)
lst.insert(4)
lst.print()
Output:
4 --> 3 --> 2 --> 1 -->
As we insert 1 first it becomes our head, then after inserting 2, it becomes our new head and 1 (the previous head) becomes it's next node. same for 3 and 4.
METHOD TO CALCULATE THE LENGTH OF THE LINKED LIST:
def length(self):
# store our head in 'itr' variable
# self.head is an entire Node which has value as well as next.
itr = self.head
count = 0 # set count to 0
while itr:
# we will travel through our linked list till
# we reach at the end where itr == None
count += 1 # increase the count until there is an element i.e. itr != None
# assign itr as the next element
itr = itr.next
# as soon as itr becomes None return the total count
return count
Let's insert some elements and print the length of our linked list
lst = LinkedList()
lst.insert(1)
lst.insert(2)
lst.insert(3)
lst.insert(4)
print(lst.length()) # this will print 4 as we've inserted 4 elements
METHOD TO INSERT AN ELEMENT AT THE END OF THE LINKED LIST:
def insert_at_end(self, element):
# first check if there is any head present
# if there is no head that means the linked list is empty
if self.head is None:
# as linked list is empty simply create a node with received element
# and assign it as our new head
node = Node(element, None)
self.head = node
return
# if head is present that means our linked_list is not empty
itr = self.head
while itr.next:
# until there is next node present don't insert the value
itr = itr.next
# after reaching to the last node start inserting the values
# here the itr is the last node of the linked list, simply insert a new node next to it
itr.next = Node(element, None)
Let's insert some elements at the end of our linked list and print it out:
lst = LinkedList()
lst.insert_at_end(1)
lst.insert_at_end(2)
lst.insert_at_end(3)
lst.insert_at_end(4)
lst.print()
Output:
1 --> 2 --> 3 --> 4 -->
While inserting 1, the linked list is empty. So, it will assign 1 as the head of our linked list. After inserting 2, the linked list already has 1 as it's head so, it will look for the next node, as there is no next node it will place 2 next to 1. Same for 3 and 4.
METHOD TO INSERT AN ELEMENT AT PERTICULAR INDEX:
def insert_at(self, index, element):
# first check if there is any head present
# if there is no head that means the linked list is empty
if self.head is None:
print("linked list is empty")
return
# use self.length() to calculate the length (OOP stuff)
if index > (self.length()):
# index is greater than index of the last element
print("index is out of range")
return
itr = self.head
count = 0
while itr:
# stop before the index where we want to insert an element
if count == index - 1:
# and add the element next to it
# e.g. if we want to insert an element at index 3
# we will stop at 2 and insert an element next to it so
# automatically the element will be at index 3 it's that simple
itr.next = Node(element, itr.next)
# make the node which is already present in that index
# as next node of the element that we are inserting
break
itr = itr.next
count += 1
Let's insert an element at particular index and print the linked list:
lst = LinkedList()
lst.insert_at_end(1)
lst.insert_at_end(2)
lst.insert_at_end(3)
lst.insert_at_end(4)
lst.print() # printing before replacement
lst.insert_at(3, 45)
lst.print() # printing after insertion
Output:
# output before insertion
1 --> 2 --> 3 --> 4 -->
# output after insertion
1 --> 2 --> 3 --> 45 --> 4 -->
We want to insert 45 at the index 3 so we will stop at index 2 and insert 45 next to the node present at index 2 so automatically our element will be placed at index 3 and at the same time we will make previously present element at index 3 as next node of newly inserted element. (read that again and try to visualize)
METHOD TO REPLACE AN ELEMENT AT PERTICULAR INDEX:
def replace_at(self, index, element):
# first check if there is any head present
# if there is no head that means the linked list is empty
if self.head is None:
print("linked list is empty")
return
# use self.length() to calculate the length (OOP stuff)
if index > (self.length()-1):
# index is greater than index of the last element
print("index is out of range")
return
# if head is present that means our linked_list is not empty
itr = self.head
count = 0
# until itr is not None we will travel through the linked list
while itr:
# if count value is equal to the index that we are looking for
if count == index:
# replace that Node's value with the element that we've received in an argument
itr.value = element
break
itr = itr.next
# while travelling we will keep increasing the count
# until we don't get count matching to the index
count += 1
Let's replace an element at particular index and print the linked list:
lst = LinkedList()
lst.insert_at_end(1)
lst.insert_at_end(2)
lst.insert_at_end(3)
lst.insert_at_end(4)
lst.print() # printing before replacement
lst.replace_at(0, 9)
lst.replace_at(2, 45)
lst.print() # printing after replacement
Output: (read the comments in code snippet for explanation)
# output before replacement
1 --> 2 --> 3 --> 4 -->
# output after replacement
9 --> 2 --> 45 --> 4 -->
METHOD TO REMOVE AN ELEMENT AT PERTICULAR INDEX:
def remove_at(self, index):
# if the index is 0, simply remove the head
if index == 0:
# assign node present next to the head as new head
# so automatically our current head will be gone
self.head = self.head.next
itr = self.head
count = 0
while itr:
# stop before the index where we want to delete an element
if count == index - 1:
# e.g. if we want to delete an element at index 3 we,
# will stop at index 2 and will replace index 3 item as index 4
# so that means item at index 3 is deleted
itr.next = itr.next.next
break
itr = itr.next
count += 1
Let's remove/delete an element at particular index and print the linked list:
lst = LinkedList()
lst.insert_at_end(15)
lst.insert_at_end(25)
lst.insert_at_end(35)
lst.insert_at_end(45)
lst.print() # printing before removal
lst.remove_at(1)
lst.print() # printing after removal
Output:
# output before removal
15 --> 25 --> 35 --> 45 -->
# output after removal
15 --> 35 --> 45 -->
We want to remove 25 which is present at the index 1 so we will stop at index 0 and replace 25 with an element present at the index 2. (read that again and try to visualize)
METHOD TO GET AN INDEX OF A PERTICULAR ELEMENT:
def index_of(self, data):
itr = self.head
index = ''
count = 0
while itr:
# if the value of the node is equal to the data that is passed
# assign index as the value of the count at that time
if itr.value == data:
index = count
break
itr = itr.next
# keep increasing the count until we get the matching value
count += 1
return index
Let's test this method:
lst = LinkedList()
lst.insert_at_end(1)
lst.insert_at_end(2)
lst.insert_at_end(3)
lst.insert_at_end(4)
print("index of 3 -->", lst.index_of(3))
Output: (read the comments in code snippet for explanation)
index of 3 --> 2
METHOD TO REMOVE AN ELEMENT BY THE VALUE:
def remove_by_value(self, data):
itr = self.head
while itr:
# we will keep going through the list until
# we get value matching to the passed data
if itr.value == data:
# first calculate the index by self.index_of() method
index = self.index_of(data)
# call self.remove_at() method to remove that value (OOP stuff)
self.remove_at(index)
break
itr = itr.next
Let's test this method:
lst = LinkedList()
lst.insert_at_end(1)
lst.insert_at_end(2)
lst.insert_at_end(3)
lst.insert_at_end(4)
lst.print() # before removal
lst.remove_by_value(3)
lst.print() # after removal
Output: (read the comments in code snippet for explanation)
# output before removal
1 --> 2 --> 3 --> 4 -->
# output after removal
1 --> 2 --> 4 -->
METHOD TO GET A VALUE AT THE PARTICULAR INDEX:
def value_at(self, index):
itr = self.head
count = 0
value = '' # initialize the value var
while itr:
# keep traveling through linked list and once you find
# count == index, store value of that node in value variable
if count == index:
value = itr.value
count += 1
itr = itr.next
# return value variable
return value
Let's test this method:
lst = LinkedList()
lst.insert_at_end(10)
lst.insert_at_end(20)
lst.insert_at_end(30)
lst.insert_at_end(40)
lst.insert_at_end(50)
lst.print()
print("Value at index 2 --->", lst.value_at(2))
Output: (read the comments in code snippet for explanation)
# output of lst.print()
10 --> 20 --> 30 --> 40 --> 50 --> 60 --> 70 -->
# output of lst.value_at(2)
Value at index 2 ---> 30
ASSIGNMENT:
- Add error handling in above method i.e.
"Index our of range"and"List is empty"error messages.
METHOD TO REVERSE A LINKED LIST:
def reverse(self):
j = 0
lst = []
for i in range(self.length()):
# first we will append all the values in the 'lst' var
lst.append(self.value_at(i))
for i in range((self.length() - 1), -1, -1):
# replace an element at the last index of our LINKED LIST
# with an element at the 0th index of the 'lst' var and second last
# element of the LINKED LIST with an element at the 1st index of the 'lst' var and so on...
self.replace_at(i, lst[j])
j += 1
Let's reverse our linked list
lst = LinkedList()
lst.insert_at_end(1)
lst.insert_at_end(2)
lst.insert_at_end(3)
lst.insert_at_end(4)
lst.insert_at_end(5)
lst.insert_at_end(6)
lst.insert_at_end(7)
lst.print() # before reversal
lst.reverse()
lst.print() # after reversal
We will first append all the elements of our linked list in lst list so the lst list will be [1, 2, 3, 4, 5, 6, 7] then we will replace 1 of our linked list with 7 of the lst var, similarly 2 of our linked list with 6 of the lst var, and so on...
Output:
# output before reversal
1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 -->
# output after reversal
7 --> 6 --> 5 --> 4 --> 3 --> 2 --> 1 -->
I hope you have learned something new! If you found this article useful, be sure to share, follow and support!
Thank you for reading!
If you face any problems in any of the above methods, you can go ahead and check out the code on my Github.
Also, make sure to subscribe to our newsletter on blog.learncodeonline.in and never miss any upcoming articles related to programming just like this one.
I hope this post will help you in your journey. Keep learning!