Linked Lists in Python

A linked list is a sequential collection of data elements, which are connected together via links. A linked list consists of independent nodes containing any type of data and each node holds a reference or a link to the next node in the list.

The beginning node of a linked list is called the head and the end node is called the tail. All nodes of a linked list are independent and are not stored contagiously in memory.

The above figure shows a linked list with 4 independent nodes. Each node holds the address of the next node and is linked to it. The head node is the first in the list and therefore has no link pointing towards it. The tail node is identified by a “null” value in the link address.

Linked Lists vs Arrays

Linked List	Array
Linked lists have a dynamic size, i.e., they can be changed at runtime.	The size of an array can not be altered at runtime.
Memory is allocated at runtime.	Memory is allocated at the time of compilation.
The linked list uses more memory as each node holds a reference to the next one as well.	For the same number of elements, arrays use less memory.
Accessing elements is more time consuming	Accessing elements is less time consuming
Operations such as insertion/deletion are faster.	Operations such as insertion/deletion are slower.

Types of Linked Lists

There are 4 types of linked lists that can be created in python.

• Singly Linked List
• Circular Singly Linked List
• Doubly Linked List
• Circular Doubly Linked List

Singly Linked List

In a singly linked list, each node holds a value and a reference/link to the next node. It has no link pointing to the previous node. This is the simplest form of a linked list.

Circular Singly Linked List

The circular singly linked list is similar to a singly linked list. The only difference is that the last node holds a reference to the first node of the linked list.

When we reach the last node of the circular singly linked list, we have an option of going back to the first node. This is not possible in the case of a singly linked list.

Doubly Linked List

In a doubly-linked list, each node of the list has two references, one of the previous node and the other of the next node. Thus, each node holds two addresses along with the data value. Since each node has two references, a doubly-linked list allows us to traverse in both directions.

Circular Doubly Linked List

Circular doubly linked lists are similar to doubly linked lists. The only difference is that their first and last nodes are interconnected as well. The head node holds a reference to the tail node and vice versa.

Hence, in a circular doubly linked list we can perform circular traversal by jumping from the first node to the last node or from the last node to the first node.

Creation of Singly Linked List

We can create a singly linked list in python by following the mentioned steps.

• Step 1: First, we create empty head and tail references and initialize both of them with null.
• Step 2: Create a class “node”. The objects of this class hold one variable to store the values of the nodes and another variable to store the reference addresses.
• Step 3: Create a blank node and assign it a value. Set the reference part of this node to null.
• Step 4: Since we have only one element in the linked list so far, we will link both the head and tail to this node by putting in its reference address.

#Creating the Node class
class Node:
      def __init__(self, value = None):
            self.value = value
            self.next = None

#Create a class to initialize head and tail references
class SinglyLinkedList:
      def __init__(self):
            self.head = None
            self.tail = None

singlyll = SinglyLinkedList()    #Initializing object of singly linked list
temp_node1 = Node(10)
temp_node2 = Node(20)

singlyll.head = temp_node1
singlyll.head.next = temp_node2
singlyll.tail = temp_node2

The iterator function

Since the custom-created linked list is not iterable, we have to add an “__iter__” function so as to traverse through the list.

#Iterator Function
def __iter__(self):
       node = self.head
       while node:
           yield node
           node = node.next

The time complexity for initializing a singly linked list is O(1). The space complexity is O(1) as no additional memory is required to initialize the linked list.

Insertion in Singly Linked List

A node can be inserted in a singly linked list in any one of the following three ways.

• At the beginning of the linked list
• In between the linked list
• At the end of the linked list

Insertion Algorithm

Algorithm to insert a node at the beginning

• Step 1: Create a node and assign a value to it.
• Step 2: Assign the “next” reference of the node as head.
• Step 3: Set the created node as the new head.
• Step 4: Terminate.

Method to insert a node at the beginning

#Insertion at the beginning in a Singly Linked List
class Node:
      def __init__(self, value = None):
            self.value = value
            self.next = None

class SinglyLinkedList:
      def __init__(self):
            self.head = None
            self.tail = None

      #Function to add node in the beginning
      def atBeg(self, value):
            new_node =  Node(value)
            new_node.next = self.head
            self.head = new_node

#Initially, we have a linked list (1,3,5,7,9) called "sll".
sll.atBeg(0)
print([node.value for node in sll])

#Output
[0, 1, 3, 5, 7, 9]

Algorithm to insert a node in between the linked list

• Step 1: Create a node and assign a value to it.
• Step 2: If the previous node doesn’t exist, return an error message and move to step 5.
• Step 3: Assign the “next” reference of the previous node to the “next” reference of the new node.
• Step 4: Set the “next” reference of the previous node to the newly added node.
• Step 5: Terminate.

Method to insert a node in between the linked list

#Insertion in between a Singly Linked List
      #Function to add node in the middle
      def inMid(self,mid_node, value):
             if mid_node is None:
                 print("Mentioned node doesn't exist")
                 return

             new_node = Node(value)
             new_node.next = mid_node.next
             mid_node.next = new_node 

#Initially, we have a linked list (1,3,5,7,9) called "sll" and "mid" node points to the value 3.
sll.inMid(mid, 11)
print([node.value for node in sll])

#Output
[1, 3, 11, 5, 7, 9]

Algorithm to insert a node at the end of the linked list

• Step 1: Create a node and assign a value to it.
• Step 2: If the list is empty, assign new node to head and tail. Move to step 5.
• Step 3: Search for the last node. Once found, set its “next” reference pointing to the new node.
• Step 4: Assign the new node as the tail.
• Step 5: Terminate.

Method to insert a node at the end of the linked list

#Insertion at the end in a Singly Linked List
      #Function to add node in the end
      def atEnd(self, value):
            new_node = Node(value)
            if self.head is None:
                  self.head = new_node
                  self.tail = new_node
                  return
            last_node = self.head
            while(last_node.next):
                  last_node = last_node.next
            last_node.next=new_node
            self.tail = new_node

#Initially, we have a linked list (1,3,5,7,9) called "sll".
sll.atEnd(0)
print([node.value for node in sll])

#Output
[1, 3, 5, 7, 9, 0]

Time and Space Complexity

In python, instead of iterating over the linked list and reaching the required position, we can directly jump to any point. Therefore, the time complexity of insertion in a singly linked list is O(1).

But, for insertion at the end, the time complexity is O(N) as we need to traverse to the last element. The space complexity is O(1) because it takes a constant space to add a new node.

