Data Structures in Python: LinkedList

A linked list is an ordered collection of objects which are connected via links. Each element of the linked list is called a node. Each node consists of two elements-

  1. Data: It contains the value
  2. Next: It contains the address of the next node of the list

The node looks something like this:

Node Representation

So, a linked list is a collection of nodes.

Linked List Representation

In the above figure representing a linked list notice that the first element has a head arrow which means the first element of the node is called head and it is used for iterating through the linked list. Also notice that in the last element next is none as there is no next element after the last element and it is used for ending the iteration.

The linked list is not a built-in data structure in Python but we can create it through the concept of node

So far what I have taught you about the linked list is more precisely a singly linked list and in this lecture, I will be implementing a singly linked list. There is one more type called doubly linked list which we will study later.

Creating Linked list

We will create a node object and create another class to use this node object:

class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next = next

Here in the above code, we created a node object and in this node, we have data and next element address attributes.

Now let's create a LinkedList class to use this node object:

class LinkedList:
def __init__(self):
self.head = None

Now let's use the above codes to create our linked list

LL = LinkedList()
LL.head = Node("Sun") #here we created head with node data "Sun"
print(LL)#OUTPUT
Sun

Now let's create more nodes and connect them:

e2 = Node("Mon") #2nd node
e3 = Node("Tue") #3rd node
#let's connect head to e2 node
LL.head.next = e2
#e2 to e3
e2.next = e3
print(LL)#OUTPUT:
<__main__.LinkedList object at 0x000001ffe570dfd0>

Here above when we printed our linked list a linked list object is returned. Instead of this object if you want to show list values then we should traverse through our linked list and show every node value until the next value of the node is none.

Traversing

We will implement our traverse code in the __repr__ method.

class LinkedList:
def __init__(self):
self.head = None
def __repr__(self):
if self.head is None:
return "Empty Linked List"
itr = self.head
listr = ''
while itr:
if itr.next == None:
listr += str(itr.data)
break
listr += str(itr.data) + '->'
itr = itr.next
return listr

In the ‘ __repr__’ method first, check if the head node is present because if the head is None then just show “Empty Linked List”.

We iterated through the linked list using the while loop until the next element of the current node is none and break the loop.

print(LL)#OUTPUT
Sun->Mon->Tue

I hope this would be enough for today and we will continue this only lecture tomorrow where we will implement insertion and deletion.

Insertion

Insertion could be of many types like:

  1. Insert at beginning
  2. Insert at end
  3. Insert at some specific position as we do in the list using the index and value
  4. Insert after element
  5. Inserting list of values

Insert at the beginning:

Inserting at the beginning of the linked list is too simple, just create a new node you want to insert with next equal to the current head node and define that node as a head node.

class LinkedList:
def __init__(self):
self.head = None
def insert_at_beginning(self, data):#Insertion at beginning
node = Node(data, self.head)
self.head = node
def __repr__(self):
if self.head is None:
return "Empty Linked List"
itr = self.head
listr = ''
while itr:
if itr.next == None:
listr += str(itr.data)
break
listr += str(itr.data) + '->'
itr = itr.next
return listr
LL.insert_at_beginning("Fri")
print(LL)
#OUTPUT
Fri->Sun->Mon->Tue

Insert at the end:

First of all, we will check if there is an element in our list by checking the head if it's empty then we will create a node and assign the head to it otherwise we will iterate as done in traversing and insert at the end.

class LinkedList:    def __init__(self):
self.head = None
def insert_at_beginning(self, data):#Insertion at beginning
node = Node(data, self.head)
self.head = node
def insert_at_end(self, data): #Inserting at the end
if self.head is None:
self.head = Node(data, None)
return

itr = self.head
while itr.next:
itr = itr.next
itr.next = Node(data, None)
def __repr__(self):
if self.head is None:
return "Empty Linked List"
itr = self.head
listr = ''
while itr:
if itr.next == None:
listr += str(itr.data)
break
listr += str(itr.data) + '->'
itr = itr.next
return listr
LL.insert_at_end("Thu")
print(LL)
#OUTPUT
Fri->Sun->Mon->Tue->Thu

Inserting Data List

To insert a list of values we have to iterate through the list inserted and add elements to the end of the linked list using the insert_at_end method.

class LinkedList:    def __init__(self):
self.head = None
def insert_at_beginning(self, data):#Insertion at beginning
node = Node(data, self.head)
self.head = node
def insert_at_end(self, data): #Inserting at the end
if self.head is None:
self.head = Node(data, None)
return

itr = self.head
while itr.next:
itr = itr.next
itr.next = Node(data, None)
def insert_values(self, data_list): #Inserting data list
self.head = None
for data in data_list:
self.insert_at_end(data)
def __repr__(self):
if self.head is None:
return "Empty Linked List"
itr = self.head
listr = ''
while itr:
if itr.next == None:
listr += str(itr.data)
break
listr += str(itr.data) + '->'
itr = itr.next
return listr
LL = LinkedList()
LL.insert_values([1, 2, 3, 4, 5])
print(LL)
#OUTPUT
1->2->3->4->5

