Find middle element in doubly linked list

The problem at hand involves finding the middle element of a doubly linked list. A doubly linked list is a data structure where each node holds a value and has pointers to both its previous and next nodes. The challenge is to determine an efficient method to locate the middle element within this linked list.

Problem Statement

In this problem implementation of a doubly linked list. The task is to find the middle element of the linked list.

Example

Suppose we have the following doubly linked list:

Linked List: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6

Middle : 3

Idea to Solve the Problem

To find the middle element of a linked list, we can use the "two-pointer" approach. We initialize two pointers, a slow pointer and a fast pointer. The slow pointer advances by one step while the fast pointer advances by two steps at a time. When the fast pointer reaches the end of the list, the slow pointer will be at the middle element.

Pseudocode

function middle_node():
    if head is not NULL:
        slow = head
        fast = head
        
        while fast is not NULL and fast.next is not NULL and fast.next.next is not NULL:
            slow = slow.next
            fast = fast.next.next
        
        print("Middle:", slow.data)
    else:
        print("Empty linked list")

Algorithm Explanation

1. Initialize two pointers, slow and fast, both pointing to the head of the linked list.
2. Start a loop that continues as long as fast is not NULL and both fast.next and fast.next.next are not NULL.
3. In each iteration of the loop, move the slow pointer one step forward and the fast pointer two steps forward.
4. When the loop ends, the slow pointer will be pointing to the middle element of the linked list.
5. If the linked list is empty, print "Empty linked list."

Program List

• C
• C++
• Java
• C#
• Python
• Ruby
• Php
• Node Js
• Swift 4

//C Program
//Find middle element in doubly linked list
#include <stdio.h>

#include <stdlib.h> //for malloc function

//create structure
struct Node {
  int data;
  struct Node *next;
  struct Node *prev;
};


//head and tail pointers
struct Node *head = NULL, *tail = NULL;

//insert Node element of end of linked list
void insert(int value) {

  //Create a dynamic Node
  struct Node *node = (struct Node *) malloc(sizeof(struct Node));
  if (node == NULL) {
    printf("Memory overflow\n");
  } else {
    //set data value
    node->data = value;
    node->next = NULL;
    node->prev = NULL;
    if (head == NULL) {
      head = node;
      tail = node;

    } else {
      node->prev = tail;
      tail->next = node;

      tail = node;

    }
  }
}
//display element of Node
void display() {
  struct Node *temp = head;
  if (temp == NULL) {
    printf("Empty linked list");
  } else {

    printf("\n Head to Tail Nodes : \n");
    //Traverse doubly linked list from front to rear
    while (temp != NULL) {
      //print Node value
      printf("%3d", temp->data);
      temp = temp->next;
    }
    printf("\n Tail to Head Nodes : \n");

    temp = tail;

    //Traverse doubly linked list from rear to front
    while (temp != NULL) {
      //print Node value
      printf("%3d", temp->data);
      temp = temp->prev;
    }
  }

}
///find mid node
void  middle_node()
{
  if(head!=NULL)

  {

    struct Node*slow=head,*fast=head;

    while(fast!=NULL && fast->next != NULL && fast->next->next != NULL)
    {
      slow = slow->next;
      fast = fast->next->next;
    }
    printf("\n Middle : %d\n",slow->data);


  }else
  {
    //when linked list is empty
    printf("Empty linked list");

  }
}

int main() {

  //Insert element of linked list
  insert(1);
  insert(2);
  insert(3);
  insert(4);
  insert(5);
  insert(6);
  //Display all node
  display();

  middle_node();

  insert(7);
  display();
  middle_node();
  printf("\n");
  return 0;
}

 Head to Tail Nodes : 
  1  2  3  4  5  6
 Tail to Head Nodes : 
  6  5  4  3  2  1
 Middle : 3

 Head to Tail Nodes : 
  1  2  3  4  5  6  7
 Tail to Head Nodes : 
  7  6  5  4  3  2  1
 Middle : 4

/*
 C++ Program
 Find middle element in doubly linked list
*/

#include<iostream>