Traversal in Singly Linked List

A singly linked list can only be traversed in the forward direction from the first element to the last. We get the value of the next data element by simply iterating with the help of the reference address.

Traversing Method

#Traversal through Singly Linked List
class Node:
      def __init__(self, value = None):
            self.value = value
            self.next = None

class SinglyLinkedList:
      def __init__(self):
            self.head = None
            self.tail = None

      def printList(self):
              node_print = self.head
              while node_print is not None:
                   print (node_print.value)
                   node_print = node_print.next

#Initially, we have a linked list (1,3,5,7,9) called "sll".
sll.printList()

#Output
1
3
5
7
9

Time and Space Complexity

We need to loop over the linked list to traverse and print every element. The time complexity for traversal is O(N) where ‘N’ is the size of the given linked list. The space complexity is O(1) as no additional memory is required to traverse through a singly linked list.

Searching in a Singly Linked List

To find a node in a given singly linked list, we use the technique of traversal. The only difference, in this case, is that as soon as we find the searched node, we will terminate the loop.

The worst-case scenario for search is when we have the required element at the end of the linked list, in such a case we have to iterate through the entire linked list to find the required element.

Searching Algorithm

• Step 1: If the linked list is empty, return the message and move to step 5.
• Step 2: Iterate over the linked list using the reference address for each node.
• Step 3: Search every node for the given value.
• Step 4: If the element is found, break the loop. If not, return the message “Element not found”.
• Step 5: Terminate.

Searching Method

#Searching in a Singly Linked List
class Node:
      def __init__(self, value = None):
            self.value = value
            self.next = None

class SinglyLinkedList:
      def __init__(self):
            self.head = None
            self.tail = None

       def searchList(self, value): 
             position = 0
             found = 0
             if self.head is None:
                    print ("The linked list does not exist")
             else:
                    temp_node = self.head  
                    while temp_node is not None:
                            position = position + 1
                            if temp_node.value == value:
                                   print ("The required value was found at position: " + str(position))
                                   found = 1
                            temp_node = temp_node.next
             if found == 0:
                    print ("The required value does not exist in the list")    

#Initially, we have a linked list (1,3,5,7,9) called "sll".
print(sll.searchList(7))

#Output
The required value was found at position: 4

Time and Space Complexity

The time complexity for searching a given element in the linked list is O(N) as we have to loop over all the nodes and check for the required one. The space complexity is O(1) as no additional memory is required to traverse through a singly linked list and perform a search.

Deletion of node from Singly Linked List

To delete an existing node from a singly linked list, we must know the value that the node holds. For deletion, we first locate the node previous to the given node. Then we point the “next” reference of this node to the one after the node to be deleted.

A node can be deleted from a singly linked list in any one of the following three ways.

• Deleting the first node
• Deleting any given node
• Deleting the last node

Deletion Algorithm

Algorithm to delete a node from the beginning

• Step 1: If the linked list is empty, return a null statement and go to step 5.
• Step 2: If there’s only one element, delete that node and set head and tail to none. Go to step 5.
• Step 3: Set a “temp_node” pointing at head.
• Step 4: Assign head as the next node. Delete the temp node.
• Step 5: Terminate.

Method to delete a node from the beginning

#Deletion at the beginning of a Singly Linked List
class Node:
      def __init__(self, value = None):
            self.value = value
            self.next = None

class SinglyLinkedList:
      def __init__(self):
            self.head = None
            self.tail = None

       #Function to delete node from the beginning
       def delBeg(self):
          if(self.head == None):
              return
          elif(self.head.next == self.tail.next):
              self.head = self.tail = None
              return
          elif (self.head is not None):
              temp_node = self.head
              self.head = self.head.next
              temp_node = None
              return

#Initially, we have a linked list (1,3,5,7,9) called "sll".
sll.delBeg()
print([node.value for node in sll])

#Output
[3, 5, 7, 9]

Algorithm to delete a node from between the linked list

• Step 1: If the linked list is empty, return a null statement and go to step 6.
• Step 2: If the value to be deleted is the first node, set head to the next element and remove the first node. Go to step .
• Step 3: Iterate through the linked list and search for the element to be deleted.
• Step 4: Set “prev” as the node before the one to be deleted. Break the loop.
• Step 5: Delete the required node and set “next” reference of “prev” to the node after the deleted one.
• Step 6: Terminate.

Method to delete a node from between the linked list

#Function to delete a node from between the linked list
def delMid(self, del_value):
        temp_head = self.head
        if (temp_head is not None):
            if (temp_head.value == del_value):
                self.head = temp_head.next
                temp_head = None
                return

        while (temp_head is not None):
            if temp_head.value == del_value:
                break
            prev = temp_head
            temp_head = temp_head.next

        if (temp_head == None):
            return

        prev.next = temp_head.next
        temp_head = None

#Initially, we have a linked list (1,3,5,7,9) called "sll".
sll.delMid(3)
print([node.value for node in sll])

#Output
[1, 5, 7, 9]

Algorithm to delete a node from the end

• Step 1: If the linked list is empty, return a null statement and go to step 6.
• Step 2: If there’s only one element, delete that node and set head and tail to none. Go to step 6.
• Step 3: Set a “temp_node” pointing at head. Iterate the linked list till that node points to the second last node of the list.
• Step 4: Assign tail as the temp node. Set temp node to the next node, i.e., last in the list.
• Step 5: Delete the temp_node.
• Step 6: Terminate.

Method to delete a node from the end

#Function to delete node from the end
def delEnd(self):
        if(self.head == None):
            return
        elif (self.head.next == self.tail.next):
            self.head = self.tail = None
            return
        else:
            temp_node = self.head
            while (temp_node.next is not self.tail):
                temp_node = temp_node.next
            self.tail = temp_node
            temp_node.next = None
        return
#Initially, we have a linked list (1,3,5,7,9) called "sll".
sll.delEnd()
print([node.value for node in sll])

#Output
[1, 3, 5, 7]

Time and Space Complexity

The time complexity for deletion in a singly linked list is O(N) as we have to loop over all the nodes and search for the required one. The space complexity is O(1) as no additional memory is required to delete an element from a singly linked list.

Deletion of entire Singly Linked List

The deletion of an entire singly linked list is quite a simple process. We have to set the two reference nodes “head” and “tail” to none.

Algorithm to delete an entire singly linked list

