Singly Linked List Program in Java
What is a Linked List?
A Linked List is a linear data structure. It is a collection of nodes such that each node points to the next node.
The size of a linked list isn't fixed as the nodes can be added or removed as and when required.
The nodes are created by allocating space from the heap memory, using the new keyword.
A singly linked list is one in which each node is only capable to point to the next node.
A doubly linked list is one in which each node is capable of pointing to the previous as well as the next node.
Basic Operations in a Linked List
(a) Insertion: We can insert a node in a linked list. A node can be inserted at the beginning, or at the end, or anywhere in-between the list.
(b) Deletion: We can delete a node in a linked list. Firstly, we search for the node to be deleted. If found, the deletion takes place and the linked list is readjusted. If not found, then the deletion operation is cancelled.
(c) Traversal: We can traverse a linked list, meaning that we can visit each node in the linked list and process them according to our requirement. Displaying all the nodes in a linked list is an example of linked list traversal.
(d) Searching: We can perform a search on the linked list. If the data is found, then the search operation becomes successful, otherwise unsuccessful.
Java Program to Implement Singly Linked List
import java.util.Scanner;
class Node{
int data;
Node next;
public Node(){
data = 0;
next = null;
}
public Node(int d){
data = d;
next = null;
}
}
class LinkedList{
private Node start;
public LinkedList(){
start = null;
}
public void insert(int d){
Node n = new Node(d);
Node s = null;
boolean status = false;
if(start == null)
start = n;
else if(d <= start.data){
n.next = start;
start = n;
}
else{
s = start;
Node ptr = start.next;
while(ptr != null){
if(d >= s.data && d <= ptr.data){
s.next = n;
n.next = ptr;
status = true;
break;
}
else{
s = ptr;
ptr = ptr.next;
}
}
if(status == false)
s.next = n;
}
}
public void traverse(){
if(start == null){
System.out.println("Empty linked list!");
return;
}
Node s = start;
while(s != null){
System.out.print(s.data + "-->");
s = s.next;
}
System.out.println("null");
}
public boolean delete(int d){
boolean status = false;
if(start == null)
return status;
else if(start.data == d){
start = start.next;
status = true;
}
else{
Node s = start;
Node ptr = start.next;
while(ptr != null){
if(ptr.data == d){
Node n = ptr.next;
s.next = n;
status = true;
break;
}
else{
s = ptr;
ptr = ptr.next;
}
}
}
return status;
}
public boolean search(int d){
if(start == null)
return false;
Node ptr = start;
while(ptr != null){
if(ptr.data == d)
return true;
else
ptr = ptr.next;
}
return false;
}
}
class SinglyLinkedList{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
LinkedList list = new LinkedList();
while(true){
System.out.println("1. Insert node");
System.out.println("2. Delete node");
System.out.println("3. Search nodes");
System.out.println("4. Traverse nodes");
System.out.print("Enter your choice: ");
int choice = Integer.parseInt(in.nextLine());
switch(choice){
case 1:
System.out.print("Data for the node: ");
int d = Integer.parseInt(in.nextLine());
list.insert(d);
break;
case 2:
System.out.print("Data to be deleted: ");
d = Integer.parseInt(in.nextLine());
if(list.delete(d))
System.out.println(d + " deleted!");
else
System.out.println(d + " not found!");
break;
case 3:
System.out.print("Data to be searched: ");
d = Integer.parseInt(in.nextLine());
if(list.search(d))
System.out.println(d + " is available!");
else
System.out.println(d + " is unavailable.");
break;
case 4:
list.traverse();
break;
default:
System.out.println("Bye!");
return;
}
}
}
}
Comments
Post a Comment