Linked list is a type of data structure that holds nodes linked to each other. Every node consists of information parts and reference parts. Linked list allows many operations like creation, insertion, deletion etc. on it.
In a single linear linked list, every node consists of two parts: information and address parts. Reference part holds the reference of the next node. It allows one-way and linear traversal in the list. End of the list points to null.
Creating node:
1. Create an ADT named “node” that contains “reference”(a node) and “information” parts.
2. Allocate memory for “first” node, treat the same as “last” and make its reference part null.
3. Allocate memory for a temporary node, read information and link it to the last node in the list and call it “last”
4. Repeat the process i.e. the previous step till user wishes to continue.
Inserting node:
1. Take a reference named “ptr” and move it from first node to a node that is prior to the inserting position.
2. Allocate memory for a temporary node, read information
3. Establish links as shown below (temp.next = ptr.next, then ptr.next=temp)
4. link it to the address of “ptr” node as shown
5. handle it differently if it is insertion at last node
Deleting node:
1. Take a reference named “ptr” and move it from first node to a node that is prior to the deleting position.
2. Make the link as shown in the diagram (ptr.next = ptr.next.next)
3. handle it differently when deleting the last node
Program to insert, create and delete elements in a single linked list:
import java.io.*;
class node
{
public int x;
public node next;
}
class LinkedList
{
public node first;
LinkedList()
{
first=new node();
first.next=null;
}
void add (int v)
{
node temp=new node();
temp.x=v;
temp.next=null;
node ptr=first;
while(ptr.next!=null)
ptr=ptr.next;
ptr.next=temp;
}
void insert(int p,int v)
{
node ptr=first,temp;
for(int i=1;i<=p-1;i++)
ptr=ptr.next;
temp=new node();
temp.x=v;
temp.next=ptr.next;
ptr.next=temp;
}
void del(int p)
{
node ptr=first,temp;
for(int i=1;i<=p-1;i++)
ptr=ptr.next;
temp=ptr.next;
ptr.next=ptr.next.next;
temp=null;
}
void show()
{
System.out.println("\nList Elements:");
for(node ptr=first.next;ptr!=null;ptr=ptr.next)
System.out.print("\t"+ptr.x);
}
}
class SListTest
{
public static void main(String as[]) throws Exception
{
String con="";
int x,op,p,v;
LinkedList l1=new LinkedList();
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(isr);
System.out.println("Enter elements to create");
do
{
x=Integer.parseInt(br.readLine());
l1.add(x);
System.out.print("Add more?(y,n):");
con=br.readLine();
}while(con.equals("y"));
l1.show();
do
{
System.out.println("\n 1.Insert\n 2.Delete \n 3.Display \n 4.Exit");
System.out.println("\nSelect an option:");
op=Integer.parseInt(br.readLine());
if(op==1)
{
System.out.println("Enter Position to insert:");
p= Integer.parseInt(br.readLine());
System.out.println("Enter Value to insert:");
v= Integer.parseInt(br.readLine());
l1.insert(p,v);
}
if(op==2)
{
System.out.println("Enter Position to delete:");
p= Integer.parseInt(br.readLine());
l1.del(p);
}
l1.show();
}while(op<4);
}
}
/* Output: */
Enter elements to create
30
Add more?(y,n):y
40
Add more?(y,n):y
50
Add more?(y,n):n
List Elements:
30 40 50
1.Insert
2.Delete
3.Display
4.Exit
Select an option:1
Enter Position to insert:2
Enter Value to insert:99
List Elements:
30 99 40 50
1.Insert
2.Delete
3.Display
4.Exit
Select an option: 4
l1.show();
}while(op<4);
}
}
/* Output: */
Enter elements to create
30
Add more?(y,n):y
40
Add more?(y,n):y
50
Add more?(y,n):n
List Elements:Left to Right
30 40 50
List Elements:Right to Left
50 40 30
1.Insert
2.Delete
3.Display
4.Exit
Select an option:1
Enter Position to insert:2
Enter Value to insert:99
List Elements:Left to Right
30 99 40 50
List Elements:Right to Left
50 40 99 30
1.Insert
2.Delete
3.Display
4.Exit
Select an option: 4
0 comments:
Post a Comment