• Step 1: If the linked list is empty, return an error message and go to step 4.
• Step 2: Delete the “head” node by setting it to none.
• Step 3: Delete the “tail” node by setting it to none.
• Step 4: Terminate.

Method to delete an entire singly linked list

#Deletion of an entire Singly Linked List
class Node:
      def __init__(self, value = None):
            self.value = value
            self.next = None

class SinglyLinkedList:
      def __init__(self):
            self.head = None
            self.tail = None

      def delSLL(self):
        if self.head is None:
            print("The singly linked list does not exist.")
        else:
            self.head = None
            self.tail = None
        print("The singly linked list has been deleted.")      
           
#Initially, we have a linked list (1,3,5,7,9) called "sll".
sll.delSLL()

#Output
The singly linked list has been deleted.

Time and Space Complexity

The time complexity for deletion of an entire singly linked list is O(1) because we are just setting the “head” and “tail” references to none. The space complexity is O(1) as well since there is no additional space required when deleting the references.

Time Complexity of Linked List vs Array

Operations	Array	Linked List
Creation	O(1)	O(1)
Insertion at beginning	O(1)	O(1)
Insertion in between	O(1)	O(1)
Insertion at end	O(1)	O(n)
Searching in Unsorted Data	O(n)	O(n)
Searching in Sorted Data	O(logn)	O(n)
Traversal	O(n)	O(n)
Deletion at beginning	O(1)	O(1)
Deletion in between	O(1)	O(n)/O(1)
Deletion at end	O(1)	O(n)
Deletion of entire linked list/array	O(1)	O(n)/O(1)
Accessing elements	O(1)	O(n)

Interview Questions on Singly Linked List

Write a code to remove duplicate values from an unsorted linked list.

To solve the duplicate value problem, we initialize a set called ‘visited’. It stores every value we encounter while iterating the linked list. If a value already exists in ‘visited’, we can then remove it from the list.

#Code to remove duplicate values from a linked list
def removeDuplicates(linkedList):
       if linkedList.head is None:
            return
       else: 
            current_node = linkedList.head
            visited = set([current_node.value])
            while current_node.next:
                  if current_node.next.value in visited:
                        current_node.next = current_node.next.next
                  else:
                        visited.add(current_node.next.value)
                        current_node = current_node.next
            return linkedList   
      

The time complexity of this algorithm is O(N) as we need to iterate over the entire linked list to check for any duplicate item. The space complexity is O(N) as well since the ‘visited’ set gets dynamically filled during iteration.

Implement a code to find the Kth to last element in a singly linked list.

To find the Kth to the last element in a linked list, we initialize two pointers. While one pointer iterates to the end of the linked list, the other pointer stops at Kth to the last element.

#Code to find Kth to last element in a singly linked list
def kthToLast(linkedList, k):
       first_pointer = linkedList.head
       second_pointer = linkedList.head
            
       for i in range(k): 
            if second_pointer is None:
                return None
            second_pointer = second_pointer.next
        
       while second_pointer:
            first_pointer = first_pointer.next
            second_pointer = second_pointer.next
       return first_pointer

#Initially, we have a linked list (1,3,5,7,9) called "sll".
print(kthToLast(sll, 3))

#Output
5

The time complexity of this algorithm is O(N) as we need to iterate over the entire linked list to set the pointers. The space complexity is O(1) as no additional memory is required to assign the references.

Write a code to partition a linked list around a value x. All nodes less than x come before all the nodes greater than or equal to x.

#Code to partition the linked list around a value 'x'
def partition(linkedList, x):
       current_node = linkedList.head
       linkedList.tail = linkedList.head   
            
       while current_node: 
               next_node = current_node.next
               current_node.next = None
               if current_node.value < x:
                    current_node.next = linkedList.head
                    linkedList.head = current_node
               else:
                    linkedList.tail.next = current_node
                    linkedList.tail = current_node
               current_node = current_node.next    
       if linkedList.tail.next is not None:
               linkedList.tail.next = None  

#Initially, we have a linked list (7,3,9,11,1,5) called "sll".
partition(sll, 6)
print([node.value for node in sll])

#Output
[5, 1, 3, 9, 11, 5]

The time complexity of this algorithm is O(N) as we need to iterate over the entire linked list to set the partition. The space complexity is O(1) as no additional memory is required.

There are two numbers represented by a linked list, where each node contains a single digit. The digits are placed in reverse order, i.e., the 1’s digit is at the head of the list. Write a function to add the two numbers and returns the sum as a linked list.

#Code to return the sum of two numbers represented by linked lists
def sumList(linkedList1, linkedList2):
       num1 = linkedList1.head
       num2 = linkedList2.head   
       carry = 0
       newLL = SinglyLinkedList()
            
       while num1 or num2: 
               result = carry
               if num1:
                    result += num1.value
                    num1 = num1.next
               if num2:
                    result += num2.value
                    num2 = num2.next
               newLL.add(int(result % 10))  
               carry = result /10
       return newLL   

#Initially, we have a linked list (7, 1, 6) called "sll1" and (5, 9, 2) called "sll2".
print(sll1)
print(sll2)
print(sumList(sll1, sll2))

#Output
7 -> 1 -> 6
5 -> 9 -> 2
2 -> 1 -> 9

The time complexity of this algorithm is O(N) as we need to iterate over the entire linked list. The space complexity is O(n) as we fill up the newly created linked list dynamically.

Determine whether two given singly-linked lists intersect. Return the intersecting node. The intersection is defined based on the node’s reference, not its value. It means that if the nth node of the first linked list is the same as the mth node of the second linked list, then they are intersecting.

#Code to check whether two lists are intersecting
def intersection(linkedList1, linkedList2):
       if linkedList1.tail is not linkedList2.tail:
             return False       
       lenA = len(linkedList1)     
       lenB = len(linkedList2) 
       shorter = linkedList1 if lenA < lenB else linkedList2
       longer = linkedList2 if lenA < lenB else linkedList1
       diff = len(longer) - len(shorter)
       longer_node = longer.head
       shorter_node = shorter.head

       for i in range(diff):
            longer_node = longer_node.next
       while shorter_node is not longer_node:
            shorter_node = shorter_node.next
            longer_node = longer_node.next 
       return longer_node

#Initially, we have a linked list (7, 1, 6, 8) called "sll1" and (5, 9, 6, 2) called "sll2". Suppose the node with value 6 is the same for both the linked lists.
print(intersection(sll1, sll2))

#Output
6

