Linked list is data Structure which contain linear collection of data elements as Node in such way that every node refer to next node in List.Here in java let us create class node which contain integer data and reference to the next node in Link list.
This is class Node which is in file Node.java
public class Node
{
protected int data;
protected Node link;
// Constructor to class Node with initially refer to null and set data to 0 by default
public Node()
{
link = null;
data = 0;
}
// Constructor to class Node which has both data and reference to next node
public Node(int d,Node n)
{
data = d;
link = n;
}
// Function that set link to next Node (which refer to next node
public void setLink(Node n)
{
link = n;
}
// Function which assign integer data to current Node
public void setData(int d)
{
data = d;
}
/* Function to get link to next node */
public Node getLink()
{
return link;
}
/* Function to get data from current Node */
public int getData()
{
return data;
}
}
Class LinkedList in which methods involved in it. Linkedlist.java file
import java.util.Scanner;
public class Linkedlist
{
protected Node start;
protected Node end ;
public int size ;
public Scanner sc;
/* Constructor */
public Linkedlist()
{
start = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return start == null;
}
/* Function to get size of list */
public int getSize()
{
return size;
}
/* Function to insert an element at begining */
public void insertAtStart(int val)
{
Node nptr = new Node(val, null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.setLink(start);
start = nptr;
}
}
/* Function to insert an element at end */
public void insertAtEnd(int val)
{
Node nptr = new Node(val,null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
end.setLink(nptr);
end = nptr;
}
}
/* Function to insert an element at position */
public void insertAtPos(int val , int pos)
{
Node nptr = new Node(val, null);
Node ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size; i++)
{
if (i == pos)
{
Node tmp = ptr.getLink() ;
ptr.setLink(nptr);
nptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size++ ;
}
/* Function to delete an element at position */
public void deleteAtPos(int pos)
{
if (pos == 1)
{
start = start.getLink();
size--;
return ;
}
if (pos == size)
{
Node s = start;
Node t = start;
while (s != end)
{
t = s;
s = s.getLink();
}
end = t;
end.setLink(null);
size --;
return;
}
Node ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size - 1; i++)
{
if (i == pos)
{
Node tmp = ptr.getLink();
tmp = tmp.getLink();
ptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size-- ;
}
public void reverse(){
Linkedlist newList = new Linkedlist();
Node node = start;
for(int i=0; i newList.insertAtStart(node.getData());
node = node.getLink();
}
//Update the start and end of the original list
start = newList.start;
end = newList.end;
}
public void findelement(){
System.out.println("enter a element u wanted to know position");
Linkedlist l = new Linkedlist();
Node n = start;
sc = new Scanner(System.in);
int i = sc.nextInt();
int a=1;
while(i!=n.getData()){
a++;
if(n.getLink() == null)
{
System.out.println("Count not find element " + i + " in the list");
return;
}
n=n.getLink();
}
System.out.println("index is " +a);
}
public void display(){
System.out.println("single linked list is + ");
if(size==0){
System.out.println("empty linklist");
}
if(start.getLink()==null){
System.out.println(start.getData() );
return;
}
Node ptr = start;
System.out.print(start.getData()+ "->");
ptr = start.getLink();
while (ptr.getLink() != null)
{
System.out.print(ptr.getData()+ "->");
ptr = ptr.getLink();
}
System.out.print(ptr.getData()+ "\n");
}
}
This is class Node which is in file Node.java
public class Node
{
protected int data;
protected Node link;
// Constructor to class Node with initially refer to null and set data to 0 by default
public Node()
{
link = null;
data = 0;
}
// Constructor to class Node which has both data and reference to next node
public Node(int d,Node n)
{
data = d;
link = n;
}
// Function that set link to next Node (which refer to next node
public void setLink(Node n)
{
link = n;
}
// Function which assign integer data to current Node
public void setData(int d)
{
data = d;
}
/* Function to get link to next node */
public Node getLink()
{
return link;
}
/* Function to get data from current Node */
public int getData()
{
return data;
}
}
Class LinkedList in which methods involved in it. Linkedlist.java file
import java.util.Scanner;
public class Linkedlist
{
protected Node start;
protected Node end ;
public int size ;
public Scanner sc;
/* Constructor */
public Linkedlist()
{
start = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return start == null;
}
/* Function to get size of list */
public int getSize()
{
return size;
}
/* Function to insert an element at begining */
public void insertAtStart(int val)
{
Node nptr = new Node(val, null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.setLink(start);
start = nptr;
}
}
/* Function to insert an element at end */
public void insertAtEnd(int val)
{
Node nptr = new Node(val,null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
end.setLink(nptr);
end = nptr;
}
}
/* Function to insert an element at position */
public void insertAtPos(int val , int pos)
{
Node nptr = new Node(val, null);
Node ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size; i++)
{
if (i == pos)
{
Node tmp = ptr.getLink() ;
ptr.setLink(nptr);
nptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size++ ;
}
/* Function to delete an element at position */
public void deleteAtPos(int pos)
{
if (pos == 1)
{
start = start.getLink();
size--;
return ;
}
if (pos == size)
{
Node s = start;
Node t = start;
while (s != end)
{
t = s;
s = s.getLink();
}
end = t;
end.setLink(null);
size --;
return;
}
Node ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size - 1; i++)
{
if (i == pos)
{
Node tmp = ptr.getLink();
tmp = tmp.getLink();
ptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size-- ;
}
public void reverse(){
Linkedlist newList = new Linkedlist();
Node node = start;
for(int i=0; i
node = node.getLink();
}
//Update the start and end of the original list
start = newList.start;
end = newList.end;
}
public void findelement(){
System.out.println("enter a element u wanted to know position");
Linkedlist l = new Linkedlist();
Node n = start;
sc = new Scanner(System.in);
int i = sc.nextInt();
int a=1;
while(i!=n.getData()){
a++;
if(n.getLink() == null)
{
System.out.println("Count not find element " + i + " in the list");
return;
}
n=n.getLink();
}
System.out.println("index is " +a);
}
public void display(){
System.out.println("single linked list is + ");
if(size==0){
System.out.println("empty linklist");
}
if(start.getLink()==null){
System.out.println(start.getData() );
return;
}
Node ptr = start;
System.out.print(start.getData()+ "->");
ptr = start.getLink();
while (ptr.getLink() != null)
{
System.out.print(ptr.getData()+ "->");
ptr = ptr.getLink();
}
System.out.print(ptr.getData()+ "\n");
}
}
This is a main program which involve execution of main method and calls the method of Linkedlist class.
import java.util.Scanner;
public class singlelist {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Linkedlist list = new Linkedlist();
System.out.println("Single linkedlist display");
char ch;
do
{
System.out.println("\nSingly Linked List Operations\n");
System.out.println("1. insert at begining");
System.out.println("2. insert at end");
System.out.println("3. insert at position");
System.out.println("4. delete at position");
System.out.println("5. check empty");
System.out.println("6. get size");
System.out.println("7. reverse list");
System.out.println("8. tacke element");
int choice = sc.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
list.insertAtStart( sc.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to insert");
list.insertAtEnd( sc.nextInt() );
break;
case 3 :
System.out.println("Enter integer element to insert");
int num = sc.nextInt() ;
System.out.println("Enter position");
int pos = sc.nextInt() ;
if (pos <= 1 || pos > list.getSize() )
System.out.println("Invalid position\n");
else
list.insertAtPos(num,pos);
break;
case 4 :
System.out.println("Enter position");
int p = sc.nextInt() ;
if (p < 1 || p > list.getSize() )
System.out.println("Invalid position\n");
else
list.deleteAtPos(p);
break;
case 5 :
System.out.println("Empty status = "+ list.isEmpty());
break;
case 6 :
System.out.println("Size = "+ list.getSize() +" \n");
break;
case 7 :
list.reverse();
System.out.println("reverse linked list = " + list);
break;
case 8:
list.findelement();
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
/* Display List */
list.display();
System.out.println("\nDo you want to continue (Type y or n) \n");
ch = sc.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
