Java please, show output! Occasionally, a linked structure that does not use ref
ID: 3909103 • Letter: J
Question
Java please, show output!
Occasionally, a linked structure that does not use references is useful. One such structure uses an array whose items are "linked" by array indexes. Figure 5-35a illustrates an array of nodes that represents the linked list in Figure 5-31. Each node has two data fields, item and next. The next data field is an integer index to the array element that contains the next node in the linked list. Note that the next data field of the last node contains -1. The integer variable head contains the index of the first node in the list. The array elements that currently are not a part of the linked list make up a free list of available nodes. These nodes form another linked list, with the integer variable free containing the index of the first free node. To insert an item into the original linked list, you take a free node from the beginning of the free list and insert it into the linked list (Figure 5-35b). When you delete an item from the linked list, you insert the node into the beginning of the free list (Figure 5-35c). In this way, you can avoid shifting data items. Implement the ADT list by using this array-based linked list.Explanation / Answer
import java.util.Scanner;
class CreateNd
{
//variable declaration
protected int ndval;
protected CreateNd ndlnk;
//non parameterise Constructor
public CreateNd()
{
ndlnk = null;
ndval = 0;
}
//parameterised Constructor
public CreateNd(int d,CreateNd n)
{
ndval = d;
ndlnk = n;
}
/* Function to set ndlnk to next CreateNd */
public void nd_stlk(CreateNd n)
{
ndlnk = n;
}
//create list
public void nd_stdt(int d)
{
ndval = d;
}
public CreateNd nd_gtlk()
{
return ndlnk;
}
public int nd_gtdt()
{
return ndval;
}
}
class llist
{
//variable declaration
protected CreateNd st;
protected CreateNd last ;
public int size ;
//non parameterise Constructor
public llist()
{
st = null;
last = null;
size = 0;
}
//to check if list is empty
public boolean ll_chempty()
{
return st == null;
}
//calc list size
public int ll_gtsz()
{
return size;
}
//to insert at front of the list
public void ll_inatst(int vs)
{
CreateNd fptr = new CreateNd(vs, null);
size++ ;
if(st == null)
{
st = fptr;
last = st;
}
else
{
fptr.nd_stlk(st);
st = fptr;
}
}
//to insert at last of the list
public void ll_inated(int vs)
{
CreateNd fptr = new CreateNd(vs,null);
size++ ;
if(st == null)
{
st = fptr;
last = st;
}
else
{
last.nd_stlk(fptr);
last = fptr;
}
}
//to insert at a particular position
public void ll_inatps(int vs , int position)
{
CreateNd fptr = new CreateNd(vs, null);
CreateNd sptr = st;
position = position - 1 ;
for (int i = 1; i < size; i++)
{
if (i == position)
{
CreateNd temp = sptr.nd_gtlk() ;
sptr.nd_stlk(fptr);
fptr.nd_stlk(temp);
break;
}
sptr = sptr.nd_gtlk();
}
size++ ;
}
//to delete element from a particular position
public void ll_dlatps(int position)
{
if (position == 1)
{
st = st.nd_gtlk();
size--;
return ;
}
if (position == size)
{
CreateNd s = st;
CreateNd t = st;
while (s != last)
{
t = s;
s = s.nd_gtlk();
}
last = t;
last.nd_stlk(null);
size --;
return;
}
CreateNd sptr = st;
position = position - 1 ;
for (int i = 1; i < size - 1; i++)
{
if (i == position)
{
CreateNd temp = sptr.nd_gtlk();
temp = temp.nd_gtlk();
sptr.nd_stlk(temp);
break;
}
sptr = sptr.nd_gtlk();
}
size-- ;
}
//display all the element
public void display()
{
System.out.print(" The elements are ");
if (size == 0)
{
System.out.print("List is EMPTY ");
return;
}
if (st.nd_gtlk() == null)
{
System.out.println(st.nd_gtdt() );
return;
}
CreateNd sptr = st;
System.out.print(st.nd_gtdt()+ "->");
sptr = st.nd_gtlk();
while (sptr.nd_gtlk() != null)
{
System.out.print(sptr.nd_gtdt()+ "->");
sptr = sptr.nd_gtlk();
}
System.out.print(sptr.nd_gtdt()+ " ");
}
}
public class SinglyLinkedList
{
//main Function
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of class llist */
llist obj = new llist(); //object of the list class
char ch;
/* Perform obj operations */
do
{ //menu for the user
System.out.println("1.Insert at Front");
System.out.println("2.Insert at Last");
System.out.println("3.Insert at specific Position");
System.out.println("4.Delete at specific position");
System.out.println("5.Size of the List"); System.out.println("Enter your choice");
//accepting user choice
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter element to insert");
obj.ll_inatst( scan.nextInt() );
break;
case 2 :
System.out.println("Enter element to insert");
obj.ll_inated( scan.nextInt() );
break;
case 3 :
System.out.println("Enter element to insert");
int num = scan.nextInt() ;
System.out.println("Enter your position");
int position = scan.nextInt() ;
if (position <= 1 || position > obj.ll_gtsz() )
System.out.println("Wrong position ");
else
obj.ll_inatps(num, position);
break;
case 4 :
System.out.println("Enter the position you want to delete");
int p = scan.nextInt() ;
if (p < 1 || p > obj.ll_gtsz() )
System.out.println("Wrong position ");
else
obj.ll_dlatps(p);
break;
case 5 :
System.out.println("Size of the list = "+ obj.ll_gtsz() +" ");
break;
default :
System.out.println("Invalid Choice ");
break;
}
/* Display obj */
obj.display();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
OUTPUT
y
1.Insert at Front
2.Insert at Last
3.Insert at specific Position
4.Delete at specific position
5.Size of the List
Enter your choice
5
Size of the list = 3
The elements are 56->12->45
Do you want to continue (Type y or n)
y
1.Insert at Front
2.Insert at Last
3.Insert at specific Position
4.Delete at specific position
5.Size of the List
Enter your choice
4
Enter the position you want to delete
2
The elements are 56->45
Do you want to continue (Type y or n)
y
1.Insert at Front
2.Insert at Last
3.Insert at specific Position
4.Delete at specific position
5.Size of the List
Enter your choice
5
Size of the list = 2
The elements are 56->45
Do you want to continue (Type y or n)
n
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.