The time complexity of this algorithm is O(A + B) where A is the length of the first linked list and B is the length of the second linked list. We need to traverse both lists to find the number of nodes. The space complexity is O(1) as no additional memory is required.

FAQ question

What is a Linked List in Python?

In a linked list, each data element contains a connection to another data element in form of a pointer. Python does not have linked lists in its standard library.

class Node:
   def __init__(self, dataval=None):
      self.dataval = dataval
      self.nextval = None

class SLinkedList:
   def __init__(self):
      self.headval = None
   def listprint(self):
      printval = self.headval
      while printval is not None:
         print (printval.dataval)
         printval = printval.nextval

list = SLinkedList()
list.headval = Node("Monday")
day2 = Node("Tuesday")
day3 = Node("Wednesday")
list.headval.nextval = day2
day2.nextval = day3
list.listprint()

Output

Monday
Tuesday
Wednesday

How to Reverse a Linked List in Python?

The iterative method is used in the user-defined reverse() function to reverse the linked list.

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

	def reverse(self):
		prev = None
		current = self.head
		while(current is not None):
			next = current.next
			current.next = prev
			prev = current
			current = next
		self.head = prev

	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	def printList(self):
		temp = self.head
		while(temp):
			print(temp.data)
			temp = temp.next

llist = LinkedList()
llist.push(200)
llist.push(40)
llist.push(175)
llist.push(85)
print("Given Linked List")
llist.printList()
llist.reverse()
print("\nReversed Linked List")
llist.printList()

Output

Given Linked List
85
175
40
200

Reversed Linked List
200
40
175
85

How to create a Linked List in Python

A linked list is a data structure made of a chain of node objects. Each node contains a value and a pointer to the next node in the chain.

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

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

  def insert(self, data):
    newNode = Node(data)
    if(self.head):
      current = self.head
      while(current.next):
        current = current.next
      current.next = newNode
    else:
      self.head = newNode

  def printLL(self):
    current = self.head
    while(current):
      print(current.data)
      current = current.next

LL = LinkedList()
LL.insert(98)
LL.insert(23)
LL.insert(5)
LL.printLL()

Output

98
23
5

How to Sort a Linked List in Python?

In the below code, while the node is not null, value is added at the end of the node, Which is given by node = next of node. Then the list of values is sorted.

class Solution:
    def solve(self, node):
        values = []
        head = node
        while node:
            values.append(node.val)
            node = node.next
        values.sort()
        values = collections.deque(values)
        node = head
        while node:
            node.val = values.popleft()
            node = node.next
        return head

ob = Solution()
head = make_list([5, 8, 41, 21, 5, 60, 3])
print_list(ob.solve(head))

Output

[3, 5, 5, 8, 21, 41, 60, ]

How to Use the Linked List in a Loop using Python?

To traverse through the Linked list loops can be used. In the below code, a while loop is used to traverse through the linked list.

class Node:
   def __init__(self, dataval=None):
      self.dataval = dataval
      self.nextval = None

class SLinkedList:
   def __init__(self):
      self.headval = None
   def listprint(self):
      printval = self.headval
      while printval is not None:
         print (printval.dataval)
         printval = printval.nextval

list = SLinkedList()
list.headval = Node("Monday")
day2 = Node("Tuesday")
day3 = Node("Wednesday")
list.headval.nextval = day2
day2.nextval = day3
list.listprint()

Output

Monday
Tuesday
Wednesday

How to Transform a Linked List to a Normal List in Python?

The list comprehension can be used to convert a linked list into a list.

child = {'Hello':'Welcome', 'Welcome': 'To', 'To': 'Pythonwife', 'Pythonwife': None}
def ll_iterator(node):
    while node != None:
        yield node
        node = child[node]
[x for x in ll_iterator('Hello')]

Output

['Hello', 'Welcome', 'To', 'Pythonwife']

How to Put Contents from an Array into a Linked List using Python?

We create a node in a linked list for each element of an array arr[] and insert it at the end.

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

# Function to insert node
def insert(root, item):
	temp = Node(item)
	
	if (root == None):
		root = temp
	else :
		ptr = root
		while (ptr.next != None):
			ptr = ptr.next
		ptr.next = temp
	return root

def display(root):
	while (root != None) :
		print(root.data, end = " ")
		root = root.next

def arrayToList(arr, n):
	root = None
	for i in range(0, n, 1):
		root = insert(root, arr[i])
	return root

if __name__=='__main__':
	arr = [1, 2, 3, 4, 5]
	n = len(arr)
	root = arrayToList(arr, n)
	display(root)

Output

1 2 3 4 5 

How to Reverse a Linked List Recursively using Python?

The reverse() function is called recursively to reverse the linked list.

def reverse(head, headRef):
    if head is None:
        return headRef
    first = head                
    rest = first.next          
    if rest is None:
        headRef = first
        return headRef
    headRef = reverse(rest, headRef)
    rest.next = first
    first.next = None       
    return headRef

def reverseList(head):
    return reverse(head, head) 
if __name__ == '__main__':
    head = None
    for i in reversed(range(6)):
        head = Node(i + 1, head)
    head = reverseList(head)
    printList(head)

Output

6 —> 5 —> 4 —> 3 —> 2 —> 1 —> None

How to Pass a Linked List as a Parameter in Python?

The linked list can be passed as a parameter, like any other list by enclosing the elements in [] symbol.

class MyContainer(object):
    def __init__(self, iterable=None):
        if iterable is not None:
            self.data = list(iterable)
        else:
            self.data = []
            def walk_container(self, f):
                for x in self.data:
                    print(f(x))
                    def _increment(self, x):
                        return x + 1
                    def print_increments(self):
                        self.walk_container(self._increment)

c = MyContainer([10,31,42])
c.print_increments()

Output

10
31
42

How to Sort a Linked List in Alphabetical Order in Python?

def sort(self):
		Ahead = self.Node(0)
		Dhead = self.Node(0)
		self.splitList(Ahead, Dhead)
		Ahead = Ahead.next
		Dhead = Dhead.next
		Dhead = self.reverseList(Dhead)
		self.head = self.mergeList(Ahead, Dhead)

def reverseList(self, Dhead):
		current = Dhead
		prev = None
		while current != None:
			self._next = current.next
			current.next = prev
			prev = current
			current = self._next
		Dhead = prev
		return Dhead

def mergeList(self, head1, head2):
		if head1 == None:
			return head2
		if head2 == None:
			return head1
		temp = None
		if head1.data < head2.data:
			temp = head1
			head1.next = self.mergeList(head1.next, head2)
		else:
			temp = head2
			head2.next = self.mergeList(head1, head2.next)
		return temp

