Posted on by Kalkicode
Code Doubly linked list

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:

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:

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 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) {
tail = node;

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

tail = node;

}
}
}
//display element of Node
void display() {
struct Node *temp = head;
if (temp == NULL) {
} 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()
{

{

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

}
}

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;
}
};
public:
Node *tail;
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->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() {
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;
}
}

public Node tail;

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) {
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) {
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 {

}
}

public static void main(String[] args) {
//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;
}
}

public Node tail;

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

if (node == null) {

Console.Write("Memory overflow\n");
return;
}
if (head == null) {
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) {
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 {

}
}

public static void Main(String[] args) {
//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

def __init__(self) :
self.tail = None

def insert(self, value) :
node = Node(value)
if (node == None) :
print("Memory overflow\n")
return

if (self.head == None) :
self.tail = node
else :
node.prev = self.tail
self.tail.next = node
self.tail = node

def display(self) :
if (temp == None) :
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) :
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 :

def main() :
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

def initialize()
@tail = nil
end
def insert(value)
node = Node.new(value)
if (node == nil)
print("Memory overflow\n")
return
end
if (@head == nil)
@tail = node
else
node.prev = @tail
@tail.next = node
@tail = node
end
end
def display()
if (temp == nil)
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)
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
end
end
end
def main()
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;
}
}
public \$tail;

function __construct() {
\$this->tail = null;
}
public  function insert(\$value) {
\$node = new Node(\$value);
if (\$node == null) {
echo("Memory overflow\n");
return;
}
if (\$this->head == null) {
\$this->tail = \$node;
} else {
\$node->prev = \$this->tail;
\$this->tail->next = \$node;
\$this->tail = \$node;
}
}
public  function display() {
if (\$temp == null) {
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) {
while (\$fast != null && \$fast->next != null && \$fast->next->next != null) {
\$slow = \$slow->next;
\$fast = \$fast->next->next;
}
echo("\n Middle : ". \$slow->data ."\n");
} else {
}
}
}

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;
}
}

constructor() {
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.tail = node;
} else {
node.prev = this.tail;
this.tail.next = node;
this.tail = node;
}
}
display() {
var temp = this.head;
if (temp == null) {
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 {
}
}
}

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;
}
}
var head: Node? ;
var tail: Node? ;
init() {
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.tail = node;
} else {
node!.prev = self.tail;
self.tail!.next = node;
self.tail = node;
}
}
func display() {
var temp: Node? = self.head;
if (temp == nil) {
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 {
}
}
}
func main() {
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
``````

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.

Comment

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.

Categories
Relative Post