Doubly LinkedList Operations
Need to run and correct few errors in output
import java.util.*;
import java.lang.*;
import java.io.*;
class SinglyLinkedList {
private static Node head;
private static Node last;
private static void create(int[] data) {
// create first Node
head = new Node(null, data[0], null);
// if only single element
if(data.length == 1) {
return;
}
Node last = head;
for(int i = 1; i < data.length; i++) {
Node newNode = new Node(last, data[i], null);
last.setNext(newNode);
// reset last node
last = newNode;
}
SinglyLinkedList.last = last;
}
private static void display() {
if(head == null) {
System.out.println("No nodes to print in linkedlist");
return;
}
Node current = head;
while(current != null) {
System.out.print(" " + current.data);
// move next node
current = current.getNext();
}
}
private static void displayRecursive(Node head) {
if(head == null) {
return;
}
System.out.print(" " + head.getData());
displayRecursive(head.getNext());
}
private static int count() {
if(head == null) {
return 0;
}
Node current = head;
int counter = 0;
while(current != null) {
counter++;
// move next node
current = current.getNext();
}
return counter;
}
private static int countRecursive(Node head) {
if(head == null) {
return 0;
}
return 1 + countRecursive(head.getNext());
}
private static int sum() {
if(head == null) {
return 0;
}
Node current = head;
int sum = 0;
while(current != null) {
sum += current.getData();
// move next node
current = current.getNext();
}
return sum;
}
private static int sumRecursive(Node head) {
if(head == null) {
return 0;
}
return head.getData() + sumRecursive(head.getNext());
}
private static int max() {
if(head == null) {
return 0;
}
Node current = head;
int max = Integer.MIN_VALUE;
while(current != null) {
if(current.getData() > max) {
max = current.getData();
}
// move next node
current = current.getNext();
}
return max;
}
private static int maxRecursive(Node head) {
if(head == null) {
return Integer.MIN_VALUE;
}
int max = maxRecursive(head.getNext());
return max > head.getData() ? max : head.getData();
}
private static int min() {
if(head == null) {
return 0;
}
Node current = head;
int min = Integer.MAX_VALUE;
while(current != null) {
if(current.getData() < min) {
min = current.getData();
}
// move next node
current = current.getNext();
}
return min;
}
private static int minRecursive(Node head) {
if(head == null) {
return Integer.MAX_VALUE;
}
int min = minRecursive(head.getNext());
return min < head.getData() ? min : head.getData();
}
private static boolean search(int key) {
if(head == null) {
return false;
}
Node left = head;
Node right = last;
while(left != right) {
if(left.getData() == key || right.getData() == key) {
return true;
}
// move next node
left = left.getNext();
right = right.getPrev();
}
return false;
}
private static void insertAtFirst(int data) {
Node newNode = new Node(null, data, head);
head.setPrev(newNode);
head = newNode;
}
private static void insertAtLast(int data) {
Node newNode = new Node(last, data, null);
if(head == null) {
head = newNode;
return;
}
last.setNext(newNode);
last = newNode;
}
private static void insertAfter(int data, int position) {
if(head == null) {
head = new Node(null, data, null);;
} else if(position == 0) {
// insert before head
insertAtFirst(data);
} else {
Node current = head;
// If position is 0 or 1 then node will be inserted after 1st node
for(int i = 1; i < position && current.getNext() != null; i++) {
current = current.getNext();
}
// set data and newNode's prev to current node
Node newNode = new Node(current, data, null);
// set newNode's next to next node
newNode.setNext(current.getNext());
if(current.getNext() != null) {
newNode.getNext().setPrev(newNode);
}
current.setNext(newNode);
}
}
private static void insertInSortedList(int data) {
Node newNode = new Node(null, data, null);
if(head == null) {
// return new node if list is empty
head = newNode;
} else if(head.getData() >= data) {
// add to head if new element is smaller than head
newNode.setNext(head);
head.setPrev(newNode);
head = newNode;
} else {
//In a loop, find the appropriate node after which the input node is to be inserted.
Node current = head;
while(current.getNext() != null && current.getNext().getData() < data) {
current = current.getNext();
}
newNode.setPrev(current);
newNode.setNext(current.getNext());
newNode.getPrev().setNext(newNode);
if(newNode.getNext() != null) {
newNode.getNext().setPrev(newNode);
}
}
}
private static int deleteAt(int position) {
// check list empty and validate input index
if(head == null || position <= 0 || position > count()) {
return -1;
}
Node current = head;
for(int i = 1; i < position; i++) {
current = current.getNext();
}
int x = current.getData();
// delete first node
if(current == head) {
if(head.getNext() == null) {
// only node in the list
head = null;
} else {
// More node following first node
head = head.getNext();
head.setPrev(null);
}
} else {
if(current.getNext() != null) {
// step for middle node
current.getNext().setPrev(current.getPrev());
}
// delete last node
current.getPrev().setNext(current.getNext());
}
return x;
}
// Assuming list sorted in accending order
private static boolean isSorted() {
// detect early return | return true if no node or single node
if(head == null || head.getNext() == null) {
return true;
}
Node current = head.getNext();
while(current != null) {
// return false if previous element is greater than following element
if(current.getPrev().getData() > current.getData()) {
return false;
}
current = current.getNext();
}
return true;
}
private static void removeDuplicates() {
// early return
if(head == null || head.getNext() == null) {
return;
}
// reaching here means we have atleast 2 nodes
Node current = head.getNext();
while(current != null) {
if(current.getPrev().getData() == current.getData()) {
current.getPrev().setNext(current.getNext());
if(current.getNext() != null) {
current.getNext().setPrev(current.getPrev());
}
}
current = current.getNext();
}
}
private static void reverse() {
Node temp = head;
head = last;
last = head;
}
private static Node concat(Node first, Node second) {
if(first == null) {
return second;
}
if(second == null) {
return first;
}
Node current = first;
while(current.getNext() != null) {
current = current.getNext();
}
current.setNext(second);
return first;
}
private static Node mergeSortedList(Node first, Node second) {
if(first == null) {
return second;
}
if(second == null) {
return first;
}
Node sorted;
if(first.getData() < second.getData()) {
sorted = first;
first = first.getNext();
} else {
sorted = second;
second = second.getNext();
}
Node temp = sorted;
while(first.getNext() != null && second.getNext() != null) {
if(first.getData() < second.getData()) {
temp.setNext(first);
first = first.getNext();
} else {
temp.setNext(second);
second = second.getNext();
}
temp = temp.getNext();
}
if(first.getNext() != null) {
temp.setNext(first);
}
if(second.getNext() != null) {
temp.setNext(second);
}
return sorted;
}
private static boolean isLoop(Node list) {
Node slow, fast;
slow = fast = list;
do {
slow = slow.getNext();
fast = fast.getNext();
fast = fast != null ? fast.getNext() : fast;
} while(slow != null && fast != null && slow != fast);
return slow == fast;
}
public static void main (String[] args) {
int[] data = new int[] {3,5,7,10,25,8,32};
System.out.println("Display list");
create(data);
display();
// System.out.println("\nDisplay list recursive method");
// displayRecursive(head);
// System.out.println("\nTotal number of nodes : " + count());
// System.out.println("Total number of nodes : " + countRecursive(head));
// System.out.println("Sum of nodes : " + sum());
// System.out.println("Sum of nodes : " + sumRecursive(head));
// System.out.println("Max element : " + max());
// System.out.println("Max element : " + maxRecursive(head));
// System.out.println("Min element : " + min());
// System.out.println("Min element : " + minRecursive(head));
// int key = 32;
// System.out.println(key + " found : " + search(key));
// key = 100;
// System.out.println(key + " found : " + search(key));
// System.out.println("Insert 2");
// insertAtFirst(2);
// display();
// System.out.println("\nInsert 33 at last");
// insertAtLast(33);
// display();
// System.out.println("\nInsert 1 after 0th node");
// insertAfter(/*data=*/1, /*pos=*/0);
// display();
// System.out.println("\nInsert 4 after 3rd node");
// insertAfter(4, 4);
// display();
// System.out.println("\nInsert 100 after 100th node");
// insertAfter(100, 100);
// display()
// System.out.println("\nIs sorted : " + isSorted());
System.out.println("\nCreate and display sorted list");
head = null;
for(int d : data) {
insertInSortedList(d);
}
display();
System.out.println("\nIs sorted : " + isSorted());
System.out.println("\nDeleted position 0 : " + deleteAt(0));
System.out.println("Deleted position 1 : " + deleteAt(1));
System.out.println("Deleted position 2 : " + deleteAt(2));
System.out.println("Deleted position 20 : " + deleteAt(20));
display();
System.out.println("\nDuplicate the list");
for(int d : data) {
insertInSortedList(d);
}
insertInSortedList(32);
insertInSortedList(32);
insertInSortedList(32);
insertInSortedList(32);
insertInSortedList(32);
display();
System.out.println("\nRemove duplicates.");
removeDuplicates();
display();
//System.out.println("\nReverse list.");
//reverse();
//display();
System.out.println("\nConcat list.");
Node temp = head;
create(data);
head = concat(temp, head);
display();
System.out.println("\nMerging 2 sorted list.");
head = null;
for(int d : data) {
insertInSortedList(d);
}
temp = head;
head = null;
data = new int[] {4,5,3,6,2,7,8,9,3};
for(int d : data) {
insertInSortedList(d);
}
head = mergeSortedList(temp, head);
display();
System.out.println("\nIs loop? " + isLoop(head));
// Create loop
Node temp1 = head.getNext();
Node temp2 = head.getNext().getNext().getNext().getNext().getNext().getNext().getNext()
.getNext().getNext().getNext().getNext().getNext().getNext().getNext().getNext();
temp2.setNext(temp1);
System.out.println("\nIs loop? " + isLoop(head));
}
private static class Node {
private Node prev;
private int data;
private Node next;
private Node() {}
public Node(Node prev, int data, Node next) {
this.prev = prev;
this.data = data;
this.next = next;
}
// Setters and getters methods
public Node getPrev() {
return prev;
}
public void setPrev(Node prev) {
this.prev = prev;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
}
Comments
Post a Comment