def splitList(self, Ahead, Dhead):
		ascn = Ahead
		dscn = Dhead
		curr = self.head
		while curr != None:
			ascn.next = curr
			ascn = ascn.next
			curr = curr.next
			if curr != None:
				dscn.next = curr
				dscn = dscn.next
				curr = curr.next
		ascn.next = None
		dscn.next = None

llist = LinkedList()
llist.head = llist.newNode('a')
llist.head.next = llist.newNode('hello')
llist.head.next.next = llist.newNode('bat')
llist.head.next.next.next = llist.newNode('pythonwife')
llist.head.next.next.next.next = llist.newNode('website')
llist.head.next.next.next.next.next = llist.newNode('tech')
llist.head.next.next.next.next.next.next = llist.newNode('python')
print('Given linked list')
llist.printList()
llist.sort()
print('Sorted linked list')
llist.printList()

Output

Given linked list
a
hello
bat
pythonwife
website
tech
python

Sorted linked list
a
bat
hello
python
pythonwife
tech
website

How to Make an Empty Linked List in Python?

The Empty linked list is created by not inserting any elements into the list.

    class Node:
       def __init__(self, dataval=None):
          self.dataval = dataval
          self.nextval = None

    class SLinkedList:
       def __init__(self):
          self.headval = None
       def listprint(self):
          printval = self.headval
          while printval is not None:
             print (printval.dataval)
             printval = printval.nextval

    list = SLinkedList()
    list.headval = Node()
    list.listprint()

Output

None

How to Check if an Element is in a Linked List using Python?

The search() user-defined function is used to traverse through the list and search for the elements.

def search(self, x):
	current = self.head
	while current != None:
		if current.data == x:
			return True 
		current = current.next
		
	return False 
if __name__ == '__main__':
	llist = LinkedList()
	llist.push('hello');
	llist.push(30);
	llist.push('python wife');
	llist.push(21);
	llist.push(14);
	if llist.search('hello'):
		print("Yes the item is present")
	else:
		print("No the item is not found")
       if llist.search('hi'):
	print("Yes the item is present") 
       else:
	print("No the item is not found")

Output

Yes the item is present
No the item is not found

What does Iterator Do in Linked List in Python?

The python has an inbuilt function called iter() which can be used to iterate through the linked list. The next() function will call the next element in the list.

iterable_value = ['Python','Wife','Website','Technology','Knowledge']
iterable_obj = iter(iterable_value)
while True:
	try:
		item = next(iterable_obj)
		print(item)
	except StopIteration:
		break

Output

Python
Wife
Website
Technology
Knowledge

How to make a Doubly Linked List in Python?

 The doubly linked list can be traversed in a backward direction thus making insertion and deletion operations easier to perform.

class Node:    
    def __init__(self,data):    
        self.data = data;    
        self.previous = None;    
        self.next = None;  
  
class DoublyLinkedList:       
    def __init__(self):    
        self.head = None;       
    def addNode(self, data):       
        newNode = Node(data);       
        if(self.head == None):        
            self.head = self.tail = newNode;       
            self.head.previous = None;        
            self.tail.next = None;    
        else:       
            self.tail.next = newNode;        
            newNode.previous = self.tail;      
            self.tail = newNode;      
            self.tail.next = None;  
      
    def display(self):      
        current = self.head;    
        if(self.head == None):    
            print("List is empty");    
            return;    
        print("Nodes of doubly linked list: ");    
        while(current != None):         
            print(current.data),;    
            current = current.next; 
                
dList = DoublyLinkedList();       
dList.addNode("Hello");    
dList.addNode("Welcome");    
dList.addNode(3);    
dList.addNode("Pythonwife");    
dList.addNode(5);        
dList.display(); 

Output

Nodes of doubly linked list: 
Hello
Welcome
3
Pythonwife
5

How to Delete a Node in Linked List using Python?

The linked list is traversed through and the element to be deleted is found. Once found the node is removed and the next pointer is made to point to the next following element.

def deleteNode(self, key):
		temp = self.head
		if (temp is not None):
			if (temp.data == key):
				self.head = temp.next
				temp = None
				return
		while(temp is not None):
			if temp.data == key:
				break
			prev = temp
			temp = temp.next
		if(temp == None):
			return
		prev.next = temp.next
		temp = None

llist = LinkedList()
llist.push(4)
llist.push(10)
llist.push(34)
llist.push(21)
print ("Linked List: ")
llist.printList()
llist.deleteNode(4)
print ("\nLinked List after Deletion of 4 :")
llist.printList()

Output

Linked List: 
 21
 34
 10
 4

Linked List after Deletion of 4 :
 21
 34
 10

How to Delete the Last Node in the Linked List using Python?

The secondlast node is used to traverse through the linked list till the second last element. Then the last node, which is the next node of the secondlast node is deleted.

import sys
import math
def removeLastNode(head):
	if head == None:
		return None
	if head.next == None:
		head = None
		return None
	second_last = head
	while(second_last.next.next):
		second_last = second_last.next
	second_last.next = None
	return head

if __name__=='__main__':
	head = None
	head = push(head, 12)
	head = push(head, 29)
	head = push(head, 11)
	head = push(head, 23)
	head = push(head, 8)
head = removeLastNode(head)
while(head):
    print("{} ".format(head.data), end ="")
    head = head.next

Output

8 23 11 29 

How to Loop Through Elements of Linked List in Python?

In the linked list both for loop and while loop can be used to traverse through the list.

   def append_item(self, data):
        #Append items on the list
        node = Node(data)
        if self.head:
            self.head.next = node
            self.head = node
        else:
            self.tail = node
            self.head = node
        self.count += 1

    def iterate_item(self):
        # Iterate the list.
        current_item = self.tail
        while current_item:
            val = current_item.data
            current_item = current_item.next
            yield val

items = singly_linked_list()
items.append_item('Welcome')
items.append_item('You')
items.append_item('All')
items.append_item('To')
items.append_item('Pythonwife')
items.append_item('Website')
print("list:")
for val in items.iterate_item():
    print(val)

Output

list:
Welcome
You
All
To
Pythonwife
Website

How to Convert an Array List into Linked List in Python?

We build a node in a linked list for each element of an array arr[] and insert it at the end.

import math
def display(root):
	while (root != None) :
		print(root.data, end = " ")
		root = root.next

