Python Interview Questions on Linked List

/ Python / By

We have compiled most frequently asked Python Interview Questions which will help you with different expertise levels.

Python Interview Questions on Linked List

A linked list is a linear structure that consists of elements such that each element is an individual object and contains information regarding:

  1. Data
  2. Reference to next element

In the linked list, each element is called a node.

Python Interview Questions on Linked List chapter 11 img 3

You can see in the diagram, the reference to the first node is called Head. It is the entry point of the linked list. If the list is empty then the head points to null. The last node of the linked list refers to null.

As the number of nodes can be increased or decreased as per requirement, linked lists are considered to be dynamic data structures. However, in a linked list direct access to data is not possible. Search for any item that starts from- the head and you will have to go through each reference to get that item. A linked list occupies more memory.

The linked list described above is called a singly linked list. There is one more type of linked list known as a doubly-linked list. A double-linked list has a reference to the next node and the previous node.

Python Interview Questions on Linked List chapter 11 img 4

Question 1.
Write a code to implement a Node class such that a Node contains data as well as a reference to the next node.
Answer:
To create a node object we pass data value to the constructor. The constructor assigns the data value to data and sets the node’s reference to None. Once we create all the objects we assign the memory address of the second object as the reference to the first node object, the memory address of the third object is assigned as a reference to the second object, and so on. The last object, thus have no(or none as) reference.

The code for the Node class will be as follows:

Code

class Node:
        def__init__(self,data = None):
            self . data = data
            self . reference = None
objNode1 = Node(1)
objNode2 = Node(2)
objNode3 = Node(3)
objNode4 = Node(4)
objNode1 . reference = objNode2
objNode2 . reference = objNode3
objNode3 . reference = objNode4
objNode4 . reference = None

Execution

