A linked list is a way to store a collection of elements. Like an array these can be character or integers. Each element in a linked list is stored in the form of a node.
Node:
A node is a collection of two sub-elements or parts. A data part that stores the element and a next part that stores the link to the next node.
Linked List:
A linked list is formed when many such nodes are linked together to form a chain. Each node points to the next node present in the order. The first node is always used as a reference to traverse the list and is called HEAD. The last node points to NULL.
The Following program will be used to perform the following tasks on the linked list:
1. Add a node at the end.
2. Add a node in the beginning.
3. Add a node in any position.
4. Delete a node from the end.
5. Delete a node from the beginning.
6. Delete a node from any position.
7. Reverse the linklist.
8. Print the linklist.
Nodal Class
The nodes in the linked list program will be based on the class “node”
public class node
{
private int d;
private node link;
void setdata(int x)
{
d=x;
}
void setlink(node n)
{
link=n;
}
int getdata()
{
return d;
}
node getlink()
{
return link;
}
}Class – Linked List
import java.io.*;
public class linklist
{
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
node head;
linklist()
{
head=null;
}
void append()throws IOException//push
{
node p=new node(),q;
if(p==null)
{
System.out.println("Cannot add more:");
return;
}
int x;
System.out.println("Enter data:");
x=Integer.parseInt(br.readLine());
p.setdata(x);
p.setlink(null);
if(head==null)
{
head=p;
return;
}
q=head;
while(q.getlink()!=null)
{
q=q.getlink();
}
q.setlink(p);
}
void add_beg()throws IOException
{
node p = new node();
int x;
System.out.println("Enter a value:");
x = Integer.parseInt(br.readLine());
p.setdata(x);
if(head==null)
{
head = p;
p.setlink(null);
return;
}
p.setlink(head);
head = p;
}
void delete_end() //pop for stack
{
if(head==null)
{
System.out.println("Linked list is empty");
return;
}
if(head.getlink()==null)
{
System.out.println("Deleted node = "+head.getdata());
head=null;
return;
}
node q=head.getlink(), r=head;
while(q.getlink()!=null)
{
r=r.getlink();
q=q.getlink();
}
System.out.println("deleted value = "+q.getdata());
r.setlink(null);
}
void delete_beg()
{
if(head==null)
{
System.out.println("Cannot delete");
return;
}
System.out.println("deleted value= "+head.getdata());
head=head.getlink();
}
int count()
{
node q = head;
int c=0;
while(q!=null)
{
q = q.getlink();
c++;
}
return c;
}
void add_any_pos()throws IOException
{
node p = new node(), q;
int c, x, pos;
System.out.println("Enter the position where you want to enter the node:");
pos = Integer.parseInt(br.readLine());
c = count();
if(pos<1||pos>c+1)
{
System.out.println("Invalid Position.");
return;
}
if(pos==1)
{
add_beg();
return;
}
if(pos==c+1)
{
append();
return;
}
System.out.println("Enter a value:");
x = Integer.parseInt(br.readLine());
p.setdata(x);
int i;
q = head;
for(i=2;i<pos;i++)
{
q=q.getlink();
}
p.setlink(q.getlink());
q.setlink(p);
}
void del_any_pos()throws IOException
{
node r, q;
if(head==null)
{
System.out.println("Nothing to Delete.");
return;
}
int x, pos, c, i;
System.out.println("Enter the position where you want to delete the node:");
pos = Integer.parseInt(br.readLine());
c = count();
if(pos<1||pos>c)
{
System.out.println("Invalid Position.");
return;
}
if(pos==1)
{
/*System.out.println("Deleted Value is:"+head.getdata());
head = head.getlink();*/
delete_beg();
return;
}
if(pos==c)
{
delete_end();
return;
}
q=head.getlink();
r=head;
for(i=2;i<pos;i++)
{
r=r.getlink();
q=q.getlink();
}
System.out.println("Deleted Value is:"+q.getdata());
r.setlink(q.getlink());
}
void reverse()
{
if(head==null)
{
System.out.println("The linklist is empty.");
return;
}
int c=0;
node q=head;
while(q!=null)
{
c++;
q = q.getlink();
}
int rr[] = new int[c], i;
q = head;
for(i=0;i<c;i++)
{
rr[i] = q.getdata();
q = q.getlink();
}
q = head;
for(i=c-1;i>=0;i--)
{
q.setdata(rr[i]);
q = q.getlink();
}
}
void print()
{
if(head==null)
{
System.out.println("Empty nothing to display");
return;
}
System.out.println("The elements of a linked list are");
node q=head;
while(q!=null)
{
System.out.println(q.getdata());
q=q.getlink();
}
}
public static void main()throws IOException
{
char ch;
linklist ll = new linklist();
do
{
System.out.println("MENU");
System.out.println("1. Add a node at the end.");
System.out.println("2. Add a node in the beginning.");
System.out.println("3. Add a node in any position.");
System.out.println("4. Delete a node from the end.");
System.out.println("5. Delete a node from the beginning.");
System.out.println("6. Delete a node from any position.");
System.out.println("7. Reverse the linklist.");
System.out.println("8. Print the linklist.");
System.out.println("9. Exit.");
System.out.println("Enter your choice.");
ch = (br.readLine()).charAt(0);
switch(ch)
{
case '1':
ll.append();
break;
case '2':
ll.add_beg();
break;
case '3':
ll.add_any_pos();
break;
case '4':
ll.delete_end();
break;
case '5':
ll.delete_beg();
break;
case '6':
ll.del_any_pos();
break;
case '7':
ll.reverse();
break;
case '8':
ll.print();
break;
case '9':
System.out.println("Thank You for using the program.");
break;
default:
System.out.println("Wrong input enter again.");
}
}while(ch!='9');
}
}