def ConvertarrayToList(arr, n):
	root = None
	for i in range(0, n, 1):
		root = insert(root, arr[i])
	return root

if __name__=='__main__':
	arr = [10, 20, 30, 40, 50]
	n = len(arr)
	root = ConvertarrayToList(arr, n)
	display(root)

Output

10 20 30 40 50 

How to Implement Deque Singly Linked List in Python?

The enqueue and dequeue operations are performed on the singly linked list.

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

class Queue:
    rear = None
    front = None

    def dequeue(self):
        if self.front is None:
            print("Queue Underflow")
            exit(1)
        temp = self.front
        print("Removing…", temp.data)
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        item = temp.data
        return item

    def enqueue(self, item):
        node = Node(item)
        print("Inserting…", item)
        if self.front is None:
            self.front = node
            self.rear = node
        else:
            self.rear.next = node
            self.rear = node

    def peek(self):
        if self.front:
            return self.front.data
        else:
            exit(1)
        return -1
    def isEmpty(self):
        return self.rear is None and self.front is None

if __name__ == '__main__':
    q = Queue()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    q.enqueue(4)
    print("The front element is", q.peek())
    q.dequeue()
    q.dequeue()
    if q.isEmpty():
        print("The queue is empty")
    else:
        print("The queue is not empty")

Output

Inserting… 1
Inserting… 2
Inserting… 3
Inserting… 4
The front element is 1
Removing… 1
Removing… 2
The queue is not empty

How to Find the Length of a Singly Linked List in Python?

The variable count is incremented till the node becomes null.

def getCount(self):
	temp = self.head 
	count = 0 
	while (temp):
		count += 1
		temp = temp.next
	return count

if __name__=='__main__':
	llist = LinkedList()
	llist.push(1)
	llist.push(3)
	llist.push(1)
	llist.push(2)
	llist.push(1)
	print ("length of singly linked list is :",llist.getCount())

Output

length of singly linked list is : 5

How to Insert an Element at a Specific Position in Linked List using Python?

Up to position-1 nodes, traverse the Linked list. Allocate memory and the specified data to the new node once all of the position-1 nodes have been traversed. Point the new node’s next pointer to the current node’s next pointer. Point the current node’s next pointer to the new node.

  def push_at(self, newElement, position):     
    newNode = Node(newElement) 
    if(position < 1):
      print("\nposition should be >= 1.")
    elif (position == 1):
      newNode.next = self.head
      self.head = newNode
    else:    
      temp = self.head
      for i in range(1, position-1):
        if(temp != None):
          temp = temp.next   
      if(temp != None):
        newNode.next = temp.next
        temp.next = newNode  
      else:
        print("\nThe previous node is null.") 
        
MyList = LinkedList()
#Add three elements at the end of the list.
MyList.push_back(10)
MyList.push_back(20)
MyList.push_back(30)
MyList.PrintList()
#Insert an element at position 2
MyList.push_at(100, 2)
MyList.PrintList() 
#Insert an element at position 1
MyList.push_at(200, 1)

Output

The list contains: 10 20 30 
The list contains: 10 100 20 30 
The list contains: 200 10 100 20 30 

Why Does a Linked List Return None in Python?

It is possible to reach the end of next without a return statement, any Python function will return None.

class FindOdd:
    def __init__(self,end):
        self.__start = 1
        self.__end = end
    def __iter__(self):
        return OddsIterator(self.__end)

class OddsIterator:
    def __init__(self,finish): 
        self.__current = 0
        self.__step = 1
        self.__end = finish
    def __next__(self):
        x = None
        if self.__current > self.__end:
            raise StopIteration 
        else:
            self.__current += self.__step 
            if (self.__current - self.__step + 1) % 2 != 0:
                x = self.__current - self.__step + 1
        if x != None:
            return x 

odds = FindOdd(2)
print(list(odds))

Output

[1, None, 3]

How to Find the Smallest Element in the Linked List using Python?

The linked list is traversed until the head is not NULL, and the min variable is set to INT MIN. Then, if the min value is larger than the head value, the head value is assigned to the min node; otherwise, the head point is to the next node. This method should be repeated until the head is not equal to NULL.

def smallestElement(head):
	min = 32767
	while (head != None) :
		if (min > head.data) :
			min = head.data
		head = head.next
	return min

def printList( head) :
	while (head != None) :
		print(head.data ,end= " -> ")
		head = head.next	
	print("None")

push( 15)
push( 14)
push( 13)
push( 22)
push( 17)
print("Linked list is : ")
printList(head)
print("Minimum element in linked list: ",end="")
print(smallestElement(head),end="")

Output

Linked list is : 
17 -> 22 -> 13 -> 14 -> 15 -> None
Minimum element in linked list: 13

How to Concatenate Two Linked Lists in Python?

The dummy node is created, which initially points to some node when the result list is empty. This dummy node is efficient, since it is only temporary, and it is allocated in the stack. The loop proceeds, removing one node from either ‘a’ or ‘b’ and adding it to the tail.

def mergeLists(headA, headB):
	dummyNode = Node(0)
	tail = dummyNode
	while True:
		if headA is None:
			tail.next = headB
			break
		if headB is None:
			tail.next = headA
			break
		if headA.data <= headB.data:
			tail.next = headA
			headA = headA.next
		else:
			tail.next = headB
			headB = headB.next
		tail = tail.next
	return dummyNode.next

listA = LinkedList()
listB = LinkedList()
listA.addToList(50)
listA.addToList(120)
listA.addToList(115)
print("List A : ")
listA.printList()
listB.addToList(2)
listB.addToList(60)
listB.addToList(205)
print("\nList B : ")
listB.printList()
listA.head = mergeLists(listA.head, listB.head)
print("\nMerged Linked List is:")
listA.printList()

Output

List A : 
50 120 115 
List B : 
2 60 205 
Merged Linked List is:
2 50 60 115 120 205 

How to Add an Element to the End of a Linked List in Python?

The user-defined push_back() function is used to add elements to the end of the linked list.

  def push_back(self, newElement):
    newNode = Node(newElement)
    if(self.head == None):
      self.head = newNode
      return
    else:
      temp = self.head
      while(temp.next != None):
        temp = temp.next
      temp.next = newNode

  def PrintList(self):
    temp = self.head
    if(temp != None):
      print("The list contains:", end=" ")
      while (temp != None):
        print(temp.data, end=" ")
        temp = temp.next
      print()
    else:
      print("The list is empty.")  
             
