Search an Element in Doubly Circular Linked List
Pre-requisite: Convert an Array to a Circular Doubly Linked List, Doubly Circular Linked List
Given a Doubly circular linked list. The task is to find the position of an element in the list.
Image Representation:
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Algorithm:
- Declare a temp pointer, and initialize it to head of the list.
- Iterate the loop until temp reaches start address (last node in the list, as it is in a circular fashion), check for the n element, whether present or not.
- If it is present, raise a flag, increment count and break the loop.
- At the last, as the last node is not visited yet check for the n element if present do step 3.
Below program illustrate the above approach:
C++
|
// C++ program to illustrate inserting a Node in
// a Circular Doubly Linked list in begging, end
// and middle
#include <bits/stdc++.h>
using namespace std;
// Structure of a Node
struct Node
{
int data;
struct Node *next;
struct Node *prev;
};
// Function to insert a node at the end
void insertNode(struct Node** start, int value)
{
// If the list is empty, create a single node
// circular and doubly list
if (*start == NULL)
{
struct Node* new_node = new Node;
new_node->data = value;
new_node->next = new_node->prev = new_node;
*start = new_node;
return;
}
// If list is not empty
/* Find last node */
Node *last = (*start)->prev;
// Create Node dynamically
struct Node* new_node = new Node;
new_node->data = value;
// Start is going to be next of new_node
new_node->next = *start;
// Make new node previous of start
(*start)->prev = new_node;
// Make last previous of new node
new_node->prev = last;
// Make new node next of old last
last->next = new_node;
}
// Function to display the
// circular doubly linked list
void displayList(struct Node* start)
{
struct Node *temp = start;
while (temp->next != start)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("%d ", temp->data);
}
// Function to search the particular element
// from the list
int searchList(struct Node* start, int search)
{
// Declare the temp variable
struct Node *temp = start;
// Declare other control
// variable for the searching
int count=0,flag=0,value;
// If start is NULL return -1
if(temp == NULL)
return -1;
else
{
// Move the temp pointer until,
// temp->next doesn't move
// start address (Circular Fashion)
while(temp->next != start)
{
// Increment count for location
count++;
// If it is found raise the
// flag and break the loop
if(temp->data == search)
{
flag = 1;
count--;
break;
}
// Increment temp pointer
temp = temp->next;
}
// Check whether last element in the
// list content the value if contain,
// raise a flag and increment count
if(temp->data == search)
{
count++;
flag = 1;
}
// If flag is true, then element
// found, else not
if(flag == 1)
cout<<"\n"<<search <<" found at location "<<
count<<endl;
else
cout<<"\n"<<search <<" not found"<<endl;
}
}
// Driver code
int main()
{
/* Start with the empty list */
struct Node* start = NULL;
// Insert 4. So linked list becomes 4->NULL
insertNode(&start, 4);
// Insert 5. So linked list becomes 4->5
insertNode(&start, 5);
// Insert 7. So linked list
// becomes 4->5->7
insertNode(&start, 7);
// Insert 8. So linked list
// becomes 4->5->7->8
insertNode(&start, 8);
// Insert 6. So linked list
// becomes 4->5->7->8->6
insertNode(&start, 6);
printf("Created circular doubly linked list is: ");
displayList(start);
searchList(start, 5);
return 0;
}
|
Java
|
// Java program to illustrate inserting
// a Node in a Circular Doubly Linked list
// in begging, end and middle
class GFG
{
// Structure of a Node
static class Node
{
int data;
Node next;
Node prev;
};
// Function to insert a node at the end
static Node insertNode(Node start, int value)
{
// If the list is empty, create a single node
// circular and doubly list
if (start == null)
{
Node new_node = new Node();
new_node.data = value;
new_node.next = new_node.prev = new_node;
start = new_node;
return new_node;
}
// If list is not empty
// Find last node /
Node last = (start).prev;
// Create Node dynamically
Node new_node = new Node();
new_node.data = value;
// Start is going to be next of new_node
new_node.next = start;
// Make new node previous of start
(start).prev = new_node;
// Make last previous of new node
new_node.prev = last;
// Make new node next of old last
last.next = new_node;
return start;
}
// Function to display the
// circular doubly linked list
static void displayList(Node start)
{
Node temp = start;
while (temp.next != start)
{
System.out.printf("%d ", temp.data);
temp = temp.next;
}
System.out.printf("%d ", temp.data);
}
// Function to search the particular element
// from the list
static int searchList(Node start, int search)
{
// Declare the temp variable
Node temp = start;
// Declare other control
// variable for the searching
int count = 0, flag = 0, value;
// If start is null return -1
if(temp == null)
return -1;
else
{
// Move the temp pointer until,
// temp.next doesn't move
// start address (Circular Fashion)
while(temp.next != start)
{
// Increment count for location
count++;
// If it is found raise the
// flag and break the loop
if(temp.data == search)
{
flag = 1;
count--;
break;
}
// Increment temp pointer
temp = temp.next;
}
// Check whether last element in the
// list content the value if contain,
// raise a flag and increment count
if(temp.data == search)
{
count++;
flag = 1;
}
// If flag is true, then element
// found, else not
if(flag == 1)
System.out.println("\n"+search +" found at location "+
count);
else
System.out.println("\n"+search +" not found");
}
return -1;
}
// Driver code
public static void main(String args[])
{
// Start with the empty list /
Node start = null;
// Insert 4. So linked list becomes 4.null
start= insertNode(start, 4);
// Insert 5. So linked list becomes 4.5
start= insertNode(start, 5);
// Insert 7. So linked list
// becomes 4.5.7
start= insertNode(start, 7);
// Insert 8. So linked list
// becomes 4.5.7.8
start= insertNode(start, 8);
// Insert 6. So linked list
// becomes 4.5.7.8.6
start= insertNode(start, 6);
System.out.printf("Created circular doubly linked list is: ");
displayList(start);
searchList(start, 5);
}
}
// This code is contributed by Arnab Kundu
|
Python3
|
# Python3 program to illustrate inserting a Node in
# a Circular Doubly Linked list in begging, end
# and middle
import math
# Structure of a Node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to insert a node at the end
def insertNode(start, value):
# If the list is empty, create a single node
# circular and doubly list
if (start == None) :
new_node = Node(value)
new_node.data = value
new_node.next = new_node
new_node.prev = new_node
start = new_node
return new_node
# If list is not empty
# Find last node */
last = start.prev
# Create Node dynamically
new_node = Node(value)
new_node.data = value
# Start is going to be next of new_node
new_node.next = start
# Make new node previous of start
(start).prev = new_node
# Make last previous of new node
new_node.prev = last
# Make new node next of old last
last.next = new_node
return start
# Function to display the
# circular doubly linked list
def displayList(start):
temp = start
while (temp.next != start):
print(temp.data, end = " ")
temp = temp.next
print(temp.data)
# Function to search the particular element
# from the list
def searchList(start, search):
# Declare the temp variable
temp = start
# Declare other control
# variable for the searching
count = 0
flag = 0
value = 0
# If start is None return -1
if(temp == None):
return -1
else:
# Move the temp pointer until,
# temp.next doesn't move
# start address (Circular Fashion)
while(temp.next != start):
# Increment count for location
count = count + 1
# If it is found raise the
# flag and break the loop
if(temp.data == search):
flag = 1
count = count - 1
break
# Increment temp pointer
temp = temp.next
# Check whether last element in the
# list content the value if contain,
# raise a flag and increment count
if(temp.data == search):
count = count + 1
flag = 1
# If flag is true, then element
# found, else not
if(flag == 1):
print(search,"found at location ", count)
else:
print(search, " not found")
return -1
# Driver code
if __name__=='__main__':
# Start with the empty list */
start = None
# Insert 4. So linked list becomes 4.None
start = insertNode(start, 4)
# Insert 5. So linked list becomes 4.5
start = insertNode(start, 5)
# Insert 7. So linked list
# becomes 4.5.7
start = insertNode(start, 7)
# Insert 8. So linked list
# becomes 4.5.7.8
start = insertNode(start, 8)
# Insert 6. So linked list
# becomes 4.5.7.8.6
start = insertNode(start, 6)
print("Created circular doubly linked list is: ",
end = "")
displayList(start)
searchList(start, 5)
# This article contributed by Srathore
|
C#
|
// C# Program to Reverse a List using Data Swapping
using System;
class GFG
{
// Structure of a Node
public class Node
{
public int data;
public Node next;
public Node prev;
};
// Function to insert a node at the end
static Node insertNode(Node start, int value)
{
// If the list is empty, create a single node
// circular and doubly list
Node new_node = new Node();
if (start == null)
{
new_node.data = value;
new_node.next = new_node.prev = new_node;
start = new_node;
return new_node;
}
// If list is not empty
// Find last node /
Node last = (start).prev;
// Create Node dynamically
new_node = new Node();
new_node.data = value;
// Start is going to be next of new_node
new_node.next = start;
// Make new node previous of start
(start).prev = new_node;
// Make last previous of new node
new_node.prev = last;
// Make new node next of old last
last.next = new_node;
return start;
}
// Function to display the
// circular doubly linked list
static void displayList(Node start)
{
Node temp = start;
while (temp.next != start)
{
Console.Write("{0} ", temp.data);
temp = temp.next;
}
Console.Write("{0} ", temp.data);
}
// Function to search the particular element
// from the list
static int searchList(Node start, int search)
{
// Declare the temp variable
Node temp = start;
// Declare other control
// variable for the searching
int count = 0, flag = 0, value;
// If start is null return -1
if(temp == null)
return -1;
else
{
// Move the temp pointer until,
// temp.next doesn't move
// start address (Circular Fashion)
while(temp.next != start)
{
// Increment count for location
count++;
// If it is found raise the
// flag and break the loop
if(temp.data == search)
{
flag = 1;
count--;
break;
}
// Increment temp pointer
temp = temp.next;
}
// Check whether last element in the
// list content the value if contain,
// raise a flag and increment count
if(temp.data == search)
{
count++;
flag = 1;
}
// If flag is true, then element
// found, else not
if(flag == 1)
Console.WriteLine("\n"+search +" found at location "+
count);
else
Console.WriteLine("\n"+search +" not found");
}
return -1;
}
// Driver code
public static void Main(String []args)
{
// Start with the empty list /
Node start = null;
// Insert 4. So linked list becomes 4.null
start= insertNode(start, 4);
// Insert 5. So linked list becomes 4.5
start= insertNode(start, 5);
// Insert 7. So linked list
// becomes 4.5.7
start= insertNode(start, 7);
// Insert 8. So linked list
// becomes 4.5.7.8
start= insertNode(start, 8);
// Insert 6. So linked list
// becomes 4.5.7.8.6
start= insertNode(start, 6);
Console.Write("Created circular doubly linked list is: ");
displayList(start);
searchList(start, 5);
}
}
// This code has been contributed by 29AjayKumar
|
Javascript
|
<script>
// JavaScript program to illustrate inserting
// a Node in a Circular Doubly Linked list
// in begging, end and middle
class Node
{
constructor()
{
this.data=0;
this.next=this.prev=null;
}
}
// Function to insert a node at the end
function insertNode(start,value)
{
// If the list is empty, create a single node
// circular and doubly list
if (start == null)
{
let new_node = new Node();
new_node.data = value;
new_node.next = new_node.prev = new_node;
start = new_node;
return new_node;
}
// If list is not empty
// Find last node /
let last = (start).prev;
// Create Node dynamically
let new_node = new Node();
new_node.data = value;
// Start is going to be next of new_node
new_node.next = start;
// Make new node previous of start
(start).prev = new_node;
// Make last previous of new node
new_node.prev = last;
// Make new node next of old last
last.next = new_node;
return start;
}
// Function to display the
// circular doubly linked list
function displayList(start)
{
let temp = start;
while (temp.next != start)
{
document.write(temp.data+" ");
temp = temp.next;
}
document.write(temp.data+" ");
}
// Function to search the particular element
// from the list
function searchList(start,search)
{
// Declare the temp variable
let temp = start;
// Declare other control
// variable for the searching
let count = 0, flag = 0, value;
// If start is null return -1
if(temp == null)
return -1;
else
{
// Move the temp pointer until,
// temp.next doesn't move
// start address (Circular Fashion)
while(temp.next != start)
{
// Increment count for location
count++;
// If it is found raise the
// flag and break the loop
if(temp.data == search)
{
flag = 1;
count--;
break;
}
// Increment temp pointer
temp = temp.next;
}
// Check whether last element in the
// list content the value if contain,
// raise a flag and increment count
if(temp.data == search)
{
count++;
flag = 1;
}
// If flag is true, then element
// found, else not
if(flag == 1)
document.write("<br>"+search +" found at location "+
count);
else
document.write("<br>"+search +" not found");
}
return -1;
}
// Driver code
// Start with the empty list /
let start = null;
// Insert 4. So linked list becomes 4.null
start= insertNode(start, 4);
// Insert 5. So linked list becomes 4.5
start= insertNode(start, 5);
// Insert 7. So linked list
// becomes 4.5.7
start= insertNode(start, 7);
// Insert 8. So linked list
// becomes 4.5.7.8
start= insertNode(start, 8);
// Insert 6. So linked list
// becomes 4.5.7.8.6
start= insertNode(start, 6);
document.write("Created circular doubly linked list is: ");
displayList(start);
searchList(start, 5);
// This code is contributed by avanitrachhadiya2155
</script>
|
Output:
Created circular doubly linked list is: 4 5 7 8 6
5 found at location 2
Time Complexity: As it uses linear search, so complexity is O(n).
Article Tags :
Advanced Data Structure
circular linked list
doubly linked list
Linked Lists
Searching Quiz
Practice Tags :
circular linked list
Read Full Article
Doubly Circular Linked List | Set 1 (Introduction and Insertion)
Prerequisite: Doubly Linked list, Circular Linked List
Circular Doubly Linked List has properties of both doubly linked list and circular linked list in which two consecutive elements are linked or connected by previous and next pointer and the last node points to first node by next pointer and also the first node points to last node by the previous pointer.
Following is representation of a Circular doubly linked list node in C/C++:
// Structure of the node struct node { int data; struct node *next; // Pointer to next node struct node *prev; // Pointer to previous node };Insertion in Circular Doubly Linked List
Insertion in Circular Doubly Linked List
-
Insertion at the end of list or in an empty list
- Empty List (start = NULL): A node(Say N) is inserted with data = 5, so previous pointer of N points to N and next pointer of N also points to N. But now start pointer points to the first node the list.
- List initially contains some nodes, start points to first node of the List: A node(Say M) is inserted with data = 7, so previous pointer of M points to last node, next pointer of M points to first node and last node’s next pointer points to this M node and first node’s previous pointer points to this M node.
C++
|
// Function to insert at the end
void insertEnd(struct Node** start, int value)
{
// If the list is empty, create a single node
// circular and doubly list
if (*start == NULL)
{
struct Node* new_node = new Node;
new_node->data = value;
new_node->next = new_node->prev = new_node;
*start = new_node;
return;
}
// If list is not empty
/* Find last node */
Node *last = (*start)->prev;
// Create Node dynamically
struct Node* new_node = new Node;
new_node->data = value;
// Start is going to be next of new_node
new_node->next = *start;
// Make new node previous of start
(*start)->prev = new_node;
// Make last previous of new node
new_node->prev = last;
// Make new node next of old last
last->next = new_node;
}
|
Java
|
// Function to insert at the end
static void insertEnd(int value)
{
// If the list is empty, create a single
// node circular and doubly list
if (start == null)
{
Node new_node = new Node();
new_node.data = value;
new_node.next = new_node.prev = new_node;
start = new_node;
return;
}
// If list is not empty
// Find last node
Node last = (start).prev;
// Create Node dynamically
Node new_node = new Node();
new_node.data = value;
// Start is going to be
// next of new_node
new_node.next = start;
// Make new node previous of start
(start).prev = new_node;
// Make last previous of new node
new_node.prev = last;
// Make new node next of old last
last.next = new_node;
}
// This code is contributed by rutvik_56
|
Python3
|
# Function to insert at the end
def insertEnd(value) :
global start
# If the list is empty, create a
# single node circular and doubly list
if (start == None) :
new_node = Node(0)
new_node.data = value
new_node.next = new_node.prev = new_node
start = new_node
return
# If list is not empty
# Find last node */
last = (start).prev
# Create Node dynamically
new_node = Node(0)
new_node.data = value
# Start is going to be next of new_node
new_node.next = start
# Make new node previous of start
(start).prev = new_node
# Make last previous of new node
new_node.prev = last
# Make new node next of old last
last.next = new_node
# This code is contributed by shivanisinghss2110
|
C#
|
// Function to insert at the end
static void insertEnd(int value)
{
Node new_node;
// If the list is empty, create a single node
// circular and doubly list
if (start == null)
{
new_node = new Node();
new_node.data = value;
new_node.next = new_node.prev = new_node;
start = new_node;
return;
}
// If list is not empty
/* Find last node */
Node last = (start).prev;
// Create Node dynamically
new_node = new Node();
new_node.data = value;
// Start is going to be next of new_node
new_node.next = start;
// Make new node previous of start
(start).prev = new_node;
// Make last previous of new node
new_node.prev = last;
// Make new node next of old last
last.next = new_node;
}
// This code is contributed by Pratham76
|
Javascript
|
<script>
// Function to insert at the end
function insertEnd(value)
{
// If the list is empty, create a single
// node circular and doubly list
if (start == null)
{
var new_node = new Node();
new_node.data = value;
new_node.next = new_node.prev = new_node;
start = new_node;
return;
}
// If list is not empty
// Find last node
var last = (start).prev;
// Create Node dynamically
var new_node = new Node();
new_node.data = value;
// Start is going to be
// next of new_node
new_node.next = start;
// Make new node previous of start
(start).prev = new_node;
// Make last previous of new node
new_node.prev = last;
// Make new node next of old last
last.next = new_node;
}
// This code contributed by aashish2995
</script>
|
- Insertion at the beginning of the list: To insert a node at the beginning of the list, create a node(Say T) with data = 5, T next pointer points to first node of the list, T previous pointer points to last node the list, last node’s next pointer points to this T node, first node’s previous pointer also points this T node and at last don’t forget to shift ‘Start’ pointer to this T node.
C++
|
// Function to insert Node at the beginning
// of the List,
void insertBegin(struct Node** start, int value)
{
// Pointer points to last Node
struct Node *last = (*start)->prev;
struct Node* new_node = new Node;
new_node->data = value; // Inserting the data
// setting up previous and next of new node
new_node->next = *start;
new_node->prev = last;
// Update next and previous pointers of start
// and last.
last->next = (*start)->prev = new_node;
// Update start pointer
*start = new_node;
}
|
Java
|
// Function to insert Node at the beginning
// of the List,
static void insertBegin(int value)
{
// Pointer points to last Node
Node last = (start).prev;
Node new_node = new Node();
new_node.data = value; // Inserting the data
// setting up previous and next of new node
new_node.next = start;
new_node.prev = last;
// Update next and previous pointers of start
// and last.
last.next = (start).prev = new_node;
// Update start pointer
start = new_node;
}
// this code is contributed by shivanisinghss2110
|
Python3
|
# Function to insert Node at the beginning
# of the List,
def insertBegin( value) :
global start
# Pointer points to last Node
last = (start).prev
new_node = Node(0)
new_node.data = value # Inserting the data
# setting up previous and
# next of new node
new_node.next = start
new_node.prev = last
# Update next and previous pointers
# of start and last.
last.next = (start).prev = new_node
# Update start pointer
start = new_node
# This code is contributed by shivanisinghss2110
|
C#
|
// Function to insert Node at the beginning
// of the List,
static void insertBegin(int value)
{
// Pointer points to last Node
Node last = (start).prev;
Node new_node = new Node();
new_node.data = value; // Inserting the data
// setting up previous and next of new node
new_node.next = start;
new_node.prev = last;
// Update next and previous pointers of start
// and last.
last.next = (start).prev = new_node;
// Update start pointer
start = new_node;
}
// This code is contributed by shivanisinghss2110
|
Javascript
|
// Function to insert Node at the beginning
// of the List,
function insertBegin(value) {
// Pointer points to last Node
var last = start.prev;
var new_node = new Node();
new_node.data = value; // Inserting the data
// setting up previous and next of new node
new_node.next = start;
new_node.prev = last;
// Update next and previous pointers of start
// and last.
last.next = start.prev = new_node;
// Update start pointer
start = new_node;
}
// This code is contributed by shivanisinghss2110
|
- Insertion in between the nodes of the list: To insert a node in between the list, two data values are required one after which new node will be inserted and another is the data of the new node.
C++
|
// Function to insert node with value as value1.
// The new node is inserted after the node with
// with value2
void insertAfter(struct Node** start, int value1,
int value2)
{
struct Node* new_node = new Node;
new_node->data = value1; // Inserting the data
// Find node having value2 and next node of it
struct Node *temp = *start;
while (temp->data != value2)
temp = temp->next;
struct Node *next = temp->next;
// insert new_node between temp and next.
temp->next = new_node;
new_node->prev = temp;
new_node->next = next;
next->prev = new_node;
}
|
Java
|
// Function to insert node with value as value1.
// The new node is inserted after the node with
// with value2
static void insertAfter(int value1,
int value2)
{
Node new_node = new Node();
new_node.data = value1; // Inserting the data
// Find node having value2 and next node of it
Node temp = start;
while (temp.data != value2)
temp = temp.next;
Node next = temp.next;
// insert new_node between temp and next.
temp.next = new_node;
new_node.prev = temp;
new_node.next = next;
next.prev = new_node;
}
// this code is contributed by shivanisinghss2110
|
Python3
|
# Function to insert node with value as value1.
# The new node is inserted after the node with
# with value2
def insertAfter(value1, value2) :
global start
new_node = Node(0)
new_node.data = value1 # Inserting the data
# Find node having value2 and
# next node of it
temp = start
while (temp.data != value2) :
temp = temp.next
next = temp.next
# insert new_node between temp and next.
temp.next = new_node
new_node.prev = temp
new_node.next = next
next.prev = new_node
# this code is contributed by shivanisinghss2110
|
C#
|
// Function to insert node with value as value1.
// The new node is inserted after the node with
// with value2
static void insertAfter(int value1, int value2)
{
Node new_node = new Node();
new_node.data = value1; // Inserting the data
// Find node having value2 and next node of it
Node temp = start;
while (temp.data != value2)
temp = temp.next;
Node next = temp.next;
// insert new_node between temp and next.
temp.next = new_node;
new_node.prev = temp;
new_node.next = next;
next.prev = new_node;
}
// this code is contributed by shivanisinghss2110
|
Javascript
|
<script>
// Function to insert node with value as value1.
// The new node is inserted after the node with
// with value2
function insertAfter(value1, value2)
{
var new_node = new Node();
// Inserting the data
new_node.data = value1;
// Find node having value2 and
// next node of it
var temp = start;
while (temp.data != value2)
temp = temp.next;
var next = temp.next;
// Insert new_node between temp and next.
temp.next = new_node;
new_node.prev = temp;
new_node.next = next;
next.prev = new_node;
}
// This code is contributed by shivanisinghss2110
</script>
|
Following is a complete program that uses all of the above methods to create a circular doubly linked list.
C++
|
// C++ program to illustrate inserting a Node in
// a Circular Doubly Linked list in begging, end
// and middle
#include <bits/stdc++.h>
using namespace std;
// Structure of a Node
struct Node
{
int data;
struct Node *next;
struct Node *prev;
};
// Function to insert at the end
void insertEnd(struct Node** start, int value)
{
// If the list is empty, create a single node
// circular and doubly list
if (*start == NULL)
{
struct Node* new_node = new Node;
new_node->data = value;
new_node->next = new_node->prev = new_node;
*start = new_node;
return;
}
// If list is not empty
/* Find last node */
Node *last = (*start)->prev;
// Create Node dynamically
struct Node* new_node = new Node;
new_node->data = value;
// Start is going to be next of new_node
new_node->next = *start;
// Make new node previous of start
(*start)->prev = new_node;
// Make last previous of new node
new_node->prev = last;
// Make new node next of old last
last->next = new_node;
}
// Function to insert Node at the beginning
// of the List,
void insertBegin(struct Node** start, int value)
{
// Pointer points to last Node
struct Node *last = (*start)->prev;
struct Node* new_node = new Node;
new_node->data = value; // Inserting the data
// setting up previous and next of new node
new_node->next = *start;
new_node->prev = last;
// Update next and previous pointers of start
// and last.
last->next = (*start)->prev = new_node;
// Update start pointer
*start = new_node;
}
// Function to insert node with value as value1.
// The new node is inserted after the node with
// with value2
void insertAfter(struct Node** start, int value1,
int value2)
{
struct Node* new_node = new Node;
new_node->data = value1; // Inserting the data
// Find node having value2 and next node of it
struct Node *temp = *start;
while (temp->data != value2)
temp = temp->next;
struct Node *next = temp->next;
// insert new_node between temp and next.
temp->next = new_node;
new_node->prev = temp;
new_node->next = next;
next->prev = new_node;
}
void display(struct Node* start)
{
struct Node *temp = start;
printf("\nTraversal in forward direction \n");
while (temp->next != start)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("%d ", temp->data);
printf("\nTraversal in reverse direction \n");
Node *last = start->prev;
temp = last;
while (temp->prev != last)
{
printf("%d ", temp->data);
temp = temp->prev;
}
printf("%d ", temp->data);
}
/* Driver program to test above functions*/
int main()
{
/* Start with the empty list */
struct Node* start = NULL;
// Insert 5. So linked list becomes 5->NULL
insertEnd(&start, 5);
// Insert 4 at the beginning. So linked
// list becomes 4->5
insertBegin(&start, 4);
// Insert 7 at the end. So linked list
// becomes 4->5->7
insertEnd(&start, 7);
// Insert 8 at the end. So linked list
// becomes 4->5->7->8
insertEnd(&start, 8);
// Insert 6, after 5. So linked list
// becomes 4->5->6->7->8
insertAfter(&start, 6, 5);
printf("Created circular doubly linked list is: ");
display(start);
return 0;
}
|
Java
|
// Java program to illustrate inserting a Node in
// a Circular Doubly Linked list in begging, end
// and middle
import java.util.*;
class GFG
{
static Node start;
// Structure of a Node
static class Node
{
int data;
Node next;
Node prev;
};
// Function to insert at the end
static void insertEnd(int value)
{
// If the list is empty, create a single node
// circular and doubly list
if (start == null)
{
Node new_node = new Node();
new_node.data = value;
new_node.next = new_node.prev = new_node;
start = new_node;
return;
}
// If list is not empty
/* Find last node */
Node last = (start).prev;
// Create Node dynamically
Node new_node = new Node();
new_node.data = value;
// Start is going to be next of new_node
new_node.next = start;
// Make new node previous of start
(start).prev = new_node;
// Make last previous of new node
new_node.prev = last;
// Make new node next of old last
last.next = new_node;
}
// Function to insert Node at the beginning
// of the List,
static void insertBegin(int value)
{
// Pointer points to last Node
Node last = (start).prev;
Node new_node = new Node();
new_node.data = value; // Inserting the data
// setting up previous and next of new node
new_node.next = start;
new_node.prev = last;
// Update next and previous pointers of start
// and last.
last.next = (start).prev = new_node;
// Update start pointer
start = new_node;
}
// Function to insert node with value as value1.
// The new node is inserted after the node with
// with value2
static void insertAfter(int value1,
int value2)
{
Node new_node = new Node();
new_node.data = value1; // Inserting the data
// Find node having value2 and next node of it
Node temp = start;
while (temp.data != value2)
temp = temp.next;
Node next = temp.next;
// insert new_node between temp and next.
temp.next = new_node;
new_node.prev = temp;
new_node.next = next;
next.prev = new_node;
}
static void display()
{
Node temp = start;
System.out.printf("\nTraversal in forward direction \n");
while (temp.next != start)
{
System.out.printf("%d ", temp.data);
temp = temp.next;
}
System.out.printf("%d ", temp.data);
System.out.printf("\nTraversal in reverse direction \n");
Node last = start.prev;
temp = last;
while (temp.prev != last)
{
System.out.printf("%d ", temp.data);
temp = temp.prev;
}
System.out.printf("%d ", temp.data);
}
/* Driver code*/
public static void main(String[] args)
{
/* Start with the empty list */
Node start = null;
// Insert 5. So linked list becomes 5.null
insertEnd(5);
// Insert 4 at the beginning. So linked
// list becomes 4.5
insertBegin(4);
// Insert 7 at the end. So linked list
// becomes 4.5.7
insertEnd(7);
// Insert 8 at the end. So linked list
// becomes 4.5.7.8
insertEnd(8);
// Insert 6, after 5. So linked list
// becomes 4.5.6.7.8
insertAfter(6, 5);
System.out.printf("Created circular doubly linked list is: ");
display();
}
}
// This code is contributed by Rajput-Ji
|
Python3
|
# Python3 program to illustrate inserting
# a Node in a Circular Doubly Linked list
# in begging, end and middle
start = None
# Structure of a Node
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
# Function to insert at the end
def insertEnd(value) :
global start
# If the list is empty, create a
# single node circular and doubly list
if (start == None) :
new_node = Node(0)
new_node.data = value
new_node.next = new_node.prev = new_node
start = new_node
return
# If list is not empty
# Find last node */
last = (start).prev
# Create Node dynamically
new_node = Node(0)
new_node.data = value
# Start is going to be next of new_node
new_node.next = start
# Make new node previous of start
(start).prev = new_node
# Make last previous of new node
new_node.prev = last
# Make new node next of old last
last.next = new_node
# Function to insert Node at the beginning
# of the List,
def insertBegin( value) :
global start
# Pointer points to last Node
last = (start).prev
new_node = Node(0)
new_node.data = value # Inserting the data
# setting up previous and
# next of new node
new_node.next = start
new_node.prev = last
# Update next and previous pointers
# of start and last.
last.next = (start).prev = new_node
# Update start pointer
start = new_node
# Function to insert node with value as value1.
# The new node is inserted after the node with
# with value2
def insertAfter(value1, value2) :
global start
new_node = Node(0)
new_node.data = value1 # Inserting the data
# Find node having value2 and
# next node of it
temp = start
while (temp.data != value2) :
temp = temp.next
next = temp.next
# insert new_node between temp and next.
temp.next = new_node
new_node.prev = temp
new_node.next = next
next.prev = new_node
def display() :
global start
temp = start
print ("Traversal in forward direction:")
while (temp.next != start) :
print (temp.data, end = " ")
temp = temp.next
print (temp.data)
print ("Traversal in reverse direction:")
last = start.prev
temp = last
while (temp.prev != last) :
print (temp.data, end = " ")
temp = temp.prev
print (temp.data)
# Driver Code
if __name__ == '__main__':
global start
# Start with the empty list
start = None
# Insert 5. So linked list becomes 5.None
insertEnd(5)
# Insert 4 at the beginning. So linked
# list becomes 4.5
insertBegin(4)
# Insert 7 at the end. So linked list
# becomes 4.5.7
insertEnd(7)
# Insert 8 at the end. So linked list
# becomes 4.5.7.8
insertEnd(8)
# Insert 6, after 5. So linked list
# becomes 4.5.6.7.8
insertAfter(6, 5)
print ("Created circular doubly linked list is: ")
display()
# This code is contributed by Arnab kundu
|
C#
|
// C# program to illustrate inserting a Node in
// a Circular Doubly Linked list in begging, end
// and middle
using System;
using System.Collections.Generic;
class GFG
{
static Node start;
// Structure of a Node
public class Node
{
public int data;
public Node next;
public Node prev;
};
// Function to insert at the end
static void insertEnd(int value)
{
Node new_node;
// If the list is empty, create a single node
// circular and doubly list
if (start == null)
{
new_node = new Node();
new_node.data = value;
new_node.next = new_node.prev = new_node;
start = new_node;
return;
}
// If list is not empty
/* Find last node */
Node last = (start).prev;
// Create Node dynamically
new_node = new Node();
new_node.data = value;
// Start is going to be next of new_node
new_node.next = start;
// Make new node previous of start
(start).prev = new_node;
// Make last previous of new node
new_node.prev = last;
// Make new node next of old last
last.next = new_node;
}
// Function to insert Node at the beginning
// of the List,
static void insertBegin(int value)
{
// Pointer points to last Node
Node last = (start).prev;
Node new_node = new Node();
new_node.data = value; // Inserting the data
// setting up previous and next of new node
new_node.next = start;
new_node.prev = last;
// Update next and previous pointers of start
// and last.
last.next = (start).prev = new_node;
// Update start pointer
start = new_node;
}
// Function to insert node with value as value1.
// The new node is inserted after the node with
// with value2
static void insertAfter(int value1, int value2)
{
Node new_node = new Node();
new_node.data = value1; // Inserting the data
// Find node having value2 and next node of it
Node temp = start;
while (temp.data != value2)
temp = temp.next;
Node next = temp.next;
// insert new_node between temp and next.
temp.next = new_node;
new_node.prev = temp;
new_node.next = next;
next.prev = new_node;
}
static void display()
{
Node temp = start;
Console.Write("\nTraversal in forward direction \n");
while (temp.next != start)
{
Console.Write("{0} ", temp.data);
temp = temp.next;
}
Console.Write("{0} ", temp.data);
Console.Write("\nTraversal in reverse direction \n");
Node last = start.prev;
temp = last;
while (temp.prev != last)
{
Console.Write("{0} ", temp.data);
temp = temp.prev;
}
Console.Write("{0} ", temp.data);
}
/* Driver code*/
public static void Main(String[] args)
{
/* Start with the empty list */
Node start = null;
// Insert 5. So linked list becomes 5.null
insertEnd(5);
// Insert 4 at the beginning. So linked
// list becomes 4.5
insertBegin(4);
// Insert 7 at the end. So linked list
// becomes 4.5.7
insertEnd(7);
// Insert 8 at the end. So linked list
// becomes 4.5.7.8
insertEnd(8);
// Insert 6, after 5. So linked list
// becomes 4.5.6.7.8
insertAfter(6, 5);
Console.Write("Created circular doubly linked list is: ");
display();
}
}
// This code is contributed by Rajput-Ji
|
Javascript
|
<script>
// JavaScript program to illustrate inserting a Node in
// a Circular Doubly Linked list in begging, end
// and middle
var start = null;
// Structure of a Node
class Node {
constructor() {
this.data = 0;
this.next = null;
this.prev = null;
}
}
// Function to insert at the end
function insertEnd(value) {
var new_node;
// If the list is empty, create a single node
// circular and doubly list
if (start == null) {
new_node = new Node();
new_node.data = value;
new_node.next = new_node.prev = new_node;
start = new_node;
return;
}
// If list is not empty
/* Find last node */
var last = start.prev;
// Create Node dynamically
new_node = new Node();
new_node.data = value;
// Start is going to be next of new_node
new_node.next = start;
// Make new node previous of start
start.prev = new_node;
// Make last previous of new node
new_node.prev = last;
// Make new node next of old last
last.next = new_node;
}
// Function to insert Node at the beginning
// of the List,
function insertBegin(value) {
// Pointer points to last Node
var last = start.prev;
var new_node = new Node();
new_node.data = value; // Inserting the data
// setting up previous and next of new node
new_node.next = start;
new_node.prev = last;
// Update next and previous pointers of start
// and last.
last.next = start.prev = new_node;
// Update start pointer
start = new_node;
}
// Function to insert node with value as value1.
// The new node is inserted after the node with
// with value2
function insertAfter(value1, value2) {
var new_node = new Node();
new_node.data = value1; // Inserting the data
// Find node having value2 and next node of it
var temp = start;
while (temp.data != value2) temp = temp.next;
var next = temp.next;
// insert new_node between temp and next.
temp.next = new_node;
new_node.prev = temp;
new_node.next = next;
next.prev = new_node;
}
function display() {
var temp = start;
document.write("<br>Traversal in forward direction <br>");
while (temp.next != start) {
document.write(temp.data + " ");
temp = temp.next;
}
document.write(temp.data);
document.write("<br>Traversal in reverse direction <br>");
var last = start.prev;
temp = last;
while (temp.prev != last) {
document.write(temp.data + " ");
temp = temp.prev;
}
document.write(temp.data);
}
/* Driver code*/
/* Start with the empty list */
var start = null;
// Insert 5. So linked list becomes 5.null
insertEnd(5);
// Insert 4 at the beginning. So linked
// list becomes 4.5
insertBegin(4);
// Insert 7 at the end. So linked list
// becomes 4.5.7
insertEnd(7);
// Insert 8 at the end. So linked list
// becomes 4.5.7.8
insertEnd(8);
// Insert 6, after 5. So linked list
// becomes 4.5.6.7.8
insertAfter(6, 5);
document.write("Created circular doubly linked list is: ");
display();
</script>
|
Output:
Created circular doubly linked list is: Traversal in forward direction 4 5 6 7 8 Traversal in reverse direction 8 7 6 5 4Following are the advantages and disadvantages of a circular doubly linked list:
Advantages:
- List can be traversed from both directions i.e. from head to tail or from tail to head.
- Jumping from head to tail or from tail to head is done in constant time O(1).
- Circular Doubly Linked Lists are used for the implementation of advanced data structures like Fibonacci Heap.
Disadvantages
- It takes slightly extra memory in each node to accommodate the previous pointer.
- Lots of pointers involved while implementing or doing operations on a list. So, pointers should be handled carefully otherwise data of the list may get lost.
Applications of Circular doubly linked list
- Managing songs playlist in media player applications.
- Managing shopping cart in online shopping.
This article is contributed by Akash Gupta. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to . See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Article Tags :
Linked List
doubly linked list
Practice Tags :
Linked List
Read Full Article
Circular Doubly Linked List
Data Structure Circular Doubly Linked List
Created: March-09, 2021 | Updated: June-17, 2021
A Circular Doubly Linked List is a combination of both the circular linked list and doubly linked list. Its two nodes are connected by both the previous and next pointer. The last node’s next pointer points to the first node and the first node’s previous pointer points to the last node. It can be traversed from both directions and jumping from tail to head or from head to tail. It is also used for the implementation of advanced data structures like Fibonacci Heap.
Circular Linked List
In this article, you will learn what circular linked list is and its types with implementation.
A circular linked list is a type of linked list in which the first and the last nodes are also connected to each other to form a circle.
There are basically two types of circular linked list:
1. Circular Singly Linked List
Here, the address of the last node consists of the address of the first node.
2. Circular Doubly Linked List
Here, in addition to the last node storing the address of the first node, the first node will also store the address of the last node.
Note: We will be using the singly circular linked list to represent the working of circular linked list.
Introduction to Singly Linked List
Singly Linked List is a variant of Linked List which allows only forward traversal of linked lists. This is a simple form, yet it is effective for several problems such as Big Integer calculations.
A singly linked list is made up of nodes where each node has two parts:
- The first part contains the actual data of the node
- The second part contains a link that points to the next node of the list that is the address of the next node.
The beginning of the node marked by a special pointer named START. The pointer points to the fist node of the list but the link part of the last node has no next node to point to.
The main difference from an array is:
- Elements are not stored in contiguous memory locations.
- Size of Linked List need not be known in advance. It can increase at runtime depending on number of elements dynamically without any overhead.
In Singly Linked List, only the pointer to the first node is stored. The other nodes are accessed one by one.
To get the address of ith node, we need to traverse all nodes before it because the address of ith node is stored with i-1th node and so on.