using namespace std;
class Node {
  public:
    int data;
  Node *next;
  Node *prev;
  Node(int value) {
    this->data = value;
    this->next = NULL;
    this->prev = NULL;
  }
};
class LinkedList {
  public:
    Node *head;
  Node *tail;
  LinkedList() {
    this->head = NULL;
    this->tail = NULL;
  }
  void insert(int value) {
    Node *node = new Node(value);
    if (node == NULL) {
      cout << "Memory overflow\n";
      return;
    }
    if (this->head == NULL) {
      this->head = node;
      this->tail = node;
    } else {
      node->prev = this->tail;
      this->tail->next = node;
      this->tail = node;
    }
  }
  void display() {
    Node *temp = this->head;
    if (temp == NULL) {
      cout << "\nEmpty linked list\n";
      return;
    }
    cout << "\n Head to Tail Nodes : \n  ";
    while (temp != NULL) {
      cout << temp->data << "  ";
      temp = temp->next;
    }
    temp = this->tail;
    cout << "\n Tail to Head Nodes : \n  ";
    while (temp != NULL) {
      cout << temp->data << "  ";
      temp = temp->prev;
    }
  }
  void middle_node() {
    if (this->head != NULL) {
      Node *slow = this->head, *fast = this->head;
      while (fast != NULL && fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
      }
      cout << "\n Middle : " << slow->data << "\n";
    } else {
      cout << "Empty linked list";
    }
  }
};
int main() {
  LinkedList obj;
  obj.insert(1);
  obj.insert(2);
  obj.insert(3);
  obj.insert(4);
  obj.insert(5);
  obj.insert(6);
  obj.display();
  obj.middle_node();
  obj.insert(7);
  obj.display();
  obj.middle_node();
  return 0;
}

 Head to Tail Nodes : 
  1  2  3  4  5  6
 Tail to Head Nodes : 
  6  5  4  3  2  1
 Middle : 3

 Head to Tail Nodes : 
  1  2  3  4  5  6  7
 Tail to Head Nodes : 
  7  6  5  4  3  2  1
 Middle : 4

/*
  Java Program
  Find middle element in doubly linked list

*/
class Node {

  public int data;

  public Node next;

  public Node prev;

  public Node(int value) {
    //Setup initial values of linked list node
    this.data = value;
    this.next = null;
    this.prev = null;
  }
}
class LinkedList {

  public Node head;
  public Node tail;

  public LinkedList() {
    head = null;
    tail = null;
  }
  public void insert(int value) {
    Node node = new Node(value);

    if (node == null) {

      System.out.print("Memory overflow\n");
      return;
    }
    if (head == null) {
      head = node;
      tail = node;
    } else {
      //Add Node at the end of linked list
      node.prev = tail;
      tail.next = node;
      tail = node;
    }
  }



  public void display() {
    Node temp = head;
    if (temp == null) {
      System.out.print("\nEmpty linked list\n");
      return;
    }

    System.out.print("\n Head to Tail Nodes : \n  ");

    while (temp != null) {
      System.out.print(temp.data + "  ");
      temp = temp.next;
    }

    temp = tail;

    System.out.print("\n Tail to Head Nodes : \n  ");

    while (temp != null) {
      System.out.print(temp.data + "  ");
      temp = temp.prev;
    }

  }
  //Find out middle node 
  public void middle_node() {

    if (head != null) {
      Node slow = head, fast = head;

      while (fast != null && fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
      }

      System.out.print("\n Middle : " + slow.data+ "\n");
    } else {

      System.out.print("Empty linked list");
    }
  }




  public static void main(String[] args) {
    LinkedList obj = new LinkedList();
    //Insert element of linked list
    obj.insert(1);
    obj.insert(2);
    obj.insert(3);
    obj.insert(4);
    obj.insert(5);
    obj.insert(6);
    //Display all node
    obj.display();

    obj.middle_node();

    obj.insert(7);
    obj.display();
    obj.middle_node();
   
  }


}

 Head to Tail Nodes : 
  1  2  3  4  5  6
 Tail to Head Nodes : 
  6  5  4  3  2  1
 Middle : 3

 Head to Tail Nodes : 
  1  2  3  4  5  6  7
 Tail to Head Nodes : 
  7  6  5  4  3  2  1
 Middle : 4

/*
  C# Program
  Find middle element in doubly linked list

*/
using System;
public class Node {

	public int data;

	public Node next;

	public Node prev;

	public Node(int value) {
		//Setup initial values of linked list node
		this.data = value;
		this.next = null;
		this.prev = null;
	}
}
class LinkedList {

