Python: Finding Middle Element in Linked List

1. Introduction

The linked list, being a foundational data structure, offers a dynamic way to store data where elements, termed as nodes, are connected sequentially. Each node holds its data and a link to the next node. However, unlike arrays, obtaining a middle element is not direct due to the absence of indices. In this blog post, we will explore a method to find the middle element of a linked list using Python.

2. Program Overview

The program will entail:

1. Defining a Node class to represent elements of the linked list.

2. Creating a LinkedList class with methods to:

- append data to the list's end.

- find_middle to locate and return the middle element.

To find the middle efficiently, we will use the slow and fast pointer technique. Both pointers start at the head. For every single move of the slow pointer, the fast pointer moves two steps. When the fast pointer reaches the end, the slow pointer is in the middle.

3. Code Program

class Node:
    def __init__(self, data):
        """Initialize the node with data and no reference to the next node."""
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        """Initialize the linked list with a head set to None."""
        self.head = None

    def append(self, data):
        """Add a new node with the given data at the end of the list."""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def find_middle(self):
        """Return the middle element of the linked list."""
        if not self.head:
            return "Linked List is empty."

        slow_pointer = self.head
        fast_pointer = self.head

        while fast_pointer and fast_pointer.next:
            slow_pointer = slow_pointer.next
            fast_pointer = fast_pointer.next.next

        return slow_pointer.data


# Sample Interaction
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.append(4)
llist.append(5)
print("middle element",llist.find_middle())

llist.append(6)
print("middle element",llist.find_middle())

Output:

middle element 3
middle element 4

4. Step By Step Explanation

1. The Node class acts as a blueprint for every element in the linked list. Each node has data and a reference to the next node, initially set to None.

2. The LinkedList class offers two main methods: append to add data to the list and find_middle to locate the middle element.

3. In find_middle, two pointers, slow_pointer and fast_pointer, both start at the head. For every one step of slow_pointer, the fast_pointer takes two. By the time fast_pointer gets to the end, slow_pointer reaches the middle.

4. If the number of elements is even, the second middle element is returned. For example, for a list with elements [1,2,3,4], the middle element returned is 3.