class LL {
Node head;
private int size;
LL() { //constructor of class LL is created
this.size = 0;
}
class Node { //Node class of Class LL is created
String data; //String to store data
Node next; //variable next of Node type is created;
// i.e to store address of next node
Node(String data) { //Constructor of Class Node is created;
this.data = data;
this.next = null; //when a node is created,
// its next will be null at starting
size++;
}
}
//method to add first element of list
public void addFirst(String data) {
Node newNode = new Node(data); //object of class Node is created
//and constructor is called
if (head == null) { //corner case
head = newNode;
return;
}
newNode.next = head; //newNode.next is point toward head
head = newNode; // now newNode become head
}
//Method to add last element of list
public void addLast(String data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node currNode = head; //traversing the list using currNode;
//Head should never be transvered;
while (currNode.next != null) {
currNode = currNode.next;
}
currNode.next = newNode;
}
//Method to delete first element of given list
public void deleteFirst() {
if (head == null) {
System.out.println("List is empty");
return;
}
size--;
head = head.next;
}
//Method to delete last element of list
public void deleteLast() {
if (head == null) { //corner case 1
System.out.println("The list is empty");
}
size--;
if (head.next == null) { //corner case 2
head = null;
return;
}
Node secondLast = head;
Node lastNode = head.next;
while (lastNode.next != null) {
lastNode = lastNode.next;
secondLast = secondLast.next;
}
secondLast.next = null;
}
//Method to get size of the list
public int getSize() {
return size;
}
//Method to print the list
public void printList() {
if (head == null) {
System.out.println("List is empty");
return;
}
Node currNode = head;
while (currNode != null) {
System.out.print(currNode.data + " -> ");
currNode = currNode.next;
}
System.out.println("NULL");
}
//Method to reverse a linklist
public void reverseIterate() {
if (head == null || head.next == null) {
return;
}
Node prevNode = head;
Node currNode = head.next;
while (currNode != null) {
Node nextNode = currNode.next;
currNode.next = prevNode;
//Updating the nodes
prevNode = currNode;
currNode = nextNode;
}
head.next = null;
head = prevNode;
}
//recursive method to reverse the linklist
public Node reverseRecursive(Node head) {
if (head == null || head.next == null) {
return head;
}
Node newHead = reverseRecursive(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
public static void main(String args[]) {
LL list = new LL(); //object of class LL is created i.e list
list.addFirst("a"); //first element is added
list.printList();
list.addFirst("is"); // second element is added
list.printList();
list.addLast("list"); //Third element is added
list.printList();
list.addFirst("This"); //Fourth element is added
list.printList();
// list.deleteFirst(); //first element is removed
// list.printList();
// list.deleteLast(); //last element is removed
// list.printList();
System.out.println(list.getSize()); //size method was called
// list.reverseIterate();
// list.printList();
list.head = list.reverseRecursive(list.head);
list.printList();
}
}