Get length of linked list

Before going further in insertion we will implement the get_len method to get the length of the list

class LinkedList:    def __init__(self):
self.head = None
def insert_at_beginning(self, data):#Insertion at beginning
node = Node(data, self.head)
self.head = node
def insert_at_end(self, data): #Inserting at the end
if self.head is None:
self.head = Node(data, None)
return

itr = self.head
while itr.next:
itr = itr.next
itr.next = Node(data, None)
def insert_values(self, data_list): #Inserting data list
self.head = None
for data in data_list:
self.insert_at_end(data)

def get_len(self): #get the length of the list
count = 0
itr = self.head
while itr:
count += 1
itr = itr.next
return count
def __repr__(self):
if self.head is None:
return "Empty Linked List"
itr = self.head
listr = ''
while itr:
if itr.next == None:
listr += str(itr.data)
break
listr += str(itr.data) + '->'
itr = itr.next
return listr
print(LL.get_len())#OUTPUT
5

Insert at Index

We will create the insert_at method where we will pass the index and data value we want to insert.

class LinkedList:    def __init__(self):
self.head = None
def insert_at_beginning(self, data):#Insertion at beginning
node = Node(data, self.head)
self.head = node
def insert_at_end(self, data): #Inserting at the end
if self.head is None:
self.head = Node(data, None)
return

itr = self.head
while itr.next:
itr = itr.next
itr.next = Node(data, None)
def insert_values(self, data_list): #Inserting data list
self.head = None
for data in data_list:
self.insert_at_end(data)
def get_len(self): #get the length of the list
count = 0
itr = self.head
while itr:
count += 1
itr = itr.next
return count
def insert_at(self, index, data): #to insert at particular index
if index<0 or index>=self.get_len():
raise Exception("Invalid index")
if index == 0:
self.insert_at_begining(data)
count = 0
itr = self.head
while itr:#iterate until element is found
if count == index -1:
node = Node(data, itr.next)
itr.next = node
break
itr = itr.next
count += 1
def __repr__(self):
if self.head is None:
return "Empty Linked List"
itr = self.head
listr = ''
while itr:
if itr.next == None:
listr += str(itr.data)
break
listr += str(itr.data) + '->'
itr = itr.next
return listr
LL.insert_at(2, 6)
print(LL)
#OUTPUT
1->2->6->3->4->5

Insert after value

To insert a node after a particular node let’s create the insert_after method:

class LinkedList:    def __init__(self):
self.head = None
def insert_at_beginning(self, data):#Insertion at beginning
node = Node(data, self.head)
self.head = node
def insert_at_end(self, data): #Inserting at the end
if self.head is None:
self.head = Node(data, None)
return

itr = self.head
while itr.next:
itr = itr.next
itr.next = Node(data, None)
def insert_values(self, data_list): #Inserting data list
self.head = None
for data in data_list:
self.insert_at_end(data)
def get_len(self): #get the length of the list
count = 0
itr = self.head
while itr:
count += 1
itr = itr.next
return count
def insert_at(self, index, data): #to insert at particular index
if index<0 or index>=self.get_len():
raise Exception("Invalid index")
if index == 0:
self.insert_at_begining(data)
count = 0
itr = self.head
while itr:#iterate until element is found
if count == index -1:
node = Node(data, itr.next)
itr.next = node
break
itr = itr.next
count += 1

#Insert after a value
def insert_after_value(self, data_after, data_to_insert):
itr = self.head
while itr:
if itr.data == data_after:
node = Node(data_to_insert, itr.next)
itr.next = node
return
itr = itr.next
return None
def __repr__(self):
if self.head is None:
return "Empty Linked List"
itr = self.head
listr = ''
while itr:
if itr.next == None:
listr += str(itr.data)
break
listr += str(itr.data) + '->'
itr = itr.next
return listr
LL.insert_after_value(1, 8)
print(LL)
#OUTPUT
1->8->2->6->3->4->5

Removing Nodes

We may want to remove nodes using index or value

Remove using Index

We will iterate through the list and remove value when reached the index value

class LinkedList:    def __init__(self):
self.head = None
def insert_at_beginning(self, data):#Insertion at beginning
node = Node(data, self.head)
self.head = node
def insert_at_end(self, data): #Inserting at the end
if self.head is None:
self.head = Node(data, None)
return

itr = self.head
while itr.next:
itr = itr.next
itr.next = Node(data, None)
def insert_values(self, data_list): #Inserting data list
self.head = None
for data in data_list:
self.insert_at_end(data)
def get_len(self): #get the length of the list
count = 0
itr = self.head
while itr:
count += 1
itr = itr.next
return count
def insert_at(self, index, data): #to insert at particular index
if index<0 or index>=self.get_len():
raise Exception("Invalid index")
if index == 0:
self.insert_at_begining(data)
count = 0
itr = self.head
while itr:#iterate until element is found
if count == index -1:
node = Node(data, itr.next)
itr.next = node
break
itr = itr.next
count += 1

