Question
Write a Program to insert elements in the double circular Linked List and Display them.
— Submitted By Ubaid Ahmad
What is a doubly circular Linked List?
A circular doubly linked list is a linear collection of nodes, which can be traversed from either side, i.e. from left to right and from right to left.
Everything in this is the same as a doubly-linked list, the only difference being the “next” field of the last node of the Linked List points to the head node and the “previous” element of the head field points to the last node.
Share code with your friends
Share on whatsapp
Share on facebook
Share on twitter
Share on telegram
Code
public class CircularDoublyLinkedList
{
class Node
{
int data;
Node next;
Node previous;
public Node(int data)
{
this.data = data;
}
}
// creating the head of the linkedlist. This represents the first node of the
// list.
public Node head = null;
public Node tail = null;
// adds node to the front of the list
public void insertFront(int data)
{
Node newNode = new Node(data); // creates a new node and fills it data attribute by the value passed.
// if the linkedlist is empty we make the head and tail equal to the node we
// created and make it circular
if (head == null)
{
newNode.next = newNode.previous = head;
head = tail = newNode;
return;
}
// if the list is not empty we add the node to the front of the list and make it
// the new head
newNode.next = head;
newNode.previous = tail;
head.previous = newNode;
tail.next = newNode;
head = newNode;
}
// adds a node to the end of the list
public void insertLast(int data)
{
Node newNode = new Node(data);
// if linkedlist is empty
if (head == null)
{
newNode.previous = newNode.next = newNode;
head = tail = newNode;
return;
}
// if the list is not empty we simply add the node at the end of the list
newNode.previous = tail;
newNode.next = head;
tail.next = newNode;
head.previous = newNode;
tail = newNode;
}
// printing the linkedlist
public void printList()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
if (temp == head)
{
break;
}
}
System.out.println();
}
// printing the linkedlist in reverse order
public void printListReverse()
{
Node temp = tail;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.previous;
if (temp == tail)
{
break;
}
}
System.out.println();
}
public static void main(String[] args)
{
// creating a SinglyLinkedList object names linkedList to represent the
// linkedlist
CircularDoublyLinkedList linkedList = new CircularDoublyLinkedList();
// inserting elements
linkedList.insertFront(6);
linkedList.insertFront(7);
linkedList.insertFront(8);
linkedList.insertFront(9);
linkedList.insertFront(10);
linkedList.insertLast(5);
linkedList.insertLast(4);
linkedList.insertLast(3);
linkedList.insertLast(2);
linkedList.insertLast(1);
// // prints the linkedlist
linkedList.printList();
linkedList.printListReverse();
}
}
Coding Store
Code Explanation
class Node
{
int data;
Node next;
Node previous;
public Node(int data)
{
this.data = data;
}
}
Since we are making a circular doubly linked list, we take a class called CircularDoublyLinkedList and make a nested class Node in it. This nested class will have three attributes
1. Node next: to store the location of the next node
2. Node previous: to store the location of the previous node
3. int data: to store the data of the current node.
In the node class, we make a constructor that will be used when we instantiate the objects.
public void insertFront(int data)
{
Node newNode = new Node(data); // creates a new node and fills it data attribute by the value passed.
// if the linkedlist is empty we make the head and tail equal to the node we
// created and make it circular
if (head == null)
{
newNode.next = newNode.previous = head;
head = tail = newNode;
return;
}
// if the list is not empty we add the node to the front of the list and make it
// the new head
newNode.next = head;
newNode.previous = tail;
head.previous = newNode;
tail.next = newNode;
head = newNode;
}
Now, in the DoublyLinkedList class, we make a function that will add the nodes at the front
insertFront(int):
The insertFront function accepts the data to be inserted as an argument and makes an object of class Node.
Now there are two scenarios-
The LinkedList is empty:
If it is empty, then we make a new node and have its “next” and “previous” field point to itself and then make it the head and tail node and exit from the function
The LinkedList has nodes:
If the list is not empty, make this node point to the head node. Also, we have the next field of the tail node and the previous field of the head node point to it. Then we make this node the head node
// adds a node to the end of the list
public void insertLast(int data)
{
Node newNode = new Node(data);
// if linkedlist is empty
if (head == null)
{
newNode.previous = newNode.next = newNode;
head = tail = newNode;
return;
}
// if the list is not empty we simply add the node at the end of the list
newNode.previous = tail;
newNode.next = head;
tail.next = newNode;
head.previous = newNode;
tail = newNode;
}
And one to insert at the end of the list.
insertLast(int):
The insertLast function accepts the data to be inserted as an argument and makes an object of class Node.
Now there are two scenarios-
The LinkedList is empty:
If it is empty, then we make a new node and have its “next” and “previous” field point to itself and then make it the head and tail node and exit from the function
The LinkedList has nodes:
If the list is not empty, make the tail “next” and the head “previous” fields point to this node and then have this node’s “next” field point to the head node and the “previous” field to the tail node. After this, we make this node the tail node.
// printing the linkedlist
public void printList()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
if (temp == head)
{
break;
}
}
System.out.println();
}
printList():
In this function, we just traverse till the end of the list and keep on printing the data field of each object till we reach the head node again.
// printing the linkedlist in reverse order
public void printListReverse()
{
Node temp = tail;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.previous;
if (temp == tail)
{
break;
}
}
System.out.println();
}
printListReverse():
In this function, we just traverse till the start of the list and keep on printing the data field of each object till we reach the tail node again.
public static void main(String[] args)
{
// creating a SinglyLinkedList object names linkedList to represent the
// linkedlist
CircularDoublyLinkedList linkedList = new CircularDoublyLinkedList();
// inserting elements
linkedList.insertFront(6);
linkedList.insertFront(7);
linkedList.insertFront(8);
linkedList.insertFront(9);
linkedList.insertFront(10);
linkedList.insertLast(5);
linkedList.insertLast(4);
linkedList.insertLast(3);
linkedList.insertLast(2);
linkedList.insertLast(1);
// // prints the linkedlist
linkedList.printList();
linkedList.printListReverse();
}
