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:
- Data
- Reference to next element
In the linked list, each element is called a node.
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.
- Java Program to Remove Nodes from the Beginning and End of a Linked List
- Singly Linked List: How To Insert and Print Node
- Java Program to Print a Linked List in Reverse
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:
- The node object after which the data is to be inserted.
- 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:
- Pointer to the previous node
- Data
- 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.
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:
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