MyList = LinkedList()
MyList.push_back(10)
MyList.push_back(20)
MyList.push_back(30)
MyList.PrintList()

Output

The list contains: 10 20 30 

How to Append to the Linked List in Python?

The user-defined function append_element() can be used to append elements to the linked list.

    def append_element(self, data):
        #Append items on the list
        node = Node(data)
        if self.tail:
            self.tail.next = node
            self.tail = node
        else:
            self.head = node
            self.tail = node
        self.count += 1

items = singly_linked_list()
items.append_element('C')
items.append_element('Python')
items.append_element('C#')
items.append_element('C++')
items.append_element('HTML')
for val in items.iterate_item():
    print(val)

Output

C
Python
C#
C++
HTML

How to Add Characters to Linked List in Python?

The characters can be added to the linked list, by passing the character as the node to the append() and push() functions.

	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	def append(self, new_data):
		new_node = Node(new_data)
		if self.head is None:
			self.head = new_node
			return
		last = self.head
		while (last.next):
			last = last.next
		last.next = new_node

if __name__=='__main__':
	llist = LinkedList()
	llist.append('a')
	llist.push('z');
	llist.push('x');
	llist.append('p')
	print ('Created linked list is:')
	llist.printList()

Output

Created linked list is:
x
z
a
p

How to Move the Elements of the Linked List in Python?

Traverse down the list until you reach the last node. Use two pointers: one for the final node’s address and the other for the second last node’s address. Do the following activities after the loop has ended.

• Set secLast->next = NULL to make the second last the last.
• Use last->next = *head ref as the head .
• Assign the last position as the head (*head ref = last).

	def moveToFront(self):
		tmp = self.head
		sec_last = None 
		if not tmp or not tmp.next:
			return
		while tmp and tmp.next :
			sec_last = tmp
			tmp = tmp.next
		sec_last.next = None
		tmp.next = self.head
		self.head = tmp

if __name__ == '__main__':
	llist = LinkedList()
	llist.push("Website")
	llist.push("Pythonwife")
	llist.push("to")
	llist.push("all")
	llist.push("Welcome")
	print ("Before moving ")
	llist.printList()
	llist.moveToFront()
	print ("After moving")
	llist.printList()

Output

Before moving 
Welcome, all, to, Pythonwife, Website, 
After moving
Website, Welcome, all, to, Pythonwife, 

How to Remove a Node from the Linked List using Python?

Locate the previous node of the to-be-deleted node. Change the preceding node’s next node. To delete a node, the memory of the node is freed.

	def removeNode(self, key):
		temp = self.head
		if (temp is not None):
			if (temp.data == key):
				self.head = temp.next
				temp = None
				return
		while(temp is not None):
			if temp.data == key:
				break
			prev = temp
			temp = temp.next
		if(temp == None):
			return
		prev.next = temp.next
		temp = None
	def printList(self):
		temp = self.head
		while(temp):
			print (" %d" %(temp.data)),
			temp = temp.next

llist = LinkedList()
llist.push(70)
llist.push(231)
llist.push(36)
llist.push(24)
print ("Created Linked List: ")
llist.printList()
llist.removeNode(231)
print ("\nLinked List after Deletion of 231:")
llist.printList()

Output

Created Linked List: 
 24
 36
 231
 70

Linked List after Deletion of 231:
 24
 36
 70

How to Remove Duplicate Nodes in an Unsorted Linked List using Python?

The user-defined removeduplicate() function that takes a list as an argument and deletes any duplicate node from the list can be used to remove duplicate nodes in an unsorted linked list.

	def removeduplicate(self):
		ptr1 = None
		ptr2 = None
		dup = None
		ptr1 = self.head
		while (ptr1 != None and ptr1.next != None):
			ptr2 = ptr1
			while (ptr2.next != None):
				if (ptr1.data == ptr2.next.data):
					dup = ptr2.next
					ptr2.next = ptr2.next.next
				else:
					ptr2 = ptr2.next
			ptr1 = ptr1.next

list = LinkedList()
list.head = Node(10)
list.head.next = Node(12)
list.head.next.next = Node(11)
list.head.next.next.next = Node(11)
list.head.next.next.next.next = Node(110)
list.head.next.next.next.next.next = Node(12)
list.head.next.next.next.next.next.next = Node(10)
print("Before removing duplicates :")
list.printList()
list.removeduplicate()
print()
print("After removing duplicates :")
list.printList()

Output

Before removing duplicates :
10 12 11 11 110 12 10 

After removing duplicates :
10 12 11 110 

how to merge two unsorted linked lists in python

The dummy node is created, which initially points to some node when the result list is empty. This dummy node is efficient, since it is only temporary, and it is allocated in the stack. The loop proceeds, removing one node from either ‘a’ or ‘b’ and adding it to the tail.

def mergeLists(headA, headB):
	dummyNode = Node(0)
	tail = dummyNode
	while True:
		if headA is None:
			tail.next = headB
			break
		if headB is None:
			tail.next = headA
			break
		if headA.data <= headB.data:
			tail.next = headA
			headA = headA.next
		else:
			tail.next = headB
			headB = headB.next
		tail = tail.next
	return dummyNode.next

listA = LinkedList()
listB = LinkedList()
listA.addToList(50)
listA.addToList(120)
listA.addToList(115)
print("List A : ")
listA.printList()
listB.addToList(2)
listB.addToList(60)
listB.addToList(205)
print("\nList B : ")
listB.printList()
listA.head = mergeLists(listA.head, listB.head)
print("\nMerged Linked List is:")
listA.printList()

Output

List A : 
50 120 115 
List B : 
2 60 205 
Merged Linked List is:
2 50 60 115 120 205 

How to Iterate the Linked Lists Backwards in Python?

The head pointer is passed to this method as a node. Check if the next node of a node is Null: If yes, we have reached the end of the linked list. Set the head pointer to this node. If no, pass the next node of the node to the reversetraverse() method.

	def reversetraverse(self):
		prev = None
		current = self.head
		while(current is not None):
			next = current.next
			current.next = prev
			prev = current
			current = next
		self.head = prev

llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(85)
print ("Given Linked List")
llist.printList()
llist.reversetraverse()
print ("\nReversed Linked List")
llist.printList()

Output

Given Linked List
85
15
4
20

Reversed Linked List
20
4
15
85

How to Know if a Linked List has a Loop in Python?

