Define a method in ListReferenceBased: insertAtEnd(Object item) that uses the ad

Question

Define a method in ListReferenceBased: insertAtEnd(Object item) that uses the add method as a helper method and adds the new item at the end of the list.

// ****************************************************
// Reference-based implementation of ADT list.
// ****************************************************
public class ListReferenceBased implements ListInterface {
// reference to linked list of items
private Node head;
private int numItems; // number of items in list

public ListReferenceBased() {
numItems = 0;
head = null;
} // end default constructor

public boolean isEmpty() {
return numItems == 0;
} // end isEmpty

public int size() {
return numItems;
} // end size

private Node find(int index) {
// --------------------------------------------------
// Locates a specified node in a linked list.
// Precondition: index is the number of the desired
// node. Assumes that 1 <= index <= numItems+1
// Postcondition: Returns a reference to the desired
// node.
// --------------------------------------------------
Node curr = head;
for (int skip = 1; skip < index; skip++) {
curr = curr.getNext();
} // end for
return curr;
} // end find

public Object get(int index)
throws ListIndexOutOfBoundsException {
if (index >= 1 && index <= numItems) {
// get reference to node, then data in node
Node curr = find(index);
Object dataItem = curr.getItem();
return dataItem;
}
else {
throw new ListIndexOutOfBoundsException(
"List index out of bounds exception on get");
} // end if
} // end get

public void add(int index, Object item)
throws ListIndexOutOfBoundsException {
if (index >= 1 && index <= numItems+1) {
if (index == 1) {
// insert the new node containing item at
// beginning of list
Node newNode = new Node(item, head);
head = newNode;
}
else {
Node prev = find(index-1);
// insert the new node containing item after
// the node that prev references
Node newNode = new Node(item, prev.getNext());
prev.setNext(newNode);
} // end if
numItems++;
}
else {
throw new ListIndexOutOfBoundsException(
"List index out of bounds exception on add");
} // end if
} // end add

public void remove(int index)
throws ListIndexOutOfBoundsException {
if (index >= 1 && index <= numItems) {
if (index == 1) {
// delete the first node from the list
head = head.getNext();
}
else {
Node prev = find(index-1);
// delete the node after the node that prev
// references, save reference to node
Node curr = prev.getNext();
prev.setNext(curr.getNext());
} // end if
numItems--;
} // end if
else {
throw new ListIndexOutOfBoundsException(
"List index out of bounds exception on remove");
} // end if
} // end remove

public void removeAll() {
// setting head to null causes list to be
// unreachable and thus marked for garbage
// collection
head = null;
numItems = 0;
} // end removeAll
  
public String toString(){
String returnString = "List with " + numItems + " nodes. ";
try {
Node tempNode = head;
while (tempNode != null) {
returnString += "Node: " + tempNode.toString() + " ";
tempNode = tempNode.getNext();
}
}
catch(NullPointerException npe) {
npe.printStackTrace();
}
return returnString;
}
  
/**
* insert: inserts a new item into a sorted list.
* @param item an Object, the item to be inserted
* @return none
* Precondition: list is sorted, and the items on the list implement the Comparable interface.
* Postcondition: list is still sorted, with the new item inserted.
*/
public void insert(Object item)
{
// Create a new node and put the given item in it.
Node newNode = new Node(item);
  
// Declare variables for traversing the list using the piggybacking technique.
Node current, prev;
current = head;
prev = null;
  
// Determine the point of insertion.
while (current!=null && ((Comparable) current.getItem()).compareTo(newNode.getItem()) < 0) {
//StockItem currentData = (StockItem)current.getItem();
//StockItem newData = (StockItem)newNode.getItem();
prev = current;
current = current.getNext();
}
  
// Check for the special case of inserting at the beginning of the list.
if (prev != null) {
// The new node is not at the beginning of the list.
newNode.setNext(current);
prev.setNext(newNode);
} // end if
else {
// Inserting at the beginning of the list.
newNode.setNext(head);
head = newNode;
} // end else
  
// We have inserted a new item so increment the number of items.
this.numItems++;
} // end method insert
  
} // end ListReferenceBased

List interface is just an interface therefore it just has the method headers

// ****************************************************
// Interface for the ADT list
// ****************************************************
public interface ListInterface
{
// list operations:
public boolean isEmpty();
public int size();
public void add(int index, Object item) throws ListIndexOutOfBoundsException;
public void remove(int index) throws ListIndexOutOfBoundsException;
public Object get(int index) throws ListIndexOutOfBoundsException;
public void removeAll();
} // end ListInterface

Explanation / Answer

My code is in Bold

// ****************************************************

