Which is better doubly linked list or circular linked list?

Types of Linked List

Before knowing about the types of a linked list, we should know what is linked list. So, to know about the linked list, click on the link given below:

Table of Contents Show

Types of Linked List
Difference between Singly linked list and Doubly linked list in Java
Types of Linked List - Singly linked, doubly linked and circular
Difference between Singly linked list and Doubly linked list
Doubly Circular Linked List | Set 1 (Introduction and Insertion)

Difference between Singly linked list and Doubly linked list in Java

Java 8Object Oriented ProgrammingProgramming

Both Singly linked list and Doubly linked list are the implementation of Linked list in which every element of singly-linked list contains some data and a link to the next element, which allows to keep the structure. On the other hand, every node in a doubly-linked list also contains a link to the previous node.

The following are the important differences between a Singly linked list and Doubly linked list.

Sr. No.	Key	Singly linked list	Doubly linked list
1	Complexity	In singly linked list the complexity of insertion and deletion at a known position is O(n)	In case od doubly linked list the complexity of insertion and deletion at a known position is O(1)
2	Internal implementation	In singly linked list implementation is such as where the node contains some data and a pointer to the next node in the list	While doubly linked list has some more complex implementation where the node contains some data and a pointer to the next as well as the previous node in the list
3	Order of elements	Singly linked list allows traversal elements only in one way.	Doubly linked list allows element two way traversal.
4	Usage	Singly linked list are generally used for implementation of stacks	On other hand doubly linked list can be used to implement stacks as well as heaps and binary trees.
5	Index performance	Singly linked list is preferred when we need to save memory and searching is not required as pointer of single index is stored.	If we need better performance while searching and memory is not a limitation in this case doubly linked list is more preferred.
6	Memory consumption	As singly linked list store pointer of only one node so consumes lesser memory.	On other hand Doubly linked list uses more memory per node(two pointers).

Types of Linked List - Singly linked, doubly linked and circular

In this tutorial, you will learn different types of linked list. Also, you will find implementation of linked list in C.

Before you learn about the type of the linked list, make sure you know about the LinkedList Data Structure.

There are three common types of Linked List.

Singly Linked List
Doubly Linked List
Circular Linked List

Difference between Singly linked list and Doubly linked list

Introduction to Singly linked list : A singly linked list is a set of nodes where each node has two fields ‘data’ and ‘link’. The ‘data’ field stores actual piece of information and ‘link’ field is used to point to next node. Basically the ‘link’ field stores the address of the next node.

Introduction to Doubly linked list : A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.

Singly linked list vs Doubly linked list

Singly linked list (SLL)	Doubly linked list (DLL)
SLL nodes contains 2 field -data field and next link field.	DLL nodes contains 3 fields -data field, a previous link field and a next link field.

In SLL, the traversal can be done using the next node link only. Thus traversal is possible in one direction only.	In DLL, the traversal can be done using the previous node link or the next node link. Thus traversal is possible in both directions (forward and backward).
The SLL occupies less memory than DLL as it has only 2 fields.	The DLL occupies more memory than SLL as it has 3 fields.
Complexity of insertion and deletion at a given position is O(n).	Complexity of insertion and deletion at a given position is O(1).

Article Tags :

Data Structures

Difference Between

Linked List

doubly linked list

Practice Tags :

Data Structures

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

// 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

// 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

// 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# 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 4

Following 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