@Python(Data Structure Part-2)

 

Hello, programmers in today's lesson we are going to learn about some advanced data structure. As we have already discussed data structure and variables in our previous lesson I would assume that you know the basics😄. So, in today's lesson, we are going to discuss all the linear data structures and their operations. The linear data structure is a type of data structure in which that data is stored sequentially.

Different types of the linear data structure are:

1.Linked list

2. Stack

3.Queue

What is a linked list?

A linked list is a type of data structure where it consists of n number of elements and each element has a data part and a pointer. The pointer points to the next element whereas the data part stores the data. A  pointer is nothing but a reference to the next element in python but this is not true for other programming languages such as C/C++ where a pointer is a variable that stores the address of other variables. We could visualize a linked list something like this:

Here, the linked list consists of 4 elements and each element has data and a next. The data part stores the data and the next is the pointer to the next element. Also, we have another pointer "Head" that points to the first element of the linked list. Now, let us write some code to create our own linked list in python.

#Node class
class Node:
  #Node class function
  def __init__(self,data):
    self.data = data #Assign data
    self.next = None #Assign pointer and initialize it as null
#class Linkedlist
class LinkedList:
  #Function to initialize Linked list 
  def __init__(self):
    self.head = None #pointer head pointing to the first node of linked list 

Here, In the Python code above we created a class Node which has a function containing data and a pointer. We initialized the pointer to be null as this is our first node and currently, it is not pointing to the next node. Also, we created another class LinkedList having a function that initializes the head pointer that points to the first node of the linked list. Now let us create some nodes and join them to actually make a linked list.

#Node class
class Node:
  #Node class function
  def __init__(self,data):
    self.data = data #Assign data
    self.next = None #Assign pointer and initialize it as null
#class Linkedlist
class LinkedList:
  #Function to initialize Linked list 
  def __init__(self):
    self.head = None #pointer head pointing to the first node of linked list
if __name__ == '__main__':
  first = LinkedList()
  first.head = Node(1)
  second = Node(2)
  third = Node(3)

We have created three nodes and those are first, second, and third. Here the first node contains the head pointer. Now let us join these three nodes.

#Node class
class Node:
  #Node class function
  def __init__(self,data):
    self.data = data #Assign data
    self.next = None #Assign pointer and initialize it as null
#class Linkedlist
class LinkedList:
  #Function to initialize Linked list 
  def __init__(self):
    self.head = None #pointer head pointing to the first node of linked list
if __name__ == '__main__':
  first = LinkedList()
  first.head = Node(1)
  second = Node(2)
  third = Node(3)
  first.head.next = second
  second.next = third 

Here we have joined the nodes using the next pointer and successfully created a simple linked list. Our linked list could be visualized as:

Linked List Traversal

We have created our linked list now let us traverse the linked list and print all data stored in each node. For traversal, we are going to write a print_list() function something like this:

#Node class
class Node:
  #Node class function
  def __init__(self,data):
    self.data = data #Assign data
    self.next = None #Assign pointer and initialize it as null
#class Linkedlist
class LinkedList:
  #Function to initialize Linked list 
  def __init__(self):
    self.head = None #pointer head pointing to the first node of linked list
  def print_list(self):#Function for traversal
    temp = self.head # Intializing a temp variable with the head pointing to the first node
    while(temp):
      print(temp.data) #Printing all the data in each node
      temp = temp.next #pointing to the next node after printing the first node 
if __name__ == '__main__':
  first = LinkedList() # Created a linked list with the first node
  first.head = Node(1) #Inserting value to the node
  second = Node(2)
  third = Node(3)
  first.head.next = second # pointing to the second node
  second.next = third #pointing to the third node
  first.print_list() # Calling the print_list() function

And our output should look like:

                                  

 Here In the python code above we have written a print_list() function. And the print list function has a variable temp that points to the first node of the list and it traverses through each node and prints the value stored inside the node. It is important to note that we have to call our print_list() function in our main function to execute it.    

Insertion of a node in a linked list:

We have already discussed how a linked list is created and traversed. Now let us see how can we add a node inside a linked list at different positions. Here we will discuss:

1. Adding a node at front of the linked list:

Here we are going to add a new node at the front of the linked list and move the head pointer to our new node as this node would now be our first node in the linked list. The python code for the following is shown below:

#Node class
class Node:
  #Node class function
  def __init__(self,data):
    self.data = data #Assign data
    self.next = None #Assign pointer and initialize it as null