// Reference-based implementation of ADT list.
// ****************************************************
public class ListReferenceBased implements ListInterface
{
// reference to linked list of items
private Node head;
private int numItems; // number of items in list
public ListReferenceBased() {
numItems = 0;
head = null;
} // end default constructor
public boolean isEmpty() {
return numItems == 0;
} // end isEmpty
public int size() {
return numItems;
} // end size
private Node find(int index) {
// --------------------------------------------------
// Locates a specified node in a linked list.
// Precondition: index is the number of the desired
// node. Assumes that 1 <= index <= numItems+1
// Postcondition: Returns a reference to the desired
// node.
// --------------------------------------------------
Node curr = head;
for (int skip = 1; skip < index; skip++) {
curr = curr.getNext();
} // end for
return curr;
} // end find
public Object get(int index)
throws ListIndexOutOfBoundsException {
if (index >= 1 && index <= numItems) {
// get reference to node, then data in node
Node curr = find(index);
Object dataItem = curr.getItem();
return dataItem;
}
else {
throw new ListIndexOutOfBoundsException(
"List index out of bounds exception on get");
} // end if
} // end get
public void add(int index, Object item)
throws ListIndexOutOfBoundsException {
if (index >= 1 && index <= numItems+1) {
if (index == 1) {
// insert the new node containing item at
// beginning of list
Node newNode = new Node(item, head);
head = newNode;
}
else {
Node prev = find(index-1);
// insert the new node containing item after
// the node that prev references
Node newNode = new Node(item, prev.getNext());
prev.setNext(newNode);
} // end if
numItems++;
}
else {
throw new ListIndexOutOfBoundsException(
"List index out of bounds exception on add");
} // end if
} // end add
  
////////////////////////////////////////////////////////////////
// insertAtEnd method
// Takes an item as input
// calls add method with index as numItems+1 and given item
public void insertAtEnd(Object item)
throws ListIndexOutOfBoundsException {
// call add function with numItems+1 and item
add(numItems+1, item);
} // end insertAtEnd
////////////////////////////////////////////////////////////////
  
public void remove(int index)
throws ListIndexOutOfBoundsException {
if (index >= 1 && index <= numItems) {
if (index == 1) {
// delete the first node from the list
head = head.getNext();
}
else {
Node prev = find(index-1);
// delete the node after the node that prev
// references, save reference to node
Node curr = prev.getNext();
prev.setNext(curr.getNext());
} // end if
numItems--;
} // end if
else {
throw new ListIndexOutOfBoundsException(
"List index out of bounds exception on remove");
} // end if
} // end remove
public void removeAll() {
// setting head to null causes list to be
// unreachable and thus marked for garbage
// collection
head = null;
numItems = 0;
} // end removeAll
  
public String toString(){
String returnString = "List with " + numItems + " nodes. ";
try {
Node tempNode = head;
while (tempNode != null) {
returnString += "Node: " + tempNode.toString() + " ";
tempNode = tempNode.getNext();
}
}
catch(NullPointerException npe) {
npe.printStackTrace();
}
return returnString;
}
  
/**
* insert: inserts a new item into a sorted list.
* @param item an Object, the item to be inserted
* @return none
* Precondition: list is sorted, and the items on the list implement the Comparable interface.
* Postcondition: list is still sorted, with the new item inserted.
*/
public void insert(Object item)
{
// Create a new node and put the given item in it.
Node newNode = new Node(item);
  
// Declare variables for traversing the list using the piggybacking technique.
Node current, prev;
current = head;
prev = null;
  
// Determine the point of insertion.
while (current!=null && ((Comparable) current.getItem()).compareTo(newNode.getItem()) < 0) {
//StockItem currentData = (StockItem)current.getItem();
//StockItem newData = (StockItem)newNode.getItem();
prev = current;
current = current.getNext();
}
  
// Check for the special case of inserting at the beginning of the list.
if (prev != null) {
// The new node is not at the beginning of the list.
newNode.setNext(current);
prev.setNext(newNode);
} // end if
else {
// Inserting at the beginning of the list.
newNode.setNext(head);
head = newNode;
} // end else
  
// We have inserted a new item so increment the number of items.
this.numItems++;
} // end method insert
  
} // end ListReferenceBased

---------------------------------------------------------------------------------------------------

// ****************************************************
// Interface for the ADT list
// ****************************************************
public interface ListInterface
{
// list operations:
public boolean isEmpty();
public int size();
public void add(int index, Object item) throws ListIndexOutOfBoundsException;
public void insertAtEnd(Object item) throws ListIndexOutOfBoundsException;
public void remove(int index) throws ListIndexOutOfBoundsException;
public Object get(int index) throws ListIndexOutOfBoundsException;
public void removeAll();
} // end ListInterface

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.