	public Node head;
	public Node tail;

	public LinkedList() {
		head = null;
		tail = null;
	}
	public void insert(int value) {
		Node node = new Node(value);

		if (node == null) {

			Console.Write("Memory overflow\n");
			return;
		}
		if (head == null) {
			head = node;
			tail = node;
		} else {
			//Add Node at the end of linked list
			node.prev = tail;
			tail.next = node;
			tail = node;
		}
	}



	public void display() {
		Node temp = head;
		if (temp == null) {
			Console.Write("\nEmpty linked list\n");
			return;
		}

		Console.Write("\n Head to Tail Nodes : \n  ");

		while (temp != null) {
			Console.Write(temp.data + "  ");
			temp = temp.next;
		}

		temp = tail;

		Console.Write("\n Tail to Head Nodes : \n  ");

		while (temp != null) {
			Console.Write(temp.data + "  ");
			temp = temp.prev;
		}

	}
	//Find out middle node 
	public void middle_node() {

		if (head != null) {
			Node slow = head, fast = head;

			while (fast != null && fast.next != null && fast.next.next != null) {
				slow = slow.next;
				fast = fast.next.next;
			}

			Console.Write("\n Middle : " + slow.data+ "\n");
		} else {

			Console.Write("Empty linked list");
		}
	}




	public static void Main(String[] args) {
		LinkedList obj = new LinkedList();
		//Insert element of linked list
		obj.insert(1);
		obj.insert(2);
		obj.insert(3);
		obj.insert(4);
		obj.insert(5);
		obj.insert(6);
		//Display all node
		obj.display();

		obj.middle_node();

		obj.insert(7);
		obj.display();
		obj.middle_node();

	}


}

 Head to Tail Nodes : 
  1  2  3  4  5  6
 Tail to Head Nodes : 
  6  5  4  3  2  1
 Middle : 3

 Head to Tail Nodes : 
  1  2  3  4  5  6  7
 Tail to Head Nodes : 
  7  6  5  4  3  2  1
 Middle : 4

# Python 3 Program
# Find middle element in doubly linked list

class Node :

  def __init__(self, value) :
    self.data = value
    self.next = None
    self.prev = None
  

class LinkedList :

  def __init__(self) :
    self.head = None
    self.tail = None
  
  def insert(self, value) :
    node = Node(value)
    if (node == None) :
      print("Memory overflow\n")
      return
    
    if (self.head == None) :
      self.head = node
      self.tail = node
    else :
      node.prev = self.tail
      self.tail.next = node
      self.tail = node
    
  
  def display(self) :
    temp = self.head
    if (temp == None) :
      print("\nEmpty linked list")
      return
    
    print("\n Head to Tail Nodes :  ")
    while (temp != None) :
      print(temp.data ,end="  ")
      temp = temp.next
    
    temp = self.tail
    print("\n Tail to Head Nodes :  ")
    while (temp != None) :
      print(temp.data ,end="  ")
      temp = temp.prev
    
  
  def middle_node(self) :
    if (self.head != None) :
      slow = self.head
      fast = self.head
      while (fast != None and fast.next != None and fast.next.next != None) :
        slow = slow.next
        fast = fast.next.next
      
      print("\n Middle : ", slow.data )
    else :
      print("Empty linked list")
    
  

def main() :
  obj = LinkedList()
  obj.insert(1)
  obj.insert(2)
  obj.insert(3)
  obj.insert(4)
  obj.insert(5)
  obj.insert(6)
  obj.display()
  obj.middle_node()
  obj.insert(7)
  obj.display()
  obj.middle_node()

if __name__ == "__main__":
  main()

 Head to Tail Nodes : 
  1  2  3  4  5  6
 Tail to Head Nodes : 
  6  5  4  3  2  1
 Middle : 3

 Head to Tail Nodes : 
  1  2  3  4  5  6  7
 Tail to Head Nodes : 
  7  6  5  4  3  2  1
 Middle : 4

# Ruby Program
# Find middle element in doubly linked list

class Node 
	attr_reader :data, :next, :prev
	attr_accessor :data, :next, :prev
	def initialize(value) 
		self.data = value
		self.next = nil
		self.prev = nil
	end
end