To detect if a linked list has a loop or not hashing approach can be used. In hashing method, The list is traversed and the node address is added to the hash table. If NULL is reached at any time, return false; otherwise, return true if the next of the current nodes points to any of the previously recorded nodes in Hash.

	def findLoop(self):
		s = set()
		temp = self.head
		while (temp):
			if (temp in s):
				return True
			s.add(temp)
			temp = temp.next
		return False

llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(10)
llist.head.next.next.next.next = llist.head
if(llist.findLoop()):
	print("Loop found")
else:
	print("No Loop ")

Output

Loop found

How To Return a Linked List in Python?

Like any other data linked list can also be returned from the function.

def returnlist():
    x=[1,2,3,4]
    return x
print(returnlist())

Output

[1, 2, 3, 4]

How to Index a Linked List in Python?

The Linked List is traversed through and the count variable is used to keep track of the index of the element.

    def findIndex(self, x):
        current = self.head
        count = 0 
        while current != None:
            if current.data == x:
                print("Index of 21 is ",count)
                return True
            count++
            current = current.next
        return False

if __name__ == '__main__':
	llist = LinkedList()
	llist.push(10);
	llist.push(30);
	llist.push(11);
	llist.push(21);
	llist.push(14);

	if llist.search(21):
		print("Yes")
	else:
		print("No")

Output

Index of 21 is 1
Yes

How to Traverse the Linked List in Python?

The while loop can be used to traverse through the linked list.

def printList(self):
    node_print = self.head
    while node_print is not None:
        print (node_print.value)
        node_print = node_print.next

sll = LinkedList()
sll.push(20)
sll.push(4)
sll.push(15)
sll.push(10)
sll.printList()

Output

20
4
15
10

How to Interleave Two Linked Lists in Python?

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

def make_list(elements):
   head = ListNode(elements[0])
   for element in elements[1:]:
      ptr = head
      while ptr.next:
         ptr = ptr.next
      ptr.next = ListNode(element)
   return head

def print_list(head):
   ptr = head
   print('[', end = "")
   while ptr:
      print(ptr.val, end = ", ")
      ptr = ptr.next
print(']')

class Solution:
   def solve(self, l1, l2):
      ans = l1
      while l2:
         if ans:
            if ans.next != None:
               newnode = ListNode(l2.val, None)
               newnode.next = ans.next
               ans.next = newnode
               ans = newnode.next
               l2 = l2.next
            else:
               ans.next = l2
               return l2
           else:
               return l1

ob = Solution()
l1 = make_list([5,4,6,3,4,7])
l2 = make_list([8,6,9])
res = ob.solve(l1,l2)
print_list(res)

Output

[5, 8, 4, 6, 6, 9, 3, 4, 7, ]

How To Make a List that has Some Words Linked Together in Python?

The list has some words can be linked together using List comprehension.

test_list = ['Python', '52', 'wife', '93', 'Website' , '12', '35']
print("The given list : " + str(test_list))
res = [''.join([i for i in test_list if not i.isdigit()]),
				*[j for j in test_list if j.isdigit()]]
print("The joined adjacent words : " + str(res))

Output

The given list : ['Python', '52', 'wife', '93', 'Website', '12', '35']
The joined adjacent words : ['PythonwifeWebsite', '52', '93', '12', '35']

How to Insert an Array in Linked List using Python?

The array is passed as a node to push() and append() function to insert it into a linked list.

	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	def append(self, new_data):
		new_node = Node(new_data)
		if self.head is None:
			self.head = new_node
			return
		last = self.head
		while (last.next):
			last = last.next
		last.next = new_node

if __name__=='__main__':
	llist = LinkedList()
	llist.append(6)
	llist.push(7);
	llist.push([1,2]);
	llist.append([9,7])
	print ('Created linked list is:')
	llist.printList()

Output

Created linked list is:
[1, 2]
7
8
6
[9, 7]

How to Implement a Stack using a Linked List in Python?

In stack Implementation using Linked List, a stack contains a top pointer. This is the head of the stack, where items are pushed and popped at the top of the list. The first node’s link field is null, the second node’s link field is the first node’s address, and so on, with the last node’s address in the top pointer.

class Node:
	
	# Class to create nodes of linked list
	# constructor initializes node automatically
	def __init__(self,data):
		self.data = data
		self.next = None
class Stack:
	def __init__(self):
		self.head = None
	def isempty(self):
		if self.head == None:
			return True
		else:
			return False

	def push(self,data):
		if self.head == None:
			self.head=Node(data)			
		else:
			newnode = Node(data)
			newnode.next = self.head
			self.head = newnode

	def pop(self):
		if self.isempty():
			return None		
		else:
			poppednode = self.head
			self.head = self.head.next
			poppednode.next = None
			return poppednode.data

	def peek(self):		
		if self.isempty():
			return None		
		else:
			return self.head.data

	def display(self):
		iternode = self.head
		if self.isempty():
			print("Stack Underflow")
		else:
			while(iternode != None):
				print(iternode.data,"->",end = " ")
				iternode = iternode.next
			return

MyStack = Stack()
MyStack.push(11)
MyStack.push(22)
MyStack.push(54)
MyStack.push(34)
MyStack.display()
print("\nTop",MyStack.peek())
MyStack.pop()
MyStack.pop()
MyStack.display()
print("\nTop ", MyStack.peek())

Output

34 -> 54 -> 22 -> 11 -> 
Top 34
22 -> 11 -> 
Top  22

How to Search a Linked List in Another Linked List in Python?

The user-defined search_list() function can be used to search a linked list in another linked list.

def searchList(first, second):
	if not first and not second:
		return True
	if not first or not second:
		return False
	ptr1 = first
	ptr2 = second
	while ptr2:
		ptr2 = second
		while ptr1:
			if not ptr2:
				return False
			elif ptr1.value == ptr2.value:
				ptr1 = ptr1.next
				ptr2 = ptr2.next
			else:
				break
		if not ptr1:
			return True
		ptr1 = first
		second = second.next
	return False

node_a = Node(16)
node_a.next = Node(2)
node_a.next.next = Node(30)
node_a.next.next.next = Node(49)
node_b = Node(19)
node_b.next = Node(20)
node_b.next.next = Node(16)
node_b.next.next.next = Node(2)
node_b.next.next.next.next = Node(30)
node_b.next.next.next.next.next = Node(49)
if searchList(node_a, node_b):
	print("LIST FOUND")
else:
	print("LIST NOT FOUND")

Output

LIST FOUND