Find middle element in doubly linked list
Finding the middle element in a doubly linked list means to determine the node that is positioned exactly in the middle of the list. In a doubly linked list, each node has two pointers, one pointing to the previous node and the other pointing to the next node.
To find the middle element of a doubly linked list, you need to traverse the list by starting from the head node and moving towards the tail node. During this traversal, you need to keep two pointers, a slow pointer and a fast pointer.
The slow pointer moves one node at a time, whereas the fast pointer moves two nodes at a time. When the fast pointer reaches the end of the list, the slow pointer will be pointing to the middle node.
If the doubly linked list contains an even number of nodes, then there are two possible middle nodes. In this case, you can choose either of the middle nodes.
Program List
//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;
}
Output
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;
}
Output
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();
}
}
Output
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();
}
}
Output
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()
Output
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()
Output
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();
Output
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();
Output
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();
Output
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
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment