Singly Linked List - Java

• Insert node in the beginning of the linked list
• Insert node in the end of the linked list
• Insert a node after a given node
• Insert a node at a given position
• Given a ListNode, print all elements it hold
• Given a ListNode head, find out length of linked list
• Delete a node from a linked list at a given position
• Delete the first node from the list
• Delete the last node from the list
• Search an element in the list
• Reverse a Singly Linked List

public class SinglyLinkedList {
//It contains a static inner class ListNode
private static class ListNode {
//This class will have two fields
//One will hold data, lets say integer
//Other will hold type of ListNode class, that is, it will have a reference of its own.
//other one will point to next node in the list.
private int data;
private ListNode next;

//Create a constructor which will initialize the new node
public ListNode (int data) {
this.data = data;
this.next = null;
}
}

    //Insert element in the beginning of the linked list
public ListNode insertBeginning(ListNode head, int data) {
ListNode newNode = new ListNode(data);
if (head == null) {
return newNode;
}
newNode.next = head;
head = newNode;
//This head will be new head, having new node at beginning
return head;
}

//Insert element in the end of the linked list
public ListNode InserEnd(ListNode head, int data) {
ListNode newNode = new ListNode(data);
if(head == null) {
return newNode;
}
ListNode current = head;
while(null != current.next) {
current = current.next;
}
current.next = newNode;
return head;
}

//Insert a node after a given node
public void insertAfter(ListNode previous, int data) {
if (previous == null) {
System.out.println("Given previous node cannot be null.");
return;
}
ListNode newNode = new ListNode(data);
newNode.next = previous.next;
previous.next = newNode;
}

//Insert a node at a given position
public ListNode insertAtPosition(ListNode head, int data, int position) {
//Perform boundary checks
int size = length(head);
if (position > size + 1 || position <1) {
System.out.println("Invalid position");
return head;
}
ListNode newNode = new ListNode(data);
if(position == 1) {
newNode.next = head;
return newNode;
} else {
ListNode previous = head;
int count = 1;
while(count < position - 1) {
previous = previous.next;
count++;
}
ListNode current = previous.next;
newNode.next = current;
previous.next = newNode;
return head;
}
}

//Given a ListNode, print all elements it hold
public void display(ListNode head) {
if (head == null) {
return;
}
ListNode current = head;
//loop each element till end of the list
//last node points to null
while (current != null) {
//print current elements data
System.out.print(current.data + " > ");
//move to next element
current = current.next;
}
//Here current will be null
System.out.print(current);
}

    //Given a ListNode head, find out length of linked list
public int length(ListNode head) {
if (head == null) {
return 0;
}
// Create a count variable to hold length
int count = 0;
//loop each element and increment the count till list ends
ListNode current = head;
while(current != null) {
count++;
//move to next node
current = current.next;
}
return count;
}

//Delete a node from a linked list at a given position
public ListNode deletePosition(ListNode head, int position) {
int size = length(head);
if(position > size || position < 1) {
System.out.println("Invalid position");
return head;
}
if (position == 1) {
ListNode temp = head;
head = head.next;
temp.next = null;
return temp;
} else {
ListNode previous = head;
int count = 1;
while (count < position - 1) {
previous = previous.next;
count++;
}
ListNode current = previous.next;
previous.next = current.next;
current.next = null;
return current; 
}
}

//Delete first node from the list
public ListNode deleteFirst(ListNode head) {
if(head == null) {
return null;
}
ListNode temp = head;
head = head.next;
System.out.println("Deleted Element : " + temp.data);
temp = null;
return head;
}

//Delete last node from the list
public ListNode deleteLast(ListNode head) {
if(head == null) {
return head;
}
ListNode last = head;
ListNode previousToLast = null;
while(last.next != null) {
previousToLast = last;
last = last.next;
}
System.out.println("Deleted Element : " + last.data);
previousToLast.next = null;
return head;
}

//Search an element in the list
public boolean find(ListNode head, int searchKey) {
if (head == null) {
return false;
}
ListNode current = head;
while (current != null) {
if(current.data == searchKey) {
return true;
}
current = current.next;
}
return false;
}

//Reverse a Singly Linked List
public ListNode reverse(ListNode head) {
if (head == null) {
return head;
}
ListNode current = head;
ListNode previous = null;
ListNode next = null;
while(current != null) {
next = current.next;
current.next = previous;
previous = current;
current = next;
}
return previous;
}

public static void main(String[] args) {
//Lets create a Linked List
//1 > 2 > 3 > 4 > null
//1 as head node of linked list

ListNode head = new ListNode(10);
ListNode second = new ListNode(2);
ListNode third = new ListNode(43);
ListNode fourth = new ListNode(4);

//Attach them together to form a list
head.next = second;
second.next = third;
third.next = fourth;

System.out.println("Display all Elements : ");
SinglyLinkedList singlylinkedlist = new SinglyLinkedList();
singlylinkedlist.display(head);
System.out.println("\n");

System.out.print("Length of Linked List : " + singlylinkedlist.length(head));
System.out.println("\n");

System.out.println("Element inserted in Beginning : ");
ListNode newHead = singlylinkedlist.insertBeginning(head, 33);
singlylinkedlist.display(newHead);
System.out.println("\n");

System.out.println("Element inserted in End : ");
ListNode newHead1 = singlylinkedlist.InserEnd(head, 12);
singlylinkedlist.display(newHead1);
System.out.println("\n");

System.out.println("Insert an Element after a particulr position");
singlylinkedlist.insertAfter(head, 11);
singlylinkedlist.display(head);
System.out.println("\n");

System.out.println("Insert an Element at a particulr position");
singlylinkedlist.insertAtPosition(head, 22, 4);
singlylinkedlist.display(head);
System.out.println("\n");

System.out.println("Delete Element in the particulr position");
ListNode newHead2 = singlylinkedlist.deletePosition(head, 5);
System.out.println("Deleted Element : " + newHead2.data);
System.out.println("Elements after node is deleted : " );
singlylinkedlist.display(head);
System.out.println("\n");

System.out.println("Delete First Element");
head = singlylinkedlist.deleteFirst(head);
System.out.println("Elements after First Element deleted : ");
singlylinkedlist.display(head); 
System.out.println("\n");

System.out.println("Delete Last Element");
head = singlylinkedlist.deleteLast(head);
System.out.println("Elements after Last Element deleted : ");
singlylinkedlist.display(head); 
System.out.println("\n");

System.out.println("Searching an element : ");
if(singlylinkedlist.find(head,  11)) {
System.out.println("Search Key found!!");
} else {
System.out.println("Search key not found");
}
System.out.println();

System.out.println("Reverse the Linked List : ");
ListNode reverseList = singlylinkedlist.reverse(head);
singlylinkedlist.display(reverseList);
System.out.println("\n");
}
}