#class Linkedlist
class LinkedList:
  #Function to initialize Linked list 
  def __init__(self):
    self.head = None #pointer head pointing to the first node of linked list
  def print_list(self):#Function for traversal
    temp = self.head # Intializing a temp variable with the head pointing to the first node
    while(temp):
      print(temp.data) #Printing all the data in each node
      temp = temp.next #pointing to the next node after printing the first node
  def push(self, new_data):# Function to add new node at the beginning 
    new_node = Node(new_data)  # New node created
    new_node.next = self.head # Moving the head pointer to the next node after our new node
    self.head = new_node # Placing the head pointer to our new node.    
if __name__ == '__main__':
  first = LinkedList() # Created a linked list with the first node
  first.head = Node(1) #Inserting value to the node
  second = Node(2)
  third = Node(3)
  first.head.next = second # pointing to the second node
  second.next = third #pointing to the third node
  first.push(0) #Calling the push function
  first.print_list() # Calling print_list() 

Here we created a new function push in the class LinkedList. And our function:

1. first creates a new node with data as an argument. 

2. Secondly, it moves the head pointer to the next node after our new node. This step is done to join the linked list with our new node.

3. It moves the head pointer to our new node.

Finally, we can see the output as:

      

2. Adding a node after a given node:

We have already discussed how to add a node at the beginning of the linked list. Now let us see how to add a node after any given node. 

#Node class
class Node:
  #Node class function
  def __init__(self,data):
    self.data = data #Assign data
    self.next = None #Assign pointer and initialize it as null
#class Linkedlist
class LinkedList:
  #Function to initialize Linked list 
  def __init__(self):
    self.head = None #pointer head pointing to the first node of linked list
  def print_list(self):#Function for traversal
    temp = self.head # Intializing a temp variable with the head pointing to the first node
    while(temp):
      print(temp.data) #Printing all the data in each node
      temp = temp.next #pointing to the next node after printing the first node
  def insert_after(self,prev_node,new_data):
    if prev_node is None: #check if prev_node is linked to the next node
      print("Prev_node must be linked")
    new_node = Node(new_data)#Create a new node with new_data as args
    new_node.next = prev_node.next#Move the prev_node pointer to the new_node  
    prev_node.next = new_node#make the prev_node point to the new_node     
if __name__ == '__main__':
  first = LinkedList() # Created a linked list with the first node
  first.head = Node(1) #Inserting value to the node
  second = Node(2)
  third = Node(3)
  first.head.next = second # pointing to the second node
  second.next = third #pointing to the third node
  first.insert_after(second,4) #Calling insert_after function
  first.print_list() # Calling print_list() 

In the python code above we have created a new function insert_after that inserts a new node after any given node. Here:

 1. We check if the previous node is linked or not.

2. Then we assign the pointer of the previous node to the new node.

3. At last, we make the previous node point to the new node.

This whole process can be visualized as:

Source: GeeksforGeeks

And our output for the above program would be:

                        

3. Adding a node at the end of the linked list:

Now let us discuss on how to add a node at the end of the linked list. Something like this:

Source: GeeksforGeeks

The python code for the method is shown below:

#Node class
class Node:
  #Node class function
  def __init__(self,data):
    self.data = data #Assign data
    self.next = None #Assign pointer and initialize it as null
#class Linkedlist
class LinkedList:
  #Function to initialize Linked list 
  def __init__(self):
    self.head = None #pointer head pointing to the first node of linked list
  def print_list(self):#Function for traversal
    temp = self.head # Intializing a temp variable with the head pointing to the first node
    while(temp):
      print(temp.data) #Printing all the data in each node
      temp = temp.next #pointing to the next node after printing the first node
  def add_last(self,new_data):
    new_node = Node(new_data) #create a new node
    if self.head is None:#If the list is empty 
      self.head = new_node#Then make head point to new_node
      return
    last = self.head# Else traverse to the last node
    while(last.next):
      last = last.next
    last.next = new_node# Make the last node point to the new node         
if __name__ == '__main__':
  first = LinkedList() # Created a linked list with the first node
  first.head = Node(1) #Inserting value to the node
  second = Node(2)
  third = Node(3)
  first.head.next = second # pointing to the second node
  second.next = third #pointing to the third node
  first.add_last(4) #Calling insert_after function
  first.print_list() # Calling print_list()

Here we have created  a function add_last that does the following:

1.Creates a new node

2.If the list is empty then make the head point to the new node

3.Else it traverses to the last node and makes the last node point to the new node.

The output for the following program is shown below:

                                                   

              

 We have learned all about how to add a node at different positions of the linked list now let us discuss how to remove a node from a different positions in the linked list. So, a node can be removed from the linked list by the following ways:

1. Deleting a node by using a key value:

We can delete a node in a linked list using a key value as input. That means you already know the value in your linked list and you want to delete a particular value from the linked list. The python program to delete a node using a key is shown below:

# Node class 
class Node: 

	# Constructor to initialize the node object 
	def __init__(self, data): 
	    self.data = data 
	    self.next = None

