We implemented the CRefUhsor tedLi st by maintaining a single reference, to the
ID: 3698667 • Letter: W
Question
We implemented the CRefUhsor tedLi st by maintaining a single reference, to the last element of the list. Suppose we changed our approach so that we ma tain two references into the linked list, one to the first list element and one to the last list element. a. Would the new approach necessitate a change in the class constructor? If so, b. Would the new approach necessitate a change in the get Next method? If so, c. Would the new approach necessitate a change in the find method? If so, d. Would the new approach necessitate a change in the add method? If so, describe the change. describe the change. describe the change. describe the change.Explanation / Answer
a. If we add reference to the first list element, then we need to change the constructor definition, by setting the reference to the first list element to null, since teh list is empty at instantiation.
b. The new approach would not require any change in the getNext() method since it depends on the position of the current element.
c. The new approach doesn't necessitate any change in the find method since we can traverse either from end to start or from start to end of the list. In both the approach if the element is present in the list, it can find it. So its not necessary to make any changes in the find method.
d. With the new approach changes in add method will be required. When an element is added to an empty list then both the first and last element reference should point to this element. Also when an element is added at the end of the list, then the next pointer of the this node should point to the first element of the list as it is circular list.
The updated code with the changes are (changes are bolded) :
public class CRefUnsortedList<T> implements ListInterface<T>
{
protected int numElements; // Number of elements on this list
protected LLNode<T> currentPos; // Current position for iteration
// set by find method
protected boolean found; // true if element found, else false
protected LLNode<T> location; // node containing element, if found
protected LLNode<T> previous; // node preceding location
protected LLNode<T> list; // the last node on the list
protected LLNode<T> head; // the first node on the list
//change in constructor
public CRefUnsortedList()
{
numElements = 0;
list = null;
head = null; // set head = null since the list is empty
currentPos = null;
}
//change in add method
public void add(T element)
// Adds element to this list.
{
LLNode<T> newNode = new LLNode<T>(element);
if (list == null)
{
// add element to an empty list
head = newNode; // make head point to the newNode
list = newNode;
newNode.setLink(list);
}
else
{
// add element to a non-empty list
newNode.setLink(head); // last element points to the first element of the list
list.setLink(newNode);
list = newNode;
}
numElements++;
}
//no change required
protected void find(T target)
// Searches list for an occurrence 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 unsuccessful, sets
// found to false.
{
location = list;
found = false;
if (list != null)
do
{
// move search to the next node
previous = location;
location = location.getLink();
// check for a match
if (location.getInfo().equals(target))
found = true;
}
while ((location != list) && !found);
}
public int size()
// Returns the number of elements on this list.
{
return numElements;
}
public boolean contains (T element)
// Returns true if this list contains an element e such that
// e.equals(element), otherwise returns false.
{
find(element);
return found;
}
public boolean remove (T element)
// Removes an element e from this list such that e.equals(element)
// and returns true; if no such element exists, returns false.
{
find(element);
if (found)
{
if (list == list.getLink()) // if single-element list
list = null;
else
{
if (previous.getLink() == list) // if removing last node
list = previous;
previous.setLink(location.getLink()); // remove node
}
numElements--;
}
return found;
}
public T get(T element)
// Returns an element e from this list such that e.equals(element);
// if no such element exists returns null.
{
find(element);
if (found)
return location.getInfo();
else
return null;
}
public String toString()
// Returns a nicely formatted string that represents this list.
{
String listString = "List: ";
if (list != null)
{
LLNode<T> prevNode = list;
do
{
listString = listString + " " + prevNode.getLink().getInfo() + " ";
prevNode = prevNode.getLink();
}
while (prevNode != list);
}
return listString;
}
public void reset()
// Initializes current position for an iteration through this list,
// to the first element on this list.
{
if (list != null)
currentPos = list.getLink();
}
// no change required
public T getNext()
// Preconditions: the list is not empty
// the list has been reset
// the list has not been modified since most recent reset
//
// Returns the element at the current position on this list.
// If the current position is the last element then it advances the value
// of the current position to the first element, otherwise it advances
// the value of the current position to the next element.
{
T next = currentPos.getInfo();
currentPos = currentPos.getLink();
return next;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.