Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Circular linked list implementation. public class CRefUnsortedList implements ListInterface { protected int numElements; // Number of elements on this list protected LLNode currentPos; // Current
Circular linked list implementation.
public class CRefUnsortedListWe 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 changeimplements ListInterface { protected int numElements; // Number of elements on this list protected LLNode currentPos; // Current position for iteration // set by find method protected boolean found; // true if element found, else false protected LLNode location; // node containing element, if found protected LLNode previous; // node preceding location protected LLNode list; // the last node on the list public CRefUnsortedList() { numElements = 0; list = null; currentPos = null; } public void add(T element) // Adds element to this list. { LLNode newNode = new LLNode (element); if (list == null) { // add element to an empty list list = newNode; newNode.setLink(list); } else { // add element to a non-empty list newNode.setLink(list.getLink()); list.setLink(newNode); list = newNode; } numElements++; } 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 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(); } 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; } }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started