§ 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 double linear linked list, every node consists of three parts: information and two reference parts. First reference part holds the reference of the previous node and the other holds the reference of the next node. It allows two-way and linear traversal in the list.
Creating node:
1. Create an ADT named “node” that contains “two references”(two nodes) and “information” parts
2. Allocate memory for “first” node, treat the same as “last” and make its reference parts null.
3. Allocate memory for a temporary node, read information and link it to the last node (last.next=temp) in the list. Link its “prev” part to “last” (temp.prev=last) and call it “last”
4. Repeat the process 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. Make links as shown in the diagram (temp.next=ptr.next, ptr.next.prev=temp then ptr.next =temp,temp.prev=ptr)
4. handle it differently if it is insertion at last node
Deleting node:
2. Make the links as shown below (ptr=ptr.next.next and ptr.next.prev=ptr)
3. handle it differently if it is deletion at last node
Program to insert, create and delete elements in a double linked list:
import java.io.*;
class node
{
public int x;
public node next;
public node prev;
}
class DoubleLinkedList
{
public node first;
public node last;
DoubleLinkedList()
{
first=new node();
first.next=null;
first.prev=null;
last=first;
}
void add (int v)
{
node temp=new node();
temp.x=v;
temp.next=null;
last.next=temp;
temp.prev=last;
last=temp;
}
void insert(int p,int v)
{
node ptr=first,temp;
for(int i=1;i<=p-1;i++)
ptr=ptr.next;
if(ptr.next==null)
add(v);
else
{
temp=new node();
temp.x=v;
temp.next=ptr.next;
ptr.next.prev=temp;
ptr.next=temp;
temp.prev=ptr;
}
}
void del(int p)
{
node ptr=first,temp;
for(int i=1;i<=p-1;i++)
ptr=ptr.next;
if(ptr.next.next==null)
{
temp=last;
last=last.prev;
last.next=null;
}
else
{
temp=ptr.next;
ptr.next=ptr.next.next;
ptr.next.prev=ptr;
}
temp=null;
}
void show()
{
System.out.println("\nList Elements:Left to Right");
for(node ptr=first.next;ptr!=null;ptr=ptr.next)
System.out.print("\t"+ptr.x);
System.out.println("\nList Elements:Right to Left");
for(node ptr=last;ptr.prev!=null;ptr=ptr.prev)
System.out.print("\t"+ptr.x);
}
}
Class DListTest
{
public static void main(String as[]) throws Exception
{
String con="";
int x,op,p,v;
DoubleLinkedList l1=new DoubleLinkedList();
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: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
| First |
| null |
| Ptr.next |
| Ptr |
| Temp |
| Inserting node in Double linked list |
| null |
| Last |
0 comments:
Post a Comment