Modify the LinkedCollection class to be a SortedLinkedCollecton class and see how that effects our implementation for adding and removing items. You should reference the SortedArrayCollection class provided for how these algorithms should be implemented. What needs to change here? Is it a lot of code or not much?
Include a toString method that creates and returns a string that correctly represents the current collection. Include a test driver application that demonstrates your class correctly.
//---------------------------------------------------------------------------
// LinkedCollection.java
//
// Implements the CollectionInterface using a linked
collection.
// Null elements are not allowed. Duplicate elements are
allowed.
// One constructor is provided, one that creates an empty
collection.
//---------------------------------------------------------------------------
package ch05.collections;
import support.LLNode;
public class LinkedCollection<T> implements
CollectionInterface<T>
{
protected LLNode<T> head;
// head of the linked list
protected int numElements = 0; // number of elements in this
collection
// set by find method
protected boolean found;
// true if target found, else false
protected LLNode<T> location; // node containing
target, if found
protected LLNode<T> previous; // node preceding
location
public LinkedCollection()
{
numElements = 0;
head = null;
}
public boolean add(T element)
// Adds element to this collection.
{
LLNode<T> newNode = new
LLNode<T>(element);
newNode.setLink(head);
head = newNode;
numElements++;
return true;
}
protected void find(T target)
// Searches the collection for an occurence of an element e such
that
// e.equals(target). If successful, sets instance variables
// found to true, location to node containing e, and previous
// to the node that links to location. If not successful,
sets
// found to false.
{
location = head;
found = false;
while (location != null)
{
if
(location.getInfo().equals(target)) // if they match
{
found = true;
return;
}
else
{
previous =
location;
location =
location.getLink();
}
}
}
public int size()
// Returns the number of elements on this collection.
{
return numElements;
}
public boolean contains (T target)
// Returns true if this collection contains an element e such
that
// e.equals(target); otherwise, returns false.
{
find(target);
return found;
}
public boolean remove (T target)
// Removes an element e from this collection such that
e.equals(target)
// and returns true; if no such element exists, returns
false.
{
find(target);
if (found)
{
if (head ==
location)
head =
head.getLink(); // remove first node
else
previous.setLink(location.getLink()); // remove node at
location
numElements--;
}
return found;
}
public T get(T target)
// Returns an element e from this collection such that
e.equals(target);
// if no such element exists, returns null.
{
find(target);
if (found)
return location.getInfo();
else
return null;
}
public boolean isEmpty()
// Returns true if this collection is empty; otherwise, returns
false.
{
return (numElements == 0);
}
public boolean isFull()
// Returns true if this collection is full; otherwise, returns
false.
{
return false; // Linked implementation is never
full
}
}
//----------------------------------------------------------------------------
//
SortedArrayCollection.java
by
Dale/Joyce/Weems
Chapter 5
//
// Implements the CollectionInterface using a sorted array. The
collection is
// stored in increasing order as defined by the compareTo method of
the added
// elements. Only Comparable elements should be added to a
collection. It is
// assumed that the compareTo method and equals method as defined
for added
// elements are consistent.
//
// Null elements are not permitted in this collection.
//
// Two constructors are provided: one that creates a collection of
a default
// original capacity, and one that allows the calling program to
specify the
// original capacity. The collection is unbounded.
//----------------------------------------------------------------------------
package ch05.collections;
public class SortedArrayCollection<T> implements
CollectionInterface<T>
{
protected final int DEFCAP = 100; // default capacity
protected int
origCap;
// original capacity
protected T[]
elements;
// array to hold collection elements
protected int numElements = 0; // number of
elements in this collection
// set by find method
protected boolean found; // true if target found, otherwise
false
protected int location; // indicates location of target
if found,
// indicates add index if not found
public SortedArrayCollection()
{
elements = (T[]) new Object[DEFCAP];
origCap = DEFCAP;
}
public SortedArrayCollection(int capacity)
{
elements = (T[]) new Object[capacity];
this.origCap = capacity;
}
protected void enlarge()
// Increments the capacity of the collection by an amount
// equal to the original capacity.
{
// Create the larger array.
T[] larger = (T[]) new Object[elements.length +
origCap];
// Copy the contents from the smaller array into
the larger array.
for (int i = 0; i < numElements; i++)
{
larger[i] = elements[i];
}
// Reassign elements reference.
elements = larger;
}
protected void find(T target)
// Searches elements for an occurrence of an element e such
that
// e.equals(target). If successful, sets instance variables
// found to true and location to the array index of e. If
// not successful, sets found to false and location to the
// array index where target should be inserted.
{
location = 0;
found = false;
if (!isEmpty())
recFind(target, 0, numElements
- 1);
}
protected void recFind(T target, int first, int last)
// Used by find.
{
int result;
// result of the comparison
if (first > last)
{
found = false;
result =
((Comparable)target).compareTo(elements[location]);
if (result > 0)
location++; // adjust location to indicate insert
index
}
else
{
location = (first + last) / 2;
result =
((Comparable)target).compareTo(elements[location]);
if (result == 0) // found
target
found = true;
else
if (result > 0) //
target too high
recFind(target, location
+ 1, last);
else
// target too low
recFind(target, first,
location - 1);
}
}
public boolean add(T element)
// Precondition: element is Comparable to previously added
objects
//
// Adds element to this collection.
{
if (numElements == elements.length)
enlarge();
find(element); // sets location to index
where element belongs
for (int index = numElements; index >
location; index--)
elements[index] = elements[index -
1];
elements[location] = element;
numElements++;
return true;
}
public boolean remove (T target)
// Removes an element e from this collection such that
e.equals(target)
// and returns true; if no such element exists, returns
false.
{
find(target);
if (found)
{
for (int i = location; i <=
numElements - 2; i++)
elements[i] =
elements[i+1];
elements[numElements - 1] =
null;
numElements--;
}
return found;
}
public int size()
// Returns the number of elements on this collection.
{
return numElements;
}
public boolean contains (T target)
// Returns true if this collection contains an element e such
that
// e.equals(target); otherwise, returns false.
{
find(target);
return found;
}
public T get(T target)
// Returns an element e from this collection such that
e.equals(target);
// if no such element exists, returns null.
{
find(target);
if (found)
return elements[location];
else
return null;
}
public boolean isEmpty()
// Returns true if this collection is empty; otherwise, returns
false.
{
return (numElements == 0);
}
public boolean isFull()
// This collection is unbounded so always returns false.
{
return false;
}
}
/*
* To change this license header, choose License Headers in Project
Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
*
*/
//---------------------------------------------------------------------------
// LinkedCollection.java
//
// Implements the CollectionInterface using a linked
collection.
// Null elements are not allowed. Duplicate elements are
allowed.
// One constructor is provided, one that creates an empty
collection.
//---------------------------------------------------------------------------
package ch05.collections;
import support.LLNode;
public class LinkedCollection<T> implements
CollectionInterface<T>
{
protected LLNode<T> head; // head of the linked list
protected int numElements = 0; // number of elements in this
collection
// set by find method
protected boolean found; // true if target found, else false
protected LLNode<T> location; // node containing target, if
found
protected LLNode<T> previous; // node preceding location
public LinkedCollection()
{
numElements = 0;
head = null;
}
public boolean add(T element)
// Adds element to this collection.
{
LLNode<T> newNode = new LLNode<T>(element);
newNode.setLink(head);
head = newNode;
numElements++;
return true;
}
protected void find(T target)
// Searches the collection for an occurence of an element e such
that
// e.equals(target). If successful, sets instance variables
// found to true, location to node containing e, and previous
// to the node that links to location. If not successful,
sets
// found to false.
{
location = head;
found = false;
while (location != null)
{
if (location.getInfo().equals(target)) // if they match
{
found = true;
return;
}
else
{
previous = location;
location = location.getLink();
}
}
}
public int size()
// Returns the number of elements on this collection.
{
return numElements;
}
public boolean contains (T target)
// Returns true if this collection contains an element e such
that
// e.equals(target); otherwise, returns false.
{
find(target);
return found;
}
public boolean remove (T target)
// Removes an element e from this collection such that
e.equals(target)
// and returns true; if no such element exists, returns
false.
{
find(target);
if (found)
{
if (head == location)
head = head.getLink(); // remove first node
else
previous.setLink(location.getLink()); // remove node at
location
numElements--;
}
return found;
}
public T get(T target)
// Returns an element e from this collection such that
e.equals(target);
// if no such element exists, returns null.
{
find(target);
if (found)
return location.getInfo();
else
return null;
}
public boolean isEmpty()
// Returns true if this collection is empty; otherwise, returns
false.
{
return (numElements == 0);
}
public boolean isFull()
// Returns true if this collection is full; otherwise, returns
false.
{
return false; // Linked implementation is never full
}
}
//----------------------------------------------------------------------------
// SortedArrayCollection.java by Dale/Joyce/Weems Chapter 5
//
// Implements the CollectionInterface using a sorted array. The
collection is
// stored in increasing order as defined by the compareTo method of
the added
// elements. Only Comparable elements should be added to a
collection. It is
// assumed that the compareTo method and equals method as defined
for added
// elements are consistent.
//
// Null elements are not permitted in this collection.
//
// Two constructors are provided: one that creates a collection of
a default
// original capacity, and one that allows the calling program to
specify the
// original capacity. The collection is unbounded.
//----------------------------------------------------------------------------
package ch05.collections;
public class SortedArrayCollection<T> implements
CollectionInterface<T>
{
protected final int DEFCAP = 100; // default capacity
protected int origCap; // original capacity
protected T[] elements; // array to hold collection elements
protected int numElements = 0; // number of elements in this
collection
protected int temp;
// set by find method
protected boolean found; // true if target found, otherwise
false
protected int location; // indicates location of target if
found,
// indicates add index if not found
boolean sorted=false;
public SortedArrayCollection()
{
elements = (T[]) new Object[DEFCAP];
origCap = DEFCAP;
while(!sorted)
{sorted=true;
for(int i=0; i<T.length; i++ ) // modifying for bubble
sorting
{ if(T[i]>T[i+1])
{
temp=T[i];
T[i]=T[i+1];
T[i+1]=T[i];
sorted=false;
}
}
}
}
public SortedArrayCollection(int capacity)
{
elements = (T[]) new Object[capacity];
this.origCap = capacity;
}
protected void enlarge()
// Increments the capacity of the collection by an amount
// equal to the original capacity.
{
// Create the larger array.
T[] larger = (T[]) new Object[elements.length + origCap];
// Copy the contents from the smaller array into the larger
array.
for (int i = 0; i < numElements; i++)
{
larger[i] = elements[i];
}
// Reassign elements reference.
elements = larger;
}
protected void find(T target)
// Searches elements for an occurrence of an element e such
that
// e.equals(target). If successful, sets instance variables
// found to true and location to the array index of e. If
// not successful, sets found to false and location to the
// array index where target should be inserted.
{
location = 0;
found = false;
if (!isEmpty())
recFind(target, 0, numElements - 1);
}
protected void recFind(T target, int first, int last)
// Used by find.
{
int result; // result of the comparison
if (first > last)
{
found = false;
result = ((Comparable)target).compareTo(elements[location]);
if (result > 0)
location++; // adjust location to indicate insert index
}
else
{
location = (first + last) / 2;
result = ((Comparable)target).compareTo(elements[location]);
if (result == 0) // found target
found = true;
else
if (result > 0) // target too high
recFind(target, location + 1, last);
else // target too low
recFind(target, first, location - 1);
}
}
public boolean add(T element)
// Precondition: element is Comparable to previously added
objects
//
// Adds element to this collection.
{
if (numElements == elements.length)
enlarge();
find(element); // sets location to index where element
belongs
for (int index = numElements; index > location; index--)
elements[index] = elements[index - 1];
elements[location] = element;
numElements++;
return true;
}
public boolean remove (T target)
// Removes an element e from this collection such that
e.equals(target)
// and returns true; if no such element exists, returns
false.
{
find(target);
if (found)
{
for (int i = location; i <= numElements - 2; i++)
elements[i] = elements[i+1];
elements[numElements - 1] = null;
numElements--;
}
return found;
}
public int size()
// Returns the number of elements on this collection.
{
return numElements;
}
public boolean contains (T target)
// Returns true if this collection contains an element e such
that
// e.equals(target); otherwise, returns false.
{
find(target);
return found;
}
public T get(T target)
// Returns an element e from this collection such that
e.equals(target);
// if no such element exists, returns null.
{
find(target);
if (found)
return elements[location];
else
return null;
}
public boolean isEmpty()
// Returns true if this collection is empty; otherwise, returns
false.
{
return (numElements == 0);
}
public boolean isFull()
// This collection is unbounded so always returns false.
{
return false;
}
}
}
SSS
COMMENT DOWN FOR ANY QUERIES AND,
LEAVE A THUMBS UP IF THIS ANSWER HELPS YOU.
Modify the LinkedCollection class to be a SortedLinkedCollecton class and see how that effects our implementation...
Question from Object-Oriented Data Structures Using Java 4th Edition Chapter 5 Question 30 Add the following methods to the LinkedCollection class, and create a test driver for each to show that they work correctly. Code each of these methods by accessing the internal variables of the LinkedCollection, not by calling the previously defined methods of the class.String toString() creates and returns a string that correctly represents the current collection. 1. Such a method could prove useful for testing and debugging...
Suppose we decide to add a new operation to our Stack ADT called sizeIs, which returns a value of primitive type int equal to the number of items on the stack. The method signature for sizeIS is public int sizeIs() a.) Write the code for sizeIs for the ArrayStack class b.) Write the code for sizeIs for the LinkedStack class (do not add any instance variables to the class; each time sizeIs is called you must "walk" through the stack...
When compiling the LinkedList and Iterator class, the following error is being produced: Note: LinkedList.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details. Any suggestions? public class LinkedList<T> { Node<T> itsFirstNode; Node<T> itsLastNode; private int size; public LinkedList() { itsFirstNode = null; itsLastNode = null; size = 0; } public Iterator<T> getIterator() { return new Iterator(this); } // THIS WILL NEED...
Plz help me with the code. And here are the requirement. Thanks!! You are required to design and implement a circular list using provided class and interface. Please filling the blank in CircularList.java. This circular list has a tail node which points to the end of the list and a number indicating how many elements in the list. And fill out the blank of the code below. public class CircularList<T> implements ListInterface<T> { protected CLNode<T> tail; // tail node that...
JAVA: Already completed: MyList.java, MyAbstractList.java, MyArrayList.java, MyLinkedLink.java, MyStack.java, MyQueue.java. Need to complete: ReversePoem.java. This program has you display a pessimistic poem from a list of phrases. Next, this program has you reverse the phrases to find another more optimistic poem. Use the following algorithm. 1. You are given a list of phrases each ending with a pound sign: ‘#’. 2. Create a single String object from this list. 3. Then, split the String of phrases into an array of phrases...
In Java You may add any classes or methods to the following as you see fit in order to complete the given tasks. Modify the LinkedList (or DoubleLinkedList) class and add a method append. append should take another LinkedList (DoubleLinkedList) as input and append that list to the end of this list. The append method should work by doing a few "arrow" adjustments on the boxes and it should not loop through the input list to add elements one at...
Please use Java programming: Modify both ArrayList and LinkedList classes and add the following method to both classes: public void reverseThisList(), This method will reverse the lists. When testing the method: print out the original list, call the new method, then print out the list again ------------------------------------------------------------------------- //ARRAY LIST class: public class ArrayList<E> implements List<E> { /** Array of elements in this List. */ private E[] data; /** Number of elements currently in this List. */ private int size; /**...
1) Extend the Binary Search Tree ADT to include a public method leafCount that returns the number of leaf nodes in the tree. 2) Extend the Binary Search Tree ADT to include a public method singleParent-Count that returns the number of nodes in the tree that have only one child. 3) The Binary search tree ADT is extended to include a boolean method similarTrees that receives references to two binary trees and determines whether the shapes of the trees are...
Java help: Please help complete the locate method that is in bold.. public class LinkedDoubleEndedList implements DoubleEndedList { private Node front; // first node in list private Node rear; // last node in list private int size; // number of elements in list ////////////////////////////////////////////////// // YOU MUST IMPLEMENT THE LOCATE METHOD BELOW // ////////////////////////////////////////////////// /** * Returns the position of the node containing the given value, where * the front node is at position zero and the rear node is...
Please help with the codes for the implementation of java.util.List, specifically for the 3 below overridden methods @Override public int lastIndexOf(Object arg0) { required code } @Override public ListIterator<R> listIterator() { required code } @Override public ListIterator<R> listIterator(int arg0) { required code } PLEASE NOTE: Below are some of other overridden methods that are already implemented, they are meant to be examples of what the answers to the above questions for the 3 methods should...