Circular linked list last node point to the first node of linked list. The single linked list last node point to null value which uses to identify the end of linked list. But, the circular linked list tail node point to the head node. A circularly linked list node looks exactly the same as a linear singly linked list.
Write a program to implement circular linked list. Once the item moved to tail, it overrides the head items.
Algorithm Explanation
 | Circular linked list uses two methods to identify header node. The header node can be identified by using the flag or any other identifier to differentiate between other nodes. |
| Circular linked list is same like singly linked list. |
| When the node add to the head, the head pointer need to more back one place to insert at beginning. |
| The last element points to the first element in the circular linked list. |
Source Code
package com.dsacode.DataStructre.linkedlist;
public class CircularLinkedList {
private Node start;
private int count;
private static class Node {
int data;
Node link;
public Node(int data) {
this.data = data;
}
@SuppressWarnings("unused")
public Node(int data, Node link) {
this.data = data;
this.link = link;
}
}
public void append(int x) {
count++;
Node temp = new Node(x);
if (start == null) {
start = temp;
} else {
Node tp = start;
while (tp.link != start) {
tp = tp.link;
}
tp.link = temp;
}
temp.link = start;
}
public void addBeg(int x) {
count++;
Node temp = new Node(x);
if (start == null) {
temp.link = temp;
} else {
Node tp = start;
while (tp.link != start) {
tp = tp.link;
}
tp.link = temp;
temp.link = start;
}
start = temp;
}
public void addAt(int pos, int x) {
Node temp, tp;
temp = new Node(x);
tp = start;
for (int i = 0; i < pos; i++) {
if (tp.link == start)
break;
tp = tp.link;
}
temp.link = tp.link;
tp.link = temp;
count++;
}
public void displayList() {
if (start == null)
System.out.println("List is empty..");
else {
Node temp = start;
while (temp.link != start) {
System.out.print( temp.data+"->");
temp = temp.link;
}
System.out.println(temp.data );
}
System.out.println();
}
public int deleteAt(int position) {
Node current = start;
Node previous = start;
for (int i = 0; i < position; i++) {
if (current.link == start)
break;
previous = current;
current = current.link;
}
if (position == 0)
deleteFirst();
else
previous.link = current.link;
count--;
return current.data;
}
public void deleteFirst() {
Node temp = start;
while (temp.link != start) {
temp = temp.link;
}
temp.link = start.link;
start = start.link;
count--;
}
public int getCount() {
return count;
}
public static void main(String args[]){
CircularLinkedList ccl=new CircularLinkedList();
System.out.println("Insert items in the circular linked list: 41, 25, 63, 84");
ccl.addBeg(41);
ccl.append(25);
ccl.append(63);
ccl.append(84);
ccl.displayList();
System.out.println("Insert item at 2nd position: 10");
ccl.addAt(1, 10);
ccl.displayList();
System.out.println("Insert item in the circular linked list: 53, 12");
ccl.append(53);
ccl.append(12);
ccl.displayList();
System.out.println("Delete the item in the position 1:"+ccl.deleteAt(1)+"\n"); //index starts from zero
System.out.println("Linked List items:");
ccl.displayList();
}
}
Output
Insert items in the circular linked list: 41, 25, 63, 84 41->25->63->84 Insert item at 2nd position: 10 41->25->10->63->84 Insert item in the circular linked list: 53, 12 41->25->10->63->84->53->12 Delete the item in the position 1:25 Linked List items: 41->10->63->84->53->12
Source Explanation
| Circular linked list iterate the elements from start node and tail is equal to start node. |
| Delete operation check current link node is equal to start node to delete the node |
| Add operation add the element to the beginning, particular position and add the end of linked list |
Real Applications
- Corners of a polygon
- Pool of buffers that are used and released in FIFO (“first in, first out”) order.
- Set of processes that should be time-shared in round-robin order.