Instead of a String[] it must use a Doubly-Linked List with a Dummy Front and Du
ID: 3848648 • Letter: I
Question
Instead of a String[] it must use a Doubly-Linked List with a Dummy Front and Dummy Rear to store the List's data. How doI make a private Node in my class list?
The List class' public API is the same except:
(1) Constructor List(int size) has been replaced with List(). The Linked-List has no maximum size.
(2) Constructor List(List list) has been added. It constructs a new List with the items in the input list.
//main:
public class AssignmentFour
{
public static void main(String[] args)
{
List myList = new List();
List emptyList = new List(myList);
// Cause List Empty Message
myList.removeFront();
myList.removeRear();
myList.removeItem("a");
// Cause Not found message
myList.addToFront("x");
myList.removeItem("y");
myList.removeItem("x");
myList.addAfterItem("x", "z");
myList.addBeforeItem("x", "z");
// Normal behavior
myList.addToFront("not.");
myList.addToFront("or");
myList.addToRear("is");
myList.addToRear("try.");
myList.addAfterItem("is", "no");
myList.addBeforeItem("is", "There");
myList.addToFront("Do");
myList.addAfterItem("or", "do");
myList.print("Original list");
myList.printSorted("Sorted Original List");
emptyList.print("Empty List");
List copyOfList = new List(myList);
sop(" Front is " + myList.getFront());
sop("Rear is " + myList.getRear());
sop("Count is " + myList.askCount());
sop("Is There present? " + myList.isPresent("There"));
sop("Is Dog present? " + myList.isPresent("Dog"));
myList.addToFront("junk");
myList.addToRear("morejunk");
myList.addAfterItem("or", "moremorejunk");
myList.print("List with junk");
sop("Count is " + myList.askCount());
copyOfList.print("Untouched copy of the list");
myList.removeFront();
myList.removeRear();
myList.removeItem("moremorejunk");
myList.print("List with junk removed");
sop("Count is " + myList.askCount());
sop("");
copyOfList.print("Untouched copy of the list");
while(myList.askCount() > 0) myList.removeFront();
myList.print("List after removing all items");
copyOfList.print("Copy of List after removing all items");
}
private static void sop(String s)
{
System.out.println(s);
}
}
//My class list:
import java.util.Arrays;
public class List {
private String[] mList;
private int mCount;
public List(int size)
{
mCount = 0;
mList = new String[size];
}
public void addToFront(java.lang.String item)
{
if (mCount == mList.length)
{
System.out.println("List Full");
}
else if (mCount == 0)
{
mList[0] = item;
mCount++;
}
else
{
shiftRight(mCount,0);
mList[0] = item;
mCount++;
}
}
public void addToRear(java.lang.String item)
{
if (mCount == mList.length)
{
System.out.println("List Full");
}
else {
mList[mCount++] = item;
}
}
public void addBeforeItem(java.lang.String beforeItem, java.lang.String item)
{
if (mCount == mList.length)
{
System.out.println("List Full");
}
else if(isPresent(beforeItem) && mCount < mList.length)
{
if (find(beforeItem) == 0)
{
shiftRight(mCount,0);
mList[0] = item;
mCount++;
}
else
{
shiftRight(mCount,find(beforeItem));
mList[find(beforeItem)] = item;
mCount++;
}
}
else if(!isPresent(beforeItem))
{
System.out.println("Item not found");
}
}
//Finding the index of the specific element
private int find (String s)
{
for(int i = 0; i < mCount;i++)
{
if (mList[i].equals(s))
{
return i;
}
}
return -1;
}
public void addAfterItem(java.lang.String afterItem, java.lang.String item)
{
if (mCount == mList.length)
{
System.out.println("List Full");
}
else if(isPresent(afterItem) && mCount < mList.length)
{
shiftRight(mCount, find(afterItem));
mList[find(afterItem)+1] = item;
mCount++;
}
else
{
System.out.println("Item not found");
}
}
public java.lang.String getFront()
{
return mList[0];
}
public java.lang.String getRear()
{
return mList[mCount-1];
}
public boolean isPresent(String item)
{
for (int i = 0; i < mCount; i++)
if(mList[i].equals(item))
{
return true;
}
return false;
}
public int askCount()
{
return mCount;
}
public void removeFront()
{
if (mCount == 0)
{
System.out.println("List Empty");
}
else
{
shiftLeft(mCount, 0);
mCount--;
}
}
public void removeRear()
{
if (mCount == 0)
{
System.out.println("List Empty");
}
else
{
mCount--;
}
}
public void removeItem(java.lang.String item)
{
if (mCount == 0)
{
System.out.println("List Empty");
}
else if (!isPresent(item))
{
System.out.println("Item not found");
}
else
{
int x = find(item);
shiftLeft(mCount,x);
mCount--;
}
}
public void print(java.lang.String title)
{
System.out.println("");
System.out.println(title);
for(int i = 0; i < mCount; i++)
{
System.out.print(mList[i] + " ");
}
System.out.println();
}
public void printSorted(java.lang.String title)
{
String[] mListC = new String[mCount];
System.arraycopy( mList, 0,mListC, 0, mCount);
Arrays.sort(mListC);
System.out.println();
System.out.println(title);
for(String s : mListC)
{
System.out.print(s + " ");
}
System.out.println();
}
private void shiftRight(int count, int end)
{
for (int i = (count-1); i >= end; i--)
{
mList[i+1] = mList[i];
}
}
private void shiftLeft(int count, int start)
{
for (int i = start;i < count-1; i++)
{
mList[i] = mList[i+1];
}
}
}
// Desired Output:
Explanation / Answer
/*
* Java Program to Implement Doubly Linked List
*/
import java.util.Scanner;
/* Class Node */
class Node
{
protected int data;
protected Node next, prev;
/* Constructor */
public Node()
{
next = null;
prev = null;
data = 0;
}
/* Constructor */
public Node(int d, Node n, Node p)
{
data = d;
next = n;
prev = p;
}
/* Function to set link to next node */
public void setLinkNext(Node n)
{
next = n;
}
/* Function to set link to previous node */
public void setLinkPrev(Node p)
{
prev = p;
}
/* Funtion to get link to next node */
public Node getLinkNext()
{
return next;
}
/* Function to get link to previous node */
public Node getLinkPrev()
{
return prev;
}
/* Function to set data to node */
public void setData(int d)
{
data = d;
}
/* Function to get data from node */
public int getData()
{
return data;
}
}
/* Class linkedList */
class linkedList
{
protected Node start;
protected Node end ;
public int size;
/* Constructor */
public linkedList()
{
start = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return start == null;
}
/* Function to get size of list */
public int getSize()
{
return size;
}
/* Function to insert element at begining */
public void insertAtStart(int val)
{
Node nptr = new Node(val, null, null);
if(start == null)
{
start = nptr;
end = start;
}
else
{
start.setLinkPrev(nptr);
nptr.setLinkNext(start);
start = nptr;
}
size++;
}
/* Function to insert element at end */
public void insertAtEnd(int val)
{
Node nptr = new Node(val, null, null);
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.setLinkPrev(end);
end.setLinkNext(nptr);
end = nptr;
}
size++;
}
/* Function to insert element at position */
public void insertAtPos(int val , int pos)
{
Node nptr = new Node(val, null, null);
if (pos == 1)
{
insertAtStart(val);
return;
}
Node ptr = start;
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node tmp = ptr.getLinkNext();
ptr.setLinkNext(nptr);
nptr.setLinkPrev(ptr);
nptr.setLinkNext(tmp);
tmp.setLinkPrev(nptr);
}
ptr = ptr.getLinkNext();
}
size++ ;
}
/* Function to delete node at position */
public void deleteAtPos(int pos)
{
if (pos == 1)
{
if (size == 1)
{
start = null;
end = null;
size = 0;
return;
}
start = start.getLinkNext();
start.setLinkPrev(null);
size--;
return ;
}
if (pos == size)
{
end = end.getLinkPrev();
end.setLinkNext(null);
size-- ;
}
Node ptr = start.getLinkNext();
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node p = ptr.getLinkPrev();
Node n = ptr.getLinkNext();
p.setLinkNext(n);
n.setLinkPrev(p);
size-- ;
return;
}
ptr = ptr.getLinkNext();
}
}
/* Function to display status of list */
public void display()
{
System.out.print(" Doubly Linked List = ");
if (size == 0)
{
System.out.print("empty ");
return;
}
if (start.getLinkNext() == null)
{
System.out.println(start.getData() );
return;
}
Node ptr = start;
System.out.print(start.getData()+ " <-> ");
ptr = start.getLinkNext();
while (ptr.getLinkNext() != null)
{
System.out.print(ptr.getData()+ " <-> ");
ptr = ptr.getLinkNext();
}
System.out.print(ptr.getData()+ " ");
}
}
/* Class DoublyLinkedList */
public class DoublyLinkedList
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of linkedList */
linkedList list = new linkedList();
System.out.println("Doubly Linked List Test ");
char ch;
/* Perform list operations */
do
{
System.out.println(" Doubly Linked List Operations ");
System.out.println("1. insert at begining");
System.out.println("2. insert at end");
System.out.println("3. insert at position");
System.out.println("4. delete at position");
System.out.println("5. check empty");
System.out.println("6. get size");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
list.insertAtStart( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to insert");
list.insertAtEnd( scan.nextInt() );
break;
case 3 :
System.out.println("Enter integer element to insert");
int num = scan.nextInt() ;
System.out.println("Enter position");
int pos = scan.nextInt() ;
if (pos < 1 || pos > list.getSize() )
System.out.println("Invalid position ");
else
list.insertAtPos(num, pos);
break;
case 4 :
System.out.println("Enter position");
int p = scan.nextInt() ;
if (p < 1 || p > list.getSize() )
System.out.println("Invalid position ");
else
list.deleteAtPos(p);
break;
case 5 :
System.out.println("Empty status = "+ list.isEmpty());
break;
case 6 :
System.out.println("Size = "+ list.getSize() +" ");
break;
default :
System.out.println("Wrong Entry ");
break;
}
/* Display List */
list.display();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Output :