#Insert after a value
def insert_after_value(self, data_after, data_to_insert):
itr = self.head
while itr:
if itr.data == data_after:
node = Node(data_to_insert, itr.next)
itr.next = node
return
itr = itr.next
return None
def remove_at(self, index): if index<0 or index>=self.get_len():
raise Exception("Invalid index")
if index == 0:
self.head = self.head.next
return

count = 0
itr = self.head
while itr:
if count == index - 1:
itr.next = itr.next.next
break
itr = itr.next
count += 1
def __repr__(self):
if self.head is None:
return "Empty Linked List"
itr = self.head
listr = ''
while itr:
if itr.next == None:
listr += str(itr.data)
break
listr += str(itr.data) + '->'
itr = itr.next
return listr
LL.remove_at(1)
print(LL)
#OUTPUT
1->2->6->3->4->5

Remove by Value

class LinkedList:    def __init__(self):
self.head = None
def insert_at_beginning(self, data):#Insertion at beginning
node = Node(data, self.head)
self.head = node
def insert_at_end(self, data): #Inserting at the end
if self.head is None:
self.head = Node(data, None)
return

itr = self.head
while itr.next:
itr = itr.next
itr.next = Node(data, None)
def insert_values(self, data_list): #Inserting data list
self.head = None
for data in data_list:
self.insert_at_end(data)
def get_len(self): #get the length of the list
count = 0
itr = self.head
while itr:
count += 1
itr = itr.next
return count
def insert_at(self, index, data): #to insert at particular index
if index<0 or index>=self.get_len():
raise Exception("Invalid index")
if index == 0:
self.insert_at_begining(data)
count = 0
itr = self.head
while itr:#iterate until element is found
if count == index -1:
node = Node(data, itr.next)
itr.next = node
break
itr = itr.next
count += 1

#Insert after a value
def insert_after_value(self, data_after, data_to_insert):
itr = self.head
while itr:
if itr.data == data_after:
node = Node(data_to_insert, itr.next)
itr.next = node
return
itr = itr.next
return None
def remove_at(self, index): if index<0 or index>=self.get_len():
raise Exception("Invalid index")
if index == 0:
self.head = self.head.next
return

count = 0
itr = self.head
while itr:
if count == index - 1:
itr.next = itr.next.next
break
itr = itr.next
count += 1
def remove_by_value(self, data):
if self.head == None:
return
if self.head.data == data:
self.head = self.head.next
return
itr = self.head
while itr:
if itr.next.data == data:
itr.next = itr.next.next
return
itr = itr.next
return None
def __repr__(self):
if self.head is None:
return "Empty Linked List"
itr = self.head
listr = ''
while itr:
if itr.next == None:
listr += str(itr.data)
break
listr += str(itr.data) + '->'
itr = itr.next
return listr
LL.remove_by_value(4)
print(LL)
#OUTPUT
1->2->6->3->5

That will be enough for this tutorial. If you are confused why I haven’t taught Big O notation in the linked list don’t worry it will be covered in coming tutorials. Also, I don’t want to confuse you by including everything at once. So, don’t worry and have a good day!

Lectures

Lecture 1: https://medium.com/@saifmdco/data-structures-with-python-introduction-4dadeffa2215

Lecture 2: https://medium.com/@saifmdco/data-structures-with-python-arrays-c498518bf7fd

Lecture 3: https://medium.com/@saifmdco/data-structures-in-python-lists-653a3ad103ab

Lecture 4: https://medium.com/@saifmdco/data-structures-in-python-tuples-3c350640cd9a

Lecture 5: https://medium.com/@saifmdco/data-structures-in-python-dictionary-fad27ffdda8b

Lecture 6: https://medium.com/@saifmdco/data-structures-in-python-2d-array-6bc0154aa717

Lecture 7: https://medium.com/@saifmdco/data-structures-in-python-matrix-22adba5aa597

Lecture 8: https://medium.com/@saifmdco/data-structures-in-python-sets-92d5445e97e8

Lecture 9: https://medium.com/@saifmdco/data-structures-in-python-chainmap-fca2a9d47249

Lecture 10: https://medium.com/@saifmdco/data-structures-in-python-linkedlist-50f2118c659e

Lecture 11: https://medium.com/@saifmdco/data-structures-in-python-stack-6bf182d63581

Lecture 12: https://medium.com/@saifmdco/data-structures-in-python-queue-6361d3dcff0

Lecture 13: https://medium.com/@saifmdco/data-structures-in-python-dequeue-1a585e269a55

Lecture 14: https://medium.com/@saifmdco/data-structures-in-python-custom-stack-b7b9173b4eae

Lecture 15: https://medium.com/@saifmdco/data-structures-in-python-hash-table-39be784eefc1

Lecture 16: https://medium.com/@saifmdco/data-structures-in-python-doubly-linked-list-fe698d74756c

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store