class LinkedList: 

	# Function to initialize head 
	def __init__(self): 
	    self.head = None

	# Function to insert a new node at the beginning 
	def push(self, new_data): 
	    new_node = Node(new_data) 
	    new_node.next = self.head 
	    self.head = new_node 

#Function to delete a node by using the key value
	def deleteNode(self, key):

 
		
		# Store head node into a temp variable

            temp = self.head 

		# If head node itself holds the key to be deleted 
	    if (temp is not None): 

	        if (temp.data == key): 
	            self.head = temp.next
		    temp = None
		    return

		# Search for the key to be deleted, keep track of the 
		# previous node as we need to change 'prev.next' 
		while(temp is not None): 
		    if temp.data == key: 
		        break
		    prev = temp 
		    temp = temp.next

		# if key was not present in linked list 
		if(temp == None): 
		    return

		# Unlink the node from linked list 
		prev.next = temp.next

		temp = None


	#Function to print the linked LinkedList 
	def printList(self): 
	    temp = self.head 
	    while(temp): 
	        print(" %s" %(temp.data)) 
		temp = temp.next


if __name__ == '__main__':

  llist = LinkedList() 
  llist.push('a') 
  llist.push('b') 
  llist.push('c') 
  llist.push('d') 
  print ("Created Linked List: ") 
  llist.printList() 
  llist.deleteNode('b')#calling function deleteNode with b as key 
  print ("\nLinked List after Deletion of b:") 
  llist.printList() 

In the python code above we have created a function delete node that takes a key value as an argument and does the following:

1. Stores the head pointer to a temp variable

2. If the key value is stored in the first node itself then it temp.next stores the self.head and the temp value is removed eventually. 

3. If the key value is stored at any other location then, we keep the track of the previous node. Store the temp variable into another variable prev and assign the temp.next value to temp. This is necessary because due need to change the prev.next

4. Then we unlink the node to be deleted by the link list and release the memory allocated to temp.

The output for the following program would be:

2. Deleting a node using the position in the linked list:

We have learned about how to delete a node using the key value. Now let us discuss how to remove a node using its position in the linked list. The python program for the following is shown below:

# Python program to delete a node in a linked list 
# at a given position 

# Node class 
class Node: 

	# Constructor to initialize the node object 
    def __init__(self, data): 

    self.data = data 
    self.next = None

class LinkedList: 

	# Constructor to initialize head 
        def __init__(self): 
	   self.head = None

	# Function to insert a new node at the beginning 
	def push(self, new_data): 
	    new_node = Node(new_data) 
	    new_node.next = self.head 
	    self.head = new_node 

	# Given a reference to the head of a list 
	# and a position, delete the node at a given position 
	def deleteNode(self, position): 

		# If linked list is empty 
		if self.head == None: 
		    return

		# Store head node in a temp variable
		temp = self.head 

		# If head needs to be removed 
		if position == 0: 
		    self.head = temp.next
		    temp = None
		    return

		# Find previous node of the node to be deleted 
		for i in range(position -1 ): 
			temp = temp.next #temp variable stores the temp.next value
			if temp is None: 
				break

		# If position is more than number of nodes 
		if temp is None: 
			return
		if temp.next is None: 
			return

		# Node temp.next is the node to be deleted 
		# store pointer to the next of node to be deleted 
		next = temp.next.next

		# Unlink the node from linked list 
		temp.next = None

		temp.next = next


	# Function to print the linked LinkedList 
	def printList(self): 
		temp = self.head 
		while(temp): 
		    print(" %d " %(temp.data)), 
		    temp = temp.next


if __name__ =='__main__':

  llist = LinkedList() 
  llist.push(1) 
  llist.push(2) 
  llist.push(3) 
  llist.push(4) 
  llist.push(5) 
  print("Created Linked List: ")
  llist.printList() 
  llist.deleteNode(4) 
  print("\nLinked List after Deletion at position 4: ")
  llist.printList() 

And the output for the following program would be:

Now let us discuss the deleteNode function above:

1. The deleteNode function takes one argument and that is the position of the node to be deleted. 

2. It checks if the linked list is empty. If it is empty it exits the function as we cannot delete an empty node.

3. It stores the head pointer into a temp variable. And if the first node has to be deleted then we move the head pointer to the next node of the first node and remove the first node.

4. Else, if the position to be deleted is other then first node then we find out the previous node of the node that is to be deleted and store it in a temp variable.

5. Since we know the previous node then it is obivious that the node to be deleted would be the temp.next node. And hence we need to link the next node of temp.next to its previous node. At last, we remove the temp.next node and free the memory on temp variable.

Well, that was all about inserting and deleting a node in a linked list. Now, let us discuss about differtent types of linked list:

Doubly Linked List:

Circular Linked List: