Find the Middle element of Linked List in Python

By Ashutosh Srivastava

In this tutorial, we will learn how to find the middle element of a linked list in Python.

Linked is a linear data structure. Each element consist of two items first being the data and the second being the reference to the next node item. The first node of the linked list is called as the head node. As compared to arrays linked lists are the better option for performing operations such as insertion and deletion, whereas arrays are good for accessing random elements of the arrays. These were the few things you needed to know before beginning with the linked list. In this tutorial, we are going to learn how to find the middle element of linked list in O(n).

Approaches to find the middle element of a Linked List:

  • Counting the number of elements in the linked list and then dividing by 2 to locate the middle element. This is what is known as the naive solution.
  • A better and effective way is to initialize two-variables and increase one of them by 1 and others by 2. So by the time, the latter one’s points to the null the other would have been at the center/middle.

The code to the second approach is given below but I highly recommend to try the approach first on your IDE first before looking at the code below.

Python program to find the middle element of a Linked List

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

class Linked_List:
    def __init__(self):
        self.head=None
        self.root=None
    
    def print(self):
        temp=self.root
        while(temp):
            print(temp.data)
            temp=temp.next
    
    def push(self,data):
        new=Node(data)
        if(self.head==None):
            self.head=new
            self.root=new
        else:
            self.head.next=new
            self.head=new

    def middle(self):
        i1=i2=self.root
        if(i1 is not None):
            while(i1 is not None and i1.next is not None):
                i1=i1.next.next
                i2=i2.next
            print("Middle is: ",i2.data)


if __name__=="__main__":
    llist=Linked_List()
    llist.push(1)
    llist.push(2)
    llist.push(3)
    llist.push(4)
    llist.push(5)
    llist.push(6)
    llist.push(7)
    llist.push(8)
    llist.push(9)
    llist.push(10)
    llist.middle()
Output
Middle is: 6

The class Node above is to initialize the node objects. Approach 2 is implemented in the function middle() of the Linked_List class. You can also use user input using the input() method. Instead of giving the inputs by yourself in the push method. list is the object of class Linked_List.

The code complexity for this approach is O(n), where n is the number of elements in the linked list.

[Note: In case of even elements in the list the later of middle 2 elements is called the middle. You can consider this to be a world convention.]

Leave a Reply