Suppose we have a doubly-linked list class with this internal representation Nod
ID: 3750316 • Letter: S
Question
Suppose we have a doubly-linked list class with this internal representation Node first; Node last; int sizei Suppose L is a linked list object. a. Suppose that L.get (index) and L.set (index,obj) always go up the node chain from the beginning of the list. What is a simple, more efficient way of implementing get/set? b. Regardless of any changes made from part (a), what is so inefficient about execution of the following code? n -L.size)/2; if (L.get (n) .equals("AAA")) .set(n, "BBB" ) ; How could you effectively use an additional internal Node and an additional int data member to create a modification of get/set operations so to make them even more efficient?Explanation / Answer
import java.util.Scanner;
class DLL
{
protected int size;
protected Node first,last;
//default constructor
public DLL()
{
first=null;
last=null;
size=0;
}
public DLL(int size,Node first,Node last)//overloaded constructor
{
this.size=size;
this.first=first;
this.last=last;
}
public void setFirst(Node first)
{
this.first=first;
}
public void setLast(Node last)
{
this.last=last;
}
public Node getFirst()
{
return first;
}
public Node getLast()
{
return last;
}
public void setSize(int size)
{
this .size=size;
}
public int getSize()
{
return size;
}
}
class DoubleLinkedList
{
protected Node start ;
Protected Node end;
public int data;
public DoubleLinkedList()
{
start=null;
end=null;
size=0;
}
public boolean isEmpty()
{
return start==null;
}
public int getData()
{
return data;
}
public void insertBegin(int val)
{
Node nptr=new Node(val,null,null);
if(start==null)
{
start=nptr;
end=start;
}
else
{
start.setFirst(nptr);
nptr.setLast(start);
start=nptr;
}
size++;
}
public void insertEnd(int val)
{
Node nptr=new Node(val,null,null);
if(start==null)
{
start=nptr;
end=start;
}
else
{
nptr.setLast(end);
end.setFirst(nptr);
end=nptr;
}
size++;
}
public void insertPos(int index,int val)
{
Node nptr=new Node(val,null,null);
if(index==1)
{
insertStart(val);
return;
}
Node ptr=start;
for(int i=2;i<=data;i++)
{
if(i==index)
{
Node tmp=ptr.getFirst();
ptr.setFirst(nptr);
nptr.setLast(ptr);
nptr.setFirst(tmp);
tmp.setLast(nptr);
}
ptr=ptr.getFirst();
}
size++;
}
public void display()
{
System.out.print(" Double Linked List ");
if(data==0)
{
System.out.println("empty");
return;
}
if(start.getFirst()==null)
{
System.out.println(start.getSize());
return;
}
Node ptr=start;
System.out.print(start.getSize()+"<->");
ptr=start.getFirst();
while(ptr.getFirst()!=null)
{
System.out.print(ptr.getSize()+" ");
}
}
public class DLL1
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
linkedList list=new linkedList();
System.out.println("Doubly Linked list");
char ch;
do
{
S.O.P("1.Insert at Beginning");
S.O.P("2.Insert at end");
S.O.P("3.Insert at position");
S.O.P("4.Display");
S.O.P("5.Get Size");
int ch=sc.nextInt();
switch(ch)
{
case 1:
S.O.P("Enter int value");
list.insertBegin(sc.nextInt());
break;
case 2:
S.O.P("Enter insert value");
list.insertEnd(sc.nextInt());
break;
}
case 3:
S.O.P("Enter value to insert");
int num=sc.nextInt();
System.out.println("Enter Position");
int pos=sc.nextInt();
if(pos<1||pos>list.getData())
S.O.P("Invalid Position");
else
list..insertIndex(num,pos);
break;
case 4:
list.display();
break;
case 5:
S.O.P("Size="+list.getSize());
break;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.