class LinkedList 
	attr_reader :head, :tail
	attr_accessor :head, :tail
	def initialize() 
		@head = nil
		@tail = nil
	end
	def insert(value) 
		node = Node.new(value)
		if (node == nil) 
			print("Memory overflow\n")
			return
		end
		if (@head == nil) 
			@head = node
			@tail = node
		else 
			node.prev = @tail
			@tail.next = node
			@tail = node
		end
	end
	def display() 
		temp = @head
		if (temp == nil) 
			print("\nEmpty linked list\n")
			return
		end
		print("\n Head to Tail Nodes  :\n  ")
		while (temp != nil) 
			print(temp.data ,"  ")
			temp = temp.next
		end
		temp = @tail
		print("\n Tail to Head Nodes  :\n  ")
		while (temp != nil) 
			print(temp.data ,"  ")
			temp = temp.prev
		end
	end
	def middle_node() 
		if (@head != nil) 
			slow = @head
			fast = @head
			while (fast != nil and fast.next != nil and fast.next.next != nil) 
				slow = slow.next
				fast = fast.next.next
			end
			print("\n Middle  : ", slow.data ,"\n")
		else 
			print("Empty linked list")
		end
	end
end
def main() 
	obj = LinkedList.new()
	obj.insert(1)
	obj.insert(2)
	obj.insert(3)
	obj.insert(4)
	obj.insert(5)
	obj.insert(6)
	obj.display()
	obj.middle_node()
	obj.insert(7)
	obj.display()
	obj.middle_node()
end


main()

 Head to Tail Nodes : 
  1  2  3  4  5  6
 Tail to Head Nodes : 
  6  5  4  3  2  1
 Middle : 3

 Head to Tail Nodes : 
  1  2  3  4  5  6  7
 Tail to Head Nodes : 
  7  6  5  4  3  2  1
 Middle : 4

<?Php 
/*
 Php Program
 Find middle element in doubly linked list
*/

class Node {
  public $data;
  public $next;
  public $prev;

  function __construct($value) {
    $this->data = $value;
    $this->next = null;
    $this->prev = null;
  }
}
class LinkedList {
  public $head;
  public $tail;

  function __construct() {
    $this->head = null;
    $this->tail = null;
  }
  public  function insert($value) {
    $node = new Node($value);
    if ($node == null) {
      echo("Memory overflow\n");
      return;
    }
    if ($this->head == null) {
      $this->head = $node;
      $this->tail = $node;
    } else {
      $node->prev = $this->tail;
      $this->tail->next = $node;
      $this->tail = $node;
    }
  }
  public  function display() {
    $temp = $this->head;
    if ($temp == null) {
      echo("\nEmpty linked list\n");
      return;
    }
    echo("\n Head to Tail Nodes : \n  ");
    while ($temp != null) {
      echo($temp->data ."  ");
      $temp = $temp->next;
    }
    $temp = $this->tail;
    echo("\n Tail to Head Nodes : \n  ");
    while ($temp != null) {
      echo($temp->data ."  ");
      $temp = $temp->prev;
    }
  }
  public  function middle_node() {
    if ($this->head != null) {
      $slow = $this->head;
      $fast = $this->head;
      while ($fast != null && $fast->next != null && $fast->next->next != null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
      }
      echo("\n Middle : ". $slow->data ."\n");
    } else {
      echo("Empty linked list");
    }
  }
}

function main() {
  $obj = new LinkedList();
  $obj->insert(1);
  $obj->insert(2);
  $obj->insert(3);
  $obj->insert(4);
  $obj->insert(5);
  $obj->insert(6);
  $obj->display();
  $obj->middle_node();
  $obj->insert(7);
  $obj->display();
  $obj->middle_node();
}
main();

 Head to Tail Nodes : 
  1  2  3  4  5  6
 Tail to Head Nodes : 
  6  5  4  3  2  1
 Middle : 3

 Head to Tail Nodes : 
  1  2  3  4  5  6  7
 Tail to Head Nodes : 
  7  6  5  4  3  2  1
 Middle : 4

/*
 Node Js Program
 Find middle element in doubly linked list
*/

class Node {

	constructor(value) {
		this.data = value;
		this.next = null;
		this.prev = null;
	}
}
class LinkedList {
	
