Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Below are the two given codes, like it states they don't need to be changed but they are needed: DNode: /** Node of a doubly
Below are the two given codes, like it states they don't need to be changed but they are needed:
DNode:
/** Node of a doubly linked list of strings */
public class DNode {
private String element; // String element stored by a node
private DNode next, prev; // Pointers to next and previous nodes
/** Constructor that creates a node with given fields
* Parameters:
* e - the initial element of this new node
* p - a reference to the node before this new node
* n - a reference to a node after this new node
* (references may be null)
* Postcondition:
* This new node contains the specified data and links to the
* previous and next nodes
**/
public DNode(String e, DNode p, DNode n) {
element = e;
prev = p;
next = n;
}
/** Accessor method to get the element from this node.
* Returns:
* the element of this node
**/
public String getElement() { return element; }
/** Accessor method to get a reference to the previous node.
* Returns:
* the previous node of this node
**/
public DNode getPrev() { return prev; }
/** Accessor method to get a reference to the next node.
* Returns:
* the next node of this node
* */
public DNode getNext() { return next; }
/** Sets the element of this node
* Parameters:
* newElem - the new element to place in this node
* Postcondition:
* The element of this node has been set to newElem.
**/
public void setElement(String newElem) { element = newElem; }
/** Sets the previous node of this node
* Parameters:
* newPrev - a reference to the node that should appear before
* this node (or the null reference)
* Postcondition:
* The link to the node before this node has been set to newPrev.
**/
public void setPrev(DNode newPrev) { prev = newPrev; }
/** Sets the next node of this node
* Parameters:
* newNext - a reference to the node that should appear after
* this node (or the null reference)
* Postcondition:
* The link to the node after this node has been set to newNext.
**/
public void setNext(DNode newNext) { next = newNext; }
}
DList:
/**Doubly linked list with nodes of type DNode storing strings. */
public class DList {
private int size; // number of elements
private DNode header, trailer; // sentinels
/** Constructor that creates an empty list */
public DList() {
size = 0;
header = new DNode(null, null, null); // create header
trailer = new DNode(null, header, null); // create trailer
header.setNext(trailer); // make header and trailer point to each other
}
/** Returns the number of elements in the list */
public int size() { return size; }
/** Returns whether the list is empty */
public boolean isEmpty() { return (size == 0); }
/** Returns the first node of the list
* Precondition:
* List is not empty
* Throws: IllegalStateException
* Indicates that the list is empty
**/
public DNode getFirst() throws IllegalStateException {
if (isEmpty()) throw new IllegalStateException("List is empty");
return header.getNext();
}
/** Returns the last node of the list
* Precondition:
* List is not empty
* Throws: IllegalStateException
* Indicates that the list is empty
**/
public DNode getLast() throws IllegalStateException {
if (isEmpty()) throw new IllegalStateException("List is empty");
return trailer.getPrev();
}
/** Returns the node before the given node v.
* Parameters:
* v - reference to a node in the list
* Precondition:
* v is not the header and v is not null
* Returns:
* the node before the given node v.
* Throws: IllegalArgumentException
* Indicates that v is the header
**/
public DNode getPrev(DNode v) throws IllegalArgumentException {
if (v == header) throw new IllegalArgumentException
("Cannot move back past the header of the list");
return v.getPrev();
}
/** Returns the node after the given node v.
* Parameters:
* v - reference to a node in the list
* Precondition:
* v is not the trailer and v is not null
* Returns:
* the node after the given node v.
* Throws: IllegalArgumentException
* Indicates that v is the trailer
**/
public DNode getNext(DNode v) throws IllegalArgumentException {
if (v == trailer) throw new IllegalArgumentException
("Cannot move forward past the trailer of the list");
return v.getNext();
}
/** Inserts the given node z before the given node v.
* Parameters:
* v - reference to a node in the list,
* z - reference to the node to be inserted
* Precondition:
* v is not the header and v is not null and z is not null
* Postcondition:
* Node z has been inserted before the given node v
* Throws: IllegalArgumentException
* Indicates that v is the header
**/
public void addBefore(DNode v, DNode z) throws IllegalArgumentException {
DNode u = getPrev(v); // may throw an IllegalArgumentException
z.setPrev(u);
z.setNext(v);
v.setPrev(z);
u.setNext(z);
size++;
}
/** Inserts the given node z after the given node v.
* Parameters:
* v - reference to a node in the list,
* z - reference to the node to be inserted
* Precondition:
* v is not the trailer and v is not null and z is not null
* Postcondition:
* Node z has been inserted after the given node v
* Throws: IllegalArgumentException
* Indicates that v is the trailer
**/
public void addAfter(DNode v, DNode z) throws IllegalArgumentException {
DNode w = getNext(v); // may throw an IllegalArgumentException
z.setPrev(v);
z.setNext(w);
w.setPrev(z);
v.setNext(z);
size++;
}
/** Inserts the given node v at the head of the list
* Parameters:
* v - reference to the node to be inserted
* Precondition: v is not null
* Postcondition:
* Node v has been inserted at the head of the list
**/
public void addFirst(DNode v) {
addAfter(header, v);
}
/** Inserts the given node v at the tail of the list
* Parameters:
* v - reference to the node to be inserted
* Precondition: v is not null
* Postcondition:
* Node v has been inserted at the tail of the list
**/
public void addLast(DNode v) {
addBefore(trailer, v);
}
/** Removes the given node v from the list.
* Parameters:
* v - reference to the node to be removed
* Precondition:
* v is not the header and v is not the trailer
* Postcondition:
* Node v has been removed from the linked list
**/
public void remove(DNode v) {
DNode u = getPrev(v); // may throw an IllegalArgumentException
DNode w = getNext(v); // may throw an IllegalArgumentException
// unlink the node from the list
w.setPrev(u);
u.setNext(w);
v.setPrev(null);
v.setNext(null);
size--;
}
/** Returns whether a given node has a previous node
* Parameters:
* v - reference to a node in the list
* Precondition: v is not null
* Returns:
* true if v has a previous node and the previous node is not a header;
* false otherwise
**/
public boolean hasPrev(DNode v) {
return (v.getPrev() != header) && (v != header) ;
}
/** Returns whether a given node has a next node
* Parameters:
* v - reference to a node in the list
* Precondition: v is not null
* Returns:
* true if v has a next node and the next node is not a trailer;
* false otherwise
**/
public boolean hasNext(DNode v) {
return (v.getNext() != trailer) && (v != trailer);
}
/** Returns a string representation of the list */
public String toString() {
String s = "[";
DNode v = header.getNext();
while (v != trailer) {
s += v.getElement();
v = v.getNext();
if (v != trailer)
s += ",";
}
s += "]";
return s;
}
}
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