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.
|
// 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 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
|
|
# 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
|
|
<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.
|
// 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 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
|
|
# 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
|
|
// 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.
|
// 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;
}
|
|
// 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
|
|
# 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
|
|
<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++ 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 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 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
|
|
<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.
Circular Doubly Linked List
Circular doubly linked list is a more complexed type of data structure in which a node contain pointers to its previous node as well as the next node. Circular doubly linked list doesn't contain NULL in any of the node. The last node of the list contains the address of the first node of the list. The first node of the list also contain address of the last node in its previous pointer.
A circular doubly linked list is shown in the following figure.
Due to the fact that a circular doubly linked list contains three parts in its structure therefore, it demands more space per node and more expensive basic operations. However, a circular doubly linked list provides easy manipulation of the pointers and the searching becomes twice as efficient.
Which of the following is false about the circular linked list?
9. Which of the following is false about a circular linked list? Explanation: Time complexity of inserting a new node at the head of the list is O(n) because you have to traverse through the list to find the tail node.
Which of the following points is are not true about linked list data structure when it is compared with Array?
6. Which of the following points is/are not true about Linked List data structure when it is compared with an array? ... This will take more time than arrays as arrays provide random access to its elements.
Circular Linked List
Circular Linked List is little more complicated linked data structure. In the circular linked list we can insert elements anywhere in the list whereas in the array we cannot insert element anywhere in the list because it is in the contiguous memory. In the circular linked list the previous element stores the address of the next element and the last element stores the address of the starting element. The elements points to each other in a circular way which forms a circular chain. The circular linked list has a dynamic size which means the memory can be allocated when it is required.
Application of Circular Linked List
- The real life application where the circular linked list is used is our Personal Computers, where multiple applications are running. All the running applications are kept in a circular linked list and the OS gives a fixed time slot to all for running. The Operating System keeps on iterating over the linked list until all the applications are completed.
- Another example can be Multiplayer games. All the Players are kept in a Circular Linked List and the pointer keeps on moving forward as a player's chance ends.
- Circular Linked List can also be used to create Circular Queue. In a Queue we have to keep two pointers, FRONT and REAR in memory all the time, where as in Circular Linked List, only one pointer is required.
Implementing Circular Linked List
Implementing a circular linked list is very easy and almost similar to linear linked list implementation, with the only difference being that, in circular linked list the last Node will have it's next point to the Head of the List. In Linear linked list the last Node simply holds NULL in it's next pointer.
So this will be oue Node class, as we have already studied in the lesson, it will be used to form the List.
class Node { public: int data; //pointer to the next node node* next; node() { data = 0; next = NULL; } node(int x) { data = x; next = NULL; } }Circular Linked List
Circular Linked List class will be almost same as the Linked List class that we studied in the previous lesson, with a few difference in the implementation of class methods.
class CircularLinkedList { public: node *head; //declaring the functions //function to add Node at front int addAtFront(node *n); //function to check whether Linked list is empty int isEmpty(); //function to add Node at the End of list int addAtEnd(node *n); //function to search a value node* search(int k); //function to delete any Node node* deleteNode(int x); CircularLinkedList() { head = NULL; } }Insertion at the Beginning
Steps to insert a Node at beginning :
- The first Node is the Head for any Linked List.
- When a new Linked List is instantiated, it just has the Head, which is Null.
- Else, the Head holds the pointer to the fisrt Node of the List.
- When we want to add any Node at the front, we must make the head point to it.
- And the Next pointer of the newly added Node, must point to the previous Head, whether it be NULL(in case of new List) or the pointer to the first Node of the List.
- The previous Head Node is now the second Node of Linked List, because the new Node is added at the front.
Insertion at the End
Steps to insert a Node at the end :
- If the Linked List is empty then we simply, add the new Node as the Head of the Linked List.
- If the Linked List is not empty then we find the last node, and make it' next to the new Node, and make the next of the Newly added Node point to the Head of the List.
Searching for an Element in the List
In searhing we do not have to do much, we just need to traverse like we did while getting the last node, in this case we will also compare the data of the Node. If we get the Node with the same data, we will return it, otherwise we will make our pointer point the next Node, and so on.
node* CircularLinkedList :: search(int x) { node *ptr = head; while(ptr != NULL && ptr->data != x) { //until we reach the end or we find a Node with data x, we keep moving ptr = ptr->next; } return ptr; }Deleting a Node from the List
Deleting a node can be done in many ways, like we first search the Node with data which we want to delete and then we delete it. In our approach, we will define a method which will take the data to be deleted as argument, will use the search method to locate it and will then remove the Node from the List.
To remove any Node from the list, we need to do the following :
- If the Node to be deleted is the first node, then simply set the Next pointer of the Head to point to the next element from the Node to be deleted. And update the next pointer of the Last Node as well.
- If the Node is in the middle somewhere, then find the Node before it, and make the Node before it point to the Node next to it.
- If the Node is at the end, then remove it and make the new last node point to the head.
- ← Prev
- Next →