A Doubly Circularly Linked List Makes It Easy
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 the previous and next pointer and the last node points to the first node by the next pointer and also the first node points to the last node by the previous pointer.
Following is the representation of a Circular doubly linked list node in C/C++:
C
struct node {
int data;
struct node* next;
struct node* prev;
};
Circular Doubly Linked LIst
Insertion in Circular Doubly Linked List:
1. Insertion at the end of the list or in an empty list:
A node(Say N) is inserted with data = 5. So, the previous pointer of N points to N and the next pointer of N also points to N. But now start pointer points to the first node of the list.
Insertion in an empty list
2. List initially contains some nodes, start points to the first node of the List:
A node(Say M) is inserted with data = 7, so the previous pointer of M points to the last node, the next pointer of M points to the first node and the last node's next pointer points to this M node, and first node's previous pointer points to this M node.
Insertion at the end of list
Below is the implementation of the above operations:
C++
void insertEnd( struct Node** start, int value)
{
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 ;
}
Node* last = (*start)->prev;
struct Node* new_node = new Node;
new_node->data = value;
new_node->next = *start;
(*start)->prev = new_node;
new_node->prev = last;
last->next = new_node;
}
Java
static void insertEnd( int value)
{
if (start == null ) {
Node new_node = new Node();
new_node.data = value;
new_node.next = new_node.prev = new_node;
start = new_node;
return ;
}
Node last = (start).prev;
Node new_node = new Node();
new_node.data = value;
new_node.next = start;
(start).prev = new_node;
new_node.prev = last;
last.next = new_node;
}
Python3
def insertEnd(value):
global start
if (start = = None ):
new_node = Node( 0 )
new_node.data = value
new_node. next = new_node.prev = new_node
start = new_node
return
last = (start).prev
new_node = Node( 0 )
new_node.data = value
new_node. next = start
(start).prev = new_node
new_node.prev = last
last. next = new_node
C#
static void insertEnd( int value)
{
Node new_node;
if (start == null ) {
new_node = new Node();
new_node.data = value;
new_node.next = new_node.prev = new_node;
start = new_node;
return ;
}
Node last = (start).prev;
new_node = new Node();
new_node.data = value;
new_node.next = start;
(start).prev = new_node;
new_node.prev = last;
last.next = new_node;
}
Javascript
function insertEnd(value)
{
if (start == null )
{
var new_node = new Node();
new_node.data = value;
new_node.next = new_node.prev = new_node;
start = new_node;
return ;
}
var last = (start).prev;
var new_node = new Node();
new_node.data = value;
new_node.next = start;
(start).prev = new_node;
new_node.prev = last;
last.next = new_node;
}
3. 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 the first node of the list, T previous pointer points to the last node of 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.
Insertion at the beginning of the list
Below is the implementation of the above operation:
C++
void insertBegin( struct Node** start, int value)
{
struct Node* last = (*start)->prev;
struct Node* new_node = new Node;
new_node->data = value;
new_node->next = *start;
new_node->prev = last;
last->next = (*start)->prev = new_node;
*start = new_node;
}
Java
static void insertBegin( int value)
{
Node last = (start).prev;
Node new_node = new Node();
new_node.data = value;
new_node.next = start;
new_node.prev = last;
last.next = (start).prev = new_node;
start = new_node;
}
Python3
def insertBegin(value):
global start
last = (start).prev
new_node = Node( 0 )
new_node.data = value
new_node. next = start
new_node.prev = last
last. next = (start).prev = new_node
start = new_node
C#
static void insertBegin( int value)
{
Node last = (start).prev;
Node new_node = new Node();
new_node.data = value;
new_node.next = start;
new_node.prev = last;
last.next = (start).prev = new_node;
start = new_node;
}
Javascript
function insertBegin(value) {
var last = start.prev;
var new_node = new Node();
new_node.data = value;
new_node.next = start;
new_node.prev = last;
last.next = start.prev = new_node;
start = new_node;
}
4. 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.
Insertion in between other nodes
Below is the implementation of the above operation:
C++
void insertAfter( struct Node** start, int value1,
int value2)
{
struct Node* new_node = new Node;
new_node->data = value1;
struct Node* temp = *start;
while (temp->data != value2)
temp = temp->next;
struct Node* next = temp->next;
temp->next = new_node;
new_node->prev = temp;
new_node->next = next;
next->prev = new_node;
}
Java
static void insertAfter( int value1, int value2)
{
Node new_node = new Node();
new_node.data = value1;
Node temp = start;
while (temp.data != value2)
temp = temp.next;
Node next = temp.next;
temp.next = new_node;
new_node.prev = temp;
new_node.next = next;
next.prev = new_node;
}
Python3
def insertAfter(value1, value2):
global start
new_node = Node( 0 )
new_node.data = value1
temp = start
while (temp.data ! = value2):
temp = temp. next
next = temp. next
temp. next = new_node
new_node.prev = temp
new_node. next = next
next .prev = new_node
C#
static void insertAfter( int value1, int value2)
{
Node new_node = new Node();
new_node.data = value1;
Node temp = start;
while (temp.data != value2)
temp = temp.next;
Node next = temp.next;
temp.next = new_node;
new_node.prev = temp;
new_node.next = next;
next.prev = new_node;
}
Javascript
<script>
function insertAfter(value1, value2)
{
var new_node = new Node();
new_node.data = value1;
var temp = start;
while (temp.data != value2)
temp = temp.next;
var next = temp.next;
temp.next = new_node;
new_node.prev = temp;
new_node.next = next;
next.prev = new_node;
}
</script>
Following is a complete program that uses all of the above methods to create a circular doubly linked list.
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
void insertEnd( struct Node** start, int value)
{
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 ;
}
Node* last = (*start)->prev;
struct Node* new_node = new Node;
new_node->data = value;
new_node->next = *start;
(*start)->prev = new_node;
new_node->prev = last;
last->next = new_node;
}
void insertBegin( struct Node** start, int value)
{
struct Node* last = (*start)->prev;
struct Node* new_node = new Node;
new_node->data = value;
new_node->next = *start;
new_node->prev = last;
last->next = (*start)->prev = new_node;
*start = new_node;
}
void insertAfter( struct Node** start, int value1,
int value2)
{
struct Node* new_node = new Node;
new_node->data = value1;
struct Node* temp = *start;
while (temp->data != value2)
temp = temp->next;
struct Node* next = temp->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);
}
int main()
{
struct Node* start = NULL;
insertEnd(&start, 5);
insertBegin(&start, 4);
insertEnd(&start, 7);
insertEnd(&start, 8);
insertAfter(&start, 6, 5);
printf ( "Created circular doubly linked list is: " );
display(start);
return 0;
}
Java
import java.util.*;
class GFG {
static Node start;
static class Node {
int data;
Node next;
Node prev;
};
static void insertEnd( int value)
{
if (start == null ) {
Node new_node = new Node();
new_node.data = value;
new_node.next = new_node.prev = new_node;
start = new_node;
return ;
}
Node last = (start).prev;
Node new_node = new Node();
new_node.data = value;
new_node.next = start;
(start).prev = new_node;
new_node.prev = last;
last.next = new_node;
}
static void insertBegin( int value)
{
Node last = (start).prev;
Node new_node = new Node();
new_node.data = value;
new_node.next = start;
new_node.prev = last;
last.next = (start).prev = new_node;
start = new_node;
}
static void insertAfter( int value1, int value2)
{
Node new_node = new Node();
new_node.data = value1;
Node temp = start;
while (temp.data != value2)
temp = temp.next;
Node next = temp.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);
}
public static void main(String[] args)
{
Node start = null ;
insertEnd( 5 );
insertBegin( 4 );
insertEnd( 7 );
insertEnd( 8 );
insertAfter( 6 , 5 );
System.out.printf(
"Created circular doubly linked list is: " );
display();
}
}
Python3
class Node:
def __init__( self , data):
self .data = data
self . next = None
self .prev = None
def insertEnd(value):
global start
if (start = = None ):
new_node = Node( 0 )
new_node.data = value
new_node. next = new_node.prev = new_node
start = new_node
return
last = (start).prev
new_node = Node( 0 )
new_node.data = value
new_node. next = start
(start).prev = new_node
new_node.prev = last
last. next = new_node
def insertBegin(value):
global start
last = (start).prev
new_node = Node( 0 )
new_node.data = value
new_node. next = start
new_node.prev = last
last. next = (start).prev = new_node
start = new_node
def insertAfter(value1, value2):
global start
new_node = Node( 0 )
new_node.data = value1
temp = start
while (temp.data ! = value2):
temp = temp. next
next = temp. 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)
if __name__ = = '__main__' :
global start
start = None
insertEnd( 5 )
insertBegin( 4 )
insertEnd( 7 )
insertEnd( 8 )
insertAfter( 6 , 5 )
print ( "Created circular doubly linked list is: " )
display()
C#
using System;
using System.Collections.Generic;
class GFG {
static Node start;
public class Node {
public int data;
public Node next;
public Node prev;
};
static void insertEnd( int value)
{
Node new_node;
if (start == null ) {
new_node = new Node();
new_node.data = value;
new_node.next = new_node.prev = new_node;
start = new_node;
return ;
}
Node last = (start).prev;
new_node = new Node();
new_node.data = value;
new_node.next = start;
(start).prev = new_node;
new_node.prev = last;
last.next = new_node;
}
static void insertBegin( int value)
{
Node last = (start).prev;
Node new_node = new Node();
new_node.data = value;
new_node.next = start;
new_node.prev = last;
last.next = (start).prev = new_node;
start = new_node;
}
static void insertAfter( int value1, int value2)
{
Node new_node = new Node();
new_node.data = value1;
Node temp = start;
while (temp.data != value2)
temp = temp.next;
Node next = temp.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);
}
public static void Main(String[] args)
{
Node start = null ;
insertEnd(5);
insertBegin(4);
insertEnd(7);
insertEnd(8);
insertAfter(6, 5);
Console.Write(
"Created circular doubly linked list is: " );
display();
}
}
Javascript
var start = null ;
class Node {
constructor() {
this .data = 0;
this .next = null ;
this .prev = null ;
}
}
function insertEnd(value) {
var new_node;
if (start == null ) {
new_node = new Node();
new_node.data = value;
new_node.next = new_node.prev = new_node;
start = new_node;
return ;
}
var last = start.prev;
new_node = new Node();
new_node.data = value;
new_node.next = start;
start.prev = new_node;
new_node.prev = last;
last.next = new_node;
}
function insertBegin(value) {
var last = start.prev;
var new_node = new Node();
new_node.data = value;
new_node.next = start;
new_node.prev = last;
last.next = start.prev = new_node;
start = new_node;
}
function insertAfter(value1, value2) {
var new_node = new Node();
new_node.data = value1;
var temp = start;
while (temp.data != value2) temp = temp.next;
var next = temp.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);
}
var start = null ;
insertEnd(5);
insertBegin(4);
insertEnd(7);
insertEnd(8);
insertAfter(6, 5);
document.write( "Created circular doubly linked list is: " );
display();
Output
Created circular doubly linked list is: Traversal in forward direction 4 5 6 7 8 Traversal in reverse direction 8 7 6 5 4
Time Complexity: O(N)
Auxiliary Space: O(1), As constant extra space is used.
Advantages of circular doubly linked list:
- The 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 the Fibonacci Heap.
Disadvantages of circular doubly linked list:
- It takes slightly extra memory in each node to accommodate the previous pointer.
- Lots of pointers are 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 song playlists in media player applications.
- Managing shopping carts 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 review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
joneswaidamight54.blogspot.com
Source: https://www.geeksforgeeks.org/doubly-circular-linked-list-set-1-introduction-and-insertion/
0 Response to "A Doubly Circularly Linked List Makes It Easy"
Post a Comment