Circular LinkedList Operations
No node can have null in circular linked list.
class CircularSinglyLinkedList {
private static Node head;
private static void create(int[] data) {
// if data is empty early return
if(data.length == 0) {
return;
}
// create first node
head = new Node(data[0], null);
// point next as self
head.setNext(head);
Node last = head;
// add node 2 to n
for(int i = 1; i < data.length; i++) {
Node newNode = new Node(data[i], head);
last.setNext(newNode);
last = newNode;
}
}
private static void display() {
if(head == null) {
return;
}
Node current = head;
do {
System.out.print(" " + current.getData());
current = current.getNext();
} while(current != head);
}
private static void displayRecursive(Node current, boolean flag) {
if(current != head || flag) {
flag = false;
System.out.print(" " + current.getData());
displayRecursive(current.getNext(), false);
}
}
private static void insertFirst(int data) {
Node newNode = new Node(data, head);
// if no previous data
if(head == null) {
head = newNode;
head.setNext(head);
return;
}
// point last node to new node
Node last = head;
while(last.getNext() != head) {
last = last.getNext();
}
last.setNext(newNode);
// point head to new Node
head = newNode;
}
private static void insertLast(int data) {
Node newNode = new Node(data, head);
// if No list availale
if(head == null) {
head = newNode;
head.setNext(head);
return;
}
// point last to last Node
Node last = head;
while(last.getNext() != head) {
last = last.getNext();
}
last.setNext(newNode);
}
private static void insertAfter(int data, int pos) {
// insert at head
if(pos == 0) {
insertFirst(data);
return;
}
// point current to pos
Node current = head;
for(int i = 1; i < pos && current.getNext() != head; i++) {
current = current.getNext();
}
Node newNode = new Node(data, head);
if(current.getNext() != head) {
// insert in middle
newNode.setNext(current.getNext());
}
current.setNext(newNode);
}
private static int deleteFirst() {
// if no nodes, return -1
if(head == null) {
return -1;
}
// point last node
Node last = head;
while(last.getNext() != head) {
last = last.getNext();
}
int x = head.getData();
// if there was only 1 Node
if(head == last) {
head = null;
} else {
// set new head
head = head.getNext();
// set new last.next
last.setNext(head);
}
return x;
}
private static int deleteLast() {
// if no nodes, return -1
if(head == null) {
return -1;
}
// point last node
Node last = head;
Node previous = head;
while(last.getNext() != head) {
previous = last;
last = last.getNext();
}
int x = last.getData();
// if there was only 1 Node
if(previous == last) {
head = null;
} else {
// set new head
previous.setNext(last.getNext());
}
return x;
}
private static int deleteAt(int pos) {
// if no nodes
if(head == null) {
return -1;
} else if(pos <= 1) {
return deleteFirst();
} else {
// delete middle or last element
Node current = head;
// point current to (pos - 1)th Node
for(int i = 1; i < pos - 1 && current.getNext() != head; i++) {
current = current.getNext();
}
// pos is out of range
if(current.getNext() == head) {
return -1;
}
int x = current.getNext().getData();
current.setNext(current.getNext().getNext());
return x;
}
}
public static void main(String[] args) {
int[] data = new int[] {3,5,7,10,25,8,32};
System.out.println("Create list");
create(data);
display();
System.out.println("\nDisplay list using recursive method");
displayRecursive(head, true);
System.out.println("\nInsert first");
insertFirst(2);
display();
System.out.println("\nInsert after 0th position");
insertAfter(/*data=*/1, /*pos=*/0);
display();
System.out.println("\nInsert last");
insertLast(33);
display();
System.out.println("\nInsert after 34th position");
insertAfter(/*data=*/34, /*pos=*/34);
display();
System.out.println("\nDelete first : " + deleteFirst());
System.out.println("Delete 1st node : " + deleteAt(/*pos=*/1));
System.out.println("Delete 3rd node : " + deleteAt(/*pos=*/3));
System.out.println("Delete last : " + deleteLast());
System.out.println("Delete 34rth node : " + deleteAt(/*pos=*/34));
display();
}
private static class Node {
private int data;
private Node next;
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
private void setData(int data) {
this.data = data;
}
private void setNext(Node next) {
this.next = next;
}
private int getData() {
return data;
}
private Node getNext() {
return next;
}
}
}
Output
Create list
3 5 7 10 25 8 32
Display list using recursive method
3 5 7 10 25 8 32
Insert first
2 3 5 7 10 25 8 32
Insert after 0th position
1 2 3 5 7 10 25 8 32
Insert last
1 2 3 5 7 10 25 8 32 33
Insert after 34th position
1 2 3 5 7 10 25 8 32 33 34
Delete first : 1
Delete 1st node : 2
Delete 3rd node : 7
Delete last : 34
Delete 34rth node : -1
3 5 10 25 8 32 33
Comments
Post a Comment