	constructor() {
		this.head = null;
		this.tail = null;
	}
	insert(value) {
		var node = new Node(value);
		if (node == null) {
			process.stdout.write("Memory overflow\n");
			return;
		}
		if (this.head == null) {
			this.head = node;
			this.tail = node;
		} else {
			node.prev = this.tail;
			this.tail.next = node;
			this.tail = node;
		}
	}
	display() {
		var temp = this.head;
		if (temp == null) {
			process.stdout.write("\nEmpty linked list\n");
			return;
		}
		process.stdout.write("\n Head to Tail Nodes : \n  ");
		while (temp != null) {
			process.stdout.write(temp.data + "  ");
			temp = temp.next;
		}
		temp = this.tail;
		process.stdout.write("\n Tail to Head Nodes : \n  ");
		while (temp != null) {
			process.stdout.write(temp.data + "  ");
			temp = temp.prev;
		}
	}
	middle_node() {
		if (this.head != null) {
			var slow = this.head;
			var fast = this.head;
			while (fast != null && fast.next != null && fast.next.next != null) {
				slow = slow.next;
				fast = fast.next.next;
			}
			process.stdout.write("\n Middle : " + slow.data + "\n");
		} else {
			process.stdout.write("Empty linked list");
		}
	}
}

function main() {
	var obj = new LinkedList();
	obj.insert(1);
	obj.insert(2);
	obj.insert(3);
	obj.insert(4);
	obj.insert(5);
	obj.insert(6);
	obj.display();
	obj.middle_node();
	obj.insert(7);
	obj.display();
	obj.middle_node();
}

main();

 Head to Tail Nodes : 
  1  2  3  4  5  6
 Tail to Head Nodes : 
  6  5  4  3  2  1
 Middle : 3

 Head to Tail Nodes : 
  1  2  3  4  5  6  7
 Tail to Head Nodes : 
  7  6  5  4  3  2  1
 Middle : 4

/*
 Swift 4 Program
 Find middle element in doubly linked list
*/

class Node {
  var data: Int;
  var next: Node? ;
  var prev: Node? ;
  init(_ value: Int) {
    self.data = value;
    self.next = nil;
    self.prev = nil;
  }
}
class LinkedList {
  var head: Node? ;
  var tail: Node? ;
  init() {
    self.head = nil;
    self.tail = nil;
  }
  func insert(_ value: Int) {
    let node: Node? = Node(value);
    if (node == nil) {
      print("Memory overflow\n");
      return;
    }
    if (self.head == nil) {
      self.head = node;
      self.tail = node;
    } else {
      node!.prev = self.tail;
      self.tail!.next = node;
      self.tail = node;
    }
  }
  func display() {
    var temp: Node? = self.head;
    if (temp == nil) {
      print("\nEmpty linked list\n");
      return;
    }
    print("\n Head to Tail Nodes :  ");
    while (temp != nil) {
      print(temp!.data ,terminator:"  ");
      temp = temp!.next;
    }
    temp = self.tail;
    print("\n Tail to Head Nodes : ");
    while (temp != nil) {
      print(temp!.data ,terminator:"  ");
      temp = temp!.prev;
    }
  }
  func middle_node() {
    if (self.head != nil) {
      var slow: Node? = self.head;
      var fast = self.head;
      while (fast != nil && fast!.next != nil && fast!.next!.next != nil) {
        slow = slow!.next;
        fast = fast!.next!.next;
      }
      print("\n Middle : ", slow!.data ,"\n");
    } else {
      print("Empty linked list");
    }
  }
}
func main() {
  let obj: LinkedList = LinkedList();
  obj.insert(1);
  obj.insert(2);
  obj.insert(3);
  obj.insert(4);
  obj.insert(5);
  obj.insert(6);
  obj.display();
  obj.middle_node();
  obj.insert(7);
  obj.display();
  obj.middle_node();
}
main();

 Head to Tail Nodes : 
  1  2  3  4  5  6
 Tail to Head Nodes : 
  6  5  4  3  2  1
 Middle : 3

 Head to Tail Nodes : 
  1  2  3  4  5  6  7
 Tail to Head Nodes : 
  7  6  5  4  3  2  1
 Middle : 4

Time Complexity

The time complexity of finding the middle element in a doubly linked list using the two-pointer approach is O(n), where n is the number of nodes in the linked list. Both the slow and fast pointers traverse the list at most n/2 steps. Asymptotically, this is a linear time complexity.