print("DATA VALUE = ",objNodel.data,"REFERENCE = ",objNodel.reference)
print("DATA VALUE = ",objNode2.data,"REFERENCE = ",objNode2.reference)
print("DATA VALUE = ",objNode3.data,"REFERENCE = ",objNode3.reference)
print("DATA VALUE = ",objNode4.data,"REFERENCE = ”,objNode4.reference)

Output

DATA VALUE = 1 REFERENCE = <_main_. Node object
at 0x000000595E0CC6A0>
DATA VALUE = 2 REFERENCE =<_main_ .Node object
at 0x000000595E329978>
DATA VALUE = 3 REFERENCE = <_main_ .Node object
at 0x000000595E3299B0>
DATA VALUE = 4 REFERENCE = None
>>>

Question 2.
Write code to traverse through a linked list.
Answer:
Method I
We have already written the code for the Node class:

class Node:
      def _init_ (self,data = None):
          self.data = data
          self.reference = None

objNode1 = Node(1)
objNode2 = Node(2)
objNode3 = Node(3)
objNode4 = Node(4)

We will now see how to traverse through the linked list:

Step 1
We create a variable presentNode and assign the first object to it.

presentNode = objNode1

On doing this presentNode gets the data and reference values of objectNode1.
Step 2
The reference value points to objNode2.
So, we can write a while loop:

while presentNode:
print("DATA VALUE = ",presentNode.data)
presentNode = presentNode.reference

Once the presentNode is assigned, the reference value contained in objNode4 it will come out of the while loop because the value of reference is None.

Code

class Node:
       def_init_(self,data = None):
           self.data = data
           self.reference = None

Execution

objNode1 = Node(1)
objNode2 = Node(2)
objNode3 = Node(3)
objNode4 = Node(4)
objNodel.reference = objNode2
objNode2.reference = objNode3
objNode3.reference = objNode4
objNode4.reference = None
presentNode = objNode1
while presentNode:
    print("DATA VALUE = ",presentNode.data)
    presentNode = presentNode.reference

Output

DATA VALUE = 1
DATA VALUE = 2
DATA VALUE = 3
DATA VALUE = 4

Method II
Another method to do this by creating two classes: Node and Linked list
Code

class Node:
      def_init_(self,data = None):
          self.data = data
          self.reference = None
class Linked_list:
     def_init_(self):
        self.head = None 
     def traverse(self) :
           presentNode = self.head
           while presentNode:
                  print("DATA VALUE = ",presentNode.data)
                  presentNode = presentNode.reference

Execution

objNode1 = Node(1)
objNode2 = Node(2)
objNode3 = Node(3)
objNode4 = Node(4)
linkObj = Linked_list( )
#head of the linked list to first object
linkObj.head = objNodel
# reference of the first node object to second object

linkObj.head.reference = objNode2
objNode2.reference = objNode3
objNode3.reference = objNode4
linkObj.traverse ( )

Output

DATA VALUE = 1
DATA VALUE = 2
DATA VALUE = 3
DATA VALUE = 4

Question 3.
Write a code to add a node at the beginning of a linked list.
Answer:
To solve this question, we will just add a new method to insert the node in the same code that is mentioned in the last example:
In the last example, we pointed the head of the linked list object to the first node object.

linkObj.head = objNode1

When we add the node at the beginning we just have to make the linkObj.
head = new_node and new node.reference = obj_Node1.

For this, we write a code where the value of the linkObj.head is first passed on to the new node. reference and then linkObj.head is set to the new node object.

def insert_at_Beginning(self, data) :
new_data = Node(data)
new_data.reference = self.head
self.head = new_data

So, the full code would be like the following:

Code

class Node:
     def_init_(self,data = None):
          self.data = data
          self.reference = None
class Linked_list:
   def_init_(self) :
         self.head = None
  def traverse(self):
       presentNode = self.head
       while presentNode:
            print("DATA VALUE = ",presentNode.data)
            presentNode = presentNode.reference
 def insert_at_Beginning(self, data) :
       new_data = Node(data)
       new_data.reference = self.head
       self.head = new data

Execution

objNode1 = Node(l1)
objNode2 = Node(2)
objNode3 = Node(3)
objNode4 = Node(4)
linkObj = Linked_list( )
#head of the linked list to first object
linkObj.head = objNode1
# reference of the first node object to second object
linkObj.head.reference = objNode2
objNode2.reference = objNode3
objNode3.reference = objNode4
linkObj.insert_at_Beginning(5)
linkObj.traverse ( )

Output

DATA VALUE = 5
DATA VALUE = 1
DATA VALUE = 2
DATA VALUE = 3
DATA VALUE = 4

Question 4.
Write a code to add a node at the end of a linked list.
Answer.
In order to add a node at the end of the linked list, it is important that you point the reference of the last node to the new node that you create.
Step 1:

Define the function

def insert_at_end(self,data):

Step 2:

Create a new Node object

new_data = Node(data)

Step 3:

Traverse through the linked list to reach the last node
Remember that you cannot directly access the last node in the linked list. You will have to traverse through all the nodes and reach the last node in order to take the next step.

presentNode = self.head
             while presentNode.reference != None:
                   presentNode = presentNode.reference

Step 4:

Add the new node at the end

After traversing through the linked list, you know that you have reached the last node whenpresentNode.reference = None. Since this won’t remain the last node anymore, you need to:

presentNode.reference = new_data

With this, we have added a new node at the end of a linked list.

Code

class Node:
    def_init_(self,data = None):
          self.data = data
          self.reference = None
class Linked_list:
   def_init_(self):
         self.head = None
   def traverse(self):
       presentNode = self.head
       while presentNode:
             print("DATA VALUE = ",presentNode.data)
             presentNode = presentNode.reference
  def insert_at_end(self,data):
      new_data = Node(data)
      presentNode = self.head
      while presentNode.reference != None:
          presentNode = presentNode.reference
      presentNode.reference = new_data

Execution

objNode1 = Node(1)
objNode2 = Node(2)
objNode3 = Node(3)
objNode4 = Node(4)
linkObj = Linked_list( )
#head of the linked list to first object
linkObj.head = objNode1
# reference of the first node object to second object
linkObj.head.reference = objNode2
objNode2.reference = objNode3
objNode3.reference = objNode4
linkObj.insert_at_end(5)
linkObj.insert_at_end(6)
linkObj.insert_at_end(7)
linkObj.traverse( )

Output

DATA VALUE = 1
DATA VALUE = 2
DATA VALUE = 3
DATA VALUE = 4
DATA VALUE = 5
DATA VALUE = 6
DATA VALUE = 7

Question 5.
Write a code to insert a node between two nodes in a linked list.
Answer:
The solution for this problem is very similar to adding a node to the beginning. The only difference is that when we add a node at the beginning we point the head value to the new node whereas in this case, the function will take two parameters. First will be the node object after which the new object will be inserted and the second would be the data for the new object. Once the new node is created, we pass on the reference value stored in the existing node object to it and the existing node is then made to point at the new node object

Step 1:

Define the function

This function will take two parameters:

  1. The node object after which the data is to be inserted.
  2. Data for the new node object.
def insert_in_middle(self,insert_data,new_data):

Step 2:
Assign references

new_node = Node(new_data)
new_node.reference = insert_data.reference insert_data.reference = new_node

Code

class Node:
      def_init_(self,data = None):
               self.data = data
               self.reference = None
class Linked_list:
def_init_(self):
self.head = None
def traverse(self):
presentNode = self.head
while presentNode:
                    print("DATA VALUE = ",presentNode.data)
                    presentNode = presentNode.reference


def insert_in_middle(self,insert_data,new_data):
                 new_node = Node(new_data)
                new_node.reference = insert_data.reference insert_data.reference = new_node

Execution

objNode1 = Node(1)
objNode2 = Node(2)
objNode3 = Node(3)
objNode4 = Node(4)
linkObj = Linked_list()
#head of the linked list to first object
linkObj.head = objNodel
# reference of the first node object to second object
linkObj.head.reference = objNcde2

objNode2.reference = objNode3
objNode3.reference = objNode4
linkObj.insert_in_middle(objNode3,8)
linkObj.traverse ( )

Output

DATA VALUE = 1
DATA VALUE = 2
DATA VALUE = 3
DATA VALUE = 8
DATA VALUE = 4
>>>

Question 6.
Write code to remove a node from a linked list.
Answer:
Suppose we have a linked list as shown below:
A -> B -> C
A. reference = B
B. reference = C
C. reference = A.
To remove B, we traverse through the linked list. When we reach node A that has a reference pointing to B, we replace that value with the reference value stored in B(that points to C). So that will make A point to C and B is removed from the chain.
The function code will be as follows:

def remove(self,removeObj):
 presentNode = self.head
  while presentNode:
    if(presentNode.reference == removeObj):
       presentNode.reference = removeObj.reference
           presentNode = presentNode.reference

The function takes the Node object as a parameter and traverses through the linked list, till it reaches the object that needs to be removed. Once we reach the node that has reference to the node that has to be removed, we simply change the reference value to reference value stored in object removeobj. Thus, the node now points directly to the node after the removeObj.

Code

class Node:
  def_init_(self,data = None):
           self.data = data
           self.reference = None
class Linked_list:
  def_init_(self) :
         self.head = None
  def traverse(self):
          presentNode = self.head
          while presentNode:
             print("DATA VALUE = ",presentNode.data)
             presentNode = presentNode.reference


def remove(self,removeObj):
      presentNode = self.head
       while presentNode:
             if(presentNode.reference == removeObj):
             presentNode.reference = removeObj.
reference
             presentNode = presentNode.reference

Execution

objNode1 = Node(1)
objNode2 = Node(2)
objNode3 = Node(3)
objNode4 = Node(4)
linkObj = Linked_list( )
#head of the linked list to first object
linkObj.head = objNode1
# reference of the first node object to second object
linkObj.head.reference = objNode2
objNode2.reference = objNode3
objNode3.reference = objNode4
linkObj.remove(objNode2)
linkObj.traverse( )

Question 7.
Print the values of the node in the center of the linked list.
Answer:
This involves counting the number of nodes in the object. If the length is even then the data of two nodes in the middle should be printed else only the data of the node in the center should be printed.

Step 1:

Define the function

def find_middle (self, 1list) :

Step 2:

Find the length of the counter

Here, we set a variable counter = 0. As we traverse through the linked list we increment the counter. At the end of the while loop we get the count of the number of nodes in the linked list. This is also the length of the linked list.

counter = 0
          presentNode = self.head
          while presentNode:
                 presentNode = presentNode.reference
                  counter = counter + 1 .
          print("size of linked list = ", counter)

Step 3:

Reach the middle of the linked list

The reference to the node in the middle is stored in the node before that. So, in the for loop instead of iterating (counter/2) times, we iterate (counter-1)/2 times. This brings us to the node which is placed just before the centre value.

presentNode = self.head
for i in range((counter-1)112) :
presentNode = presentNode.reference

Step 4:

Display the result depending on whether the number of nodes in the linked list

If the linked list has an even number of nodes then print the value of reference stored in the present node and the next node.

if (counter%2 == 0):
                nextNode = presentNode.reference
                print ("Since the length of linked list is an even number the two midle elements are:")
                print(presentNode.data,nextNode.data)

Else, print the value of the present node.

else: 
                print("Since the length of the linked list is an odd number, the middle element is: ")
             print(presentNode.data)

Code

class Node:
     def_init_(self,data = None):
           self.data = data
           self.reference = None
class Linked_list:
    def_init_(self):
          self.head = None
def find_middle (self, Hist) :
     counter = 0
     presentNode = self.head
    while presentNode:
         presentNode = presentNode.reference
         counter = counter + 1
    print ("size of linked list = ", counter)
    presentNode = self.head
    for i in range((counter-1)112) :
        presentNode = presentNode.reference
   if (counter%2 == 0) : 
          nextNode = presentNode.reference
          print("Since the length of linked list is an even number the two midle elements are:")
         print(presentNode.data,nextNode.data)


     else:
            print("Since the length of the linked list is an odd number, the middle element is: ")
           print(presentNode.data)

Execution (Odd Number of Nodes)

objNode1 = Node(1)
objNode2 = Node(2)
objNode3 = Node(3)
objNode4 = Node(4)
objNode5 = Node(5)
linkObj = Linked_list( )
#head of the linked list to first object
linkObj.head = objNode1
# reference of the first node object to second object
linkObj.head.reference = objNode2
objNode2.reference = objNode3
objNode3.reference = objNode4
objNode4.reference = objNode5
linkObj .find_middle (linkObj )

Output

size of linked list = 5
Since the length of the linked list is an odd 
number, the middle element is:
3

Execution (Even Numbers)

objNode1 = Node(1)
objNode2 = Node(2)
objNode3 = Node(3)
objNode4 = Node(4) 
linkObj = Linked_list( )
#head of the linked list to first object
linkObj.head = objNodel
# reference of the first node object to second object
linkObj.head.reference = objNode2
objNode2.reference = objNode3
objNode3.reference = objNode4
linkObj .find_middle (linkObj )

Output

size of linked list = 4
Since the length of the linked list is an even number the two middle elements are:
2  3

Question 8.
Implement a doubly linked list.
Answer:
A doubly linked list has three parts:

  1. Pointer to the previous node
  2. Data
  3. Pointer to the next node

Implementation of a doubly linked list is easy. We just need to take care of one thing that each node is connected to the next and the previous data.

Step 1:

Create a Node Class

The node class will have a constructor that initializes three parameters: data, reference to next node – refNext and reference to previous node – refPrev.

class Node:
          def_init_(self,data = None):
              self.data = data
              self.refNext = None
              self.refPrev = None

Step 2:

Create functions to traverse through the double linked list

I. Traverse Forward

To: traverse forward with the help of refNext that points to next value of the linked list. We start with the head and move on to the next node using
refNext.

def traverse(self):
presentNode = self.head
while presentNode:
print("DATA VALUE = ",presentNode.data)
presentNode = presentNode.refNext

II. Traverse Reverse

The traverse reverse is the opposite of the traverse forward. We are able to traverse backward with the help of the value of refPrev because it points to the previous node. We start from the tail and move on to the previous node using
refPrev.

def traverseReverse(self):
presentNode = self.tail
while presentNode:
        print("DATA VALUE = ",presentNode.data)
         presentNode = presentNode.refPrev

Step 3:

Write a function to add a node at the end

Appending a node at the end of the doubly linked list is the same as appending in the linked list the only difference is that we have to ensure that the node that is appended has its refPrev pointing to the node after which it has been added.

def append(self,data):
new_data = Node(data)
presentNode = self.head
while presentNode.refNext != None:
presentNode = presentNode.refNext
presentNode.refNext = new_data
new_data.refPrev = presentNode

Step 4:

Write a function to remove a node

This function takes the node object that needs to be removed as a parameter. In order to remove a node, we iterate through the doubly linked list twice. We first start with the head and move forward using refNext and when we encounter the object that needs to be removed we change the refNext value of the present node (which is presently pointing to the object that needs to be removed) to the node that comes after the object that needs to be removed. We then traverse through the linked list backward starting from the tail and when we encounter the object to be removed again we change the refPrev value of the present node to the node that is placed before it.

def remove(self,removeObj):
presentNode = self.head
presentNodeTail = self.tail
while presentNode.refNext != None:
     if(presentNode.refNext == removeObj):
          presentNode.refNext = removeObj.refNext
     presentNode = presentNode.refNext
 while presentNodeTail.refPrev != None:
    if(presentNodeTail.refPrev == removeObj):
        presentNodeTail.refPrev = removeObj.
refPrev
      presentNodeTail = presentNodeTail.refPrev

Code

class Node:
  def_init_(self,data = None):
      self.data = data
      self.refNext = None
      self.refPrev = None
class dLinked_list:
 def_init_(self)':
      self.head = None
      self.tail = None
def append(self, data) :
    new_data = Node(data)
    presentNode = self.head
    while presentNode.refNext != None:
         presentNode = presentNode.refNext
        presentNode.refNext = new_data
        new_data.refPrev = presentNode
       self.tail = new data


def traverse(self):
     presentNode = self.head
     while presentNode:
        print("DATA VALUE = ",presentNode.data)
        presentNode = presentNode.refNext


def traverseReverse(self):
    presentNode = self.tail
    while presentNode:
          print("DATA VALUE = ",presentNode.data)
          presentNode = presentNode.refPrev
def remove(self,removeObj):
    presentNode = self.head
    presentNodeTail = self.tail
    while presentNode.refNext != None:
       if (presentNode.refNext == removeObj):
           presentNode.refNext = removeObj.
refNext
          presentNode = presentNode.refNext
   while presentNodeTail.refPrev != None:
          if (presentNodeTail.refPrev ==
removeObj):
         presentNodeTail.refPrev = removeObj.
refPrev
        presentNodeTail = presentNodeTail.
refPrev

Execution

objNode1 = Node(1)
objNode2 = Node(2)
objNode3 = Node(3)
ObjNode4 = Node(4)
dlinkObj = dLinked_list( )
#head of the linked list to first object
dlinkObj.head = objNode1
dlinkObj.tail = objNode4
# reference of the first node object to second object
dlinkObj.head.refNext = objNode2
dlinkObj.tail.refPrev = objNode3
objNode2.refNext = objNode3
objNode3.refNext = objNode4
objNode4.refPrev = objNode3
objNode3.refPrev = objNode2
objNode2.refPrev = objNode1
print("Appending Values")
dlinkObj.append(8)
dlinkObj.append(9)
print("traversing forward after Append")
dlinkObj.traverse( )
print("traversing reverse after Append")
dlinkObj.traverseReverse( )
print("Removing Values")
dlinkObj.remove(objNode2)
print("traversing forward after Remove")
dlinkObj.traverse( )
print("traversing reverse after Remove")
dlinkObj.traverseReverse( )

Output

objNode1 = Node(1)
objNode2 = Node(2)
objNode3 = Node(3)
objNode4 = Node(4)
dlinkObj = dLinked_list( )
#head of the linked list to first object
dlinkObj.head = objNode1
dlinkObj.tail = objNode4
# reference of the first node object to second object
dlinkObj.head.refNext = objNode2
dlinkObj.tail.refPrev = objNode3
objNode2.refNext = objNode3
objNode3.refNext = objNode4
objNode4.refPrev = objNode3
objNode3.refPrev = objNode2
objNode2.refPrev = objNode1
print("Appending Values")
dlinkObj.append(8)
dlinkObj.append(9)
print("traversing forward after Append")
dlinkObj.traverse( )
print("traversing reverse after Append")
dlinkObj.traverseReverse( )
print("Removing Values")
dlinkObj.remove(objNode2)
print("traversing forward after Remove")
dlinkObj.traverse( )
print("traversing reverse after Remove")
dlinkObj.traverseReverse( )

Question 9.
Write code to reverse a linked list.
Answer:
To reverse a linked list we have to reverse the pointers. Look at the figure shown below. The first table shows how information is stored in the linked list. The second table shows how the parameters are initialized in the reverse( ) function before beginning to traverse through the list and reversing the elements.

Python Interview Questions on Linked List chapter 11 img 1

We then use the following while loop:

while nextval != None:
presentNode.refNext = previous
previous = presentNode
presentNode = nextval
nextval = nextval.refNext
presentNode.refNext = previous
self.head = presentNode

This is how the while loop works:

Python Interview Questions on Linked List chapter 11 img 2

You can see as we iterate through the while loop how the values of presentnode.refNext change. Node1 that was earlier pointing to node2 changes its pointer to none. Same way node2 changes its pointer value to node1, and so on.
Code

class Node:
def_init_(self,data = None):
      self.data = data
      self.refNext = None
class Linked_list:
     def init (self) :
     self.head = None


def reverse(self):
     previous = None
     presentNode = self.head
     nextval = presentNode.refNext
     while nextval != None:
           presentNode.refNext = previous
           previous = presentNode
           presentNode = nextval
           nextval = nextval.refNext
    presentNode.refNext = previous
    self.head = presentNode
def traverse(self) :
    presentNode = self.head
   while presentNode:
     print("DATA VALUE = ",presentNode.data)
     presentNode = presentNode.refNext

Execution

objNode1 = Node(1)
objNode2 = Node(2)
objNode3 = Node(3)
objNode4 = Node(4)
linkObj = Linked_list( )
#head of the linked list to first object
linkObj.head = objNode1
# reference of the first node object to second object
linkObj.head.refNext = objNode2
obj'Node2 . refNext = objNode3
objNode3.refNext = objNode4
print("traverse before reversing")
linkObj.traverse( )
linkObj.reverse( )
print("traverse after reversing")
linkObj.traverse( )

Output

traverse before reversing
DATA VALUE = 1
DATA VALUE = 2
DATA VALUE = 3
DATA VALUE = 4
traverse after reversing
DATA VALUE = 4
DATA VALUE = 3
DATA VALUE = 2
DATA VALUE = 1