Instead of a String[] it must use a Doubly-Linked List with a Dummy Front and Du
ID: 3837737 • 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 do I change that 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;
/**
* Create a List with the indicated size
* @param size - the maximum number of items in the List
*/
public List(int size)
{
mCount = 0;
mList = new String[size];
}
/**
* If the List is not full, item becomes the new front element If the List is full, prints "List Full"
* @param item - the item to add
*/
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];
}
}
}
Explanation / Answer
//My class list:
class Node {
String data;
Node next;
Node prev;
}
public class List {
private Node front;
private Node rear;
/**
* Create a List with the indicated size
*
* @param size
* - the maximum number of items in the List
*/
public List() {
//
}
public List(List list) {
this.front=list.front;
this.rear=list.rear;
}
/**
* If the List is not full, item becomes the new front element If the List
* is full, prints "List Full" <<<<<< you can change your comment because
* it's not required now
*
* @param item
* - the item to add
*/
// Node1 <--> node2 <---> node3
// Front rear
public void addToFront(java.lang.String item) {
Node temp = new Node();
temp.data = item;
if (front == null) {
front = temp;
rear = front;
} else {
temp.next = front;
front.prev = temp;
front = temp;
}
}
public void addToRear(java.lang.String item) {
Node temp = new Node();
temp.data = item;
if (rear == null) {
rear = temp;
front = rear;
} else {
temp.prev = rear;
rear.next = temp;
rear = temp;
}
}
public void addBeforeItem(java.lang.String beforeItem, java.lang.String item) {
// node1<--->temp<--->beforeNode //temp is new node
Node temp = new Node();
temp.data = item;
Node beforeNode = isPresent(beforeItem);
if (beforeNode != null) {
Node prevNodeOfBeforeNode = beforeNode.prev;
if (beforeNode == front) {
addToFront(item);
} else {
prevNodeOfBeforeNode.next = temp;
temp.prev = prevNodeOfBeforeNode;
temp.next = beforeNode;
beforeNode.prev = temp;
}
} else {
System.err.println(" we are not able to find beforeItem string");
}
}
public void addAfterItem(java.lang.String afterItem, java.lang.String item) {
// node1<--->afterItem<--->temp<--->node //temp is new node
Node temp = new Node();
temp.data = item;
Node afterItemNode = isPresent(afterItem);
if (afterItemNode != null) {
Node nextafterItemNode = afterItemNode.next;
if (afterItemNode == rear) {
addToRear(item);
} else {
afterItemNode.next = temp;
temp.prev = afterItemNode;
temp.next = nextafterItemNode;
nextafterItemNode.prev = temp;
}
} else {
System.err.println(" we are not able to find afterItem string");
}
}
public Node getFront() {
return front;
}
public Node getRear() {
return rear;
}
public Node isPresent(String item) { // this function returns Node that
// contains string item or null
Node temp = front;
while (temp != null) {
if (temp.data.contentEquals(item)) {
return temp;
}
temp = temp.next;
}
return null;
}
public int askCount() {
int count = 0;
Node temp = front;
while (temp != null) {
count++;
temp = temp.next;
}
return count;
}
public void removeFront() {
front = front.next;
front.prev = null;
}
public void removeRear() {
rear = rear.prev;
rear.next = null;
}
// Node<--->itemNode<---><node> //itemNode to be deleted
public void removeItem(java.lang.String item) {
Node itemNode = isPresent(item);
itemNode.prev.next = itemNode.next;
itemNode.next.prev = itemNode.prev;
}
public void print(java.lang.String title) {
System.out.println("");
System.out.println(title);
Node temp = front;
while (temp != null) {
System.out.println(temp.data);
temp = temp.next;
}
System.out.println();
}
public void printSorted(java.lang.String title) {
//you have to sort linked 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);
}
}