I need to write a main mathod that tests all the below methods, which are swap,
ID: 3730449 • Letter: I
Question
I need to write a main mathod that tests all the below methods, which are swap, concat, merge, reverse.
Thanks!
public class EE 269 {
public boolean swap(DNode x, DNode y){
if(x.getNext()==null || x.getPrev() == null || y.getNext()==null|| y.getPrev()==null || x==null || y==null || x==y){
return false;
}
else{
DNode tempX = x;
x.setNext(y.getNext());
x.setPrev(y.getPrev());
x.getPrev().setNext(y);
x.getNext().setPrev(y);
y.setNext(tempX.getNext());
y.setPrev(tempX.getPrev());
y.getPrev().setNext(x);
y.getNext().setPrev(x);
return true;
}
}
public DList Concat(DList L, DList M){
DNode tempL = L.getLast();
L.getLast().setNext(M.getFirst());
M.getFirst().setPrev(tempL);
return L;
}
public DList reverse(DList list){
DNode n = list.getFirst(), next;
while(n.getNext() != null){
next = n.getNext();
n.setNext(n.getPrev());
n.setPrev(next);
n = next;
}
return list;
}
public DList merge(DList L, DList M){
DList N = new DList();
DNode p = L.getFirst();
DNode q = M.getFirst();
while (p != L.getLast() && q !=M.getLast()) {
N.addLast(p);
N.addLast(q);
p = p.getNext();
q = q.getNext();
}
while(p != L.getLast()){
N.addLast(p);
p = p.getNext();
}
while(q != M.getLast()){
N.addLast(q);
q = q.getNext();
}
return N;
}
public static void main (String args[]) {
//code goes here
}
}
Dnode class:
/** 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 class:
/** 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;
}
}
Explanation / Answer
Answer.)
Main method provided below :
Code :
package example3;
public class EE269 {
public boolean swap(DNode x, DNode y){
if(x.getNext()==null || x.getPrev() == null || y.getNext()==null|| y.getPrev()==null || x==null || y==null || x==y){
return false;
}
else{
DNode tempX = x;
x.setNext(y.getNext());
x.setPrev(y.getPrev());
x.getPrev().setNext(y);
x.getNext().setPrev(y);
y.setNext(tempX.getNext());
y.setPrev(tempX.getPrev());
y.getPrev().setNext(x);
y.getNext().setPrev(x);
return true;
}
}
public DList Concat(DList L, DList M){
DNode tempL = L.getLast();
L.getLast().setNext(M.getFirst());
M.getFirst().setPrev(tempL);
return L;
}
public DList reverse(DList list){
DNode n = list.getFirst(), next;
while(n.getNext() != null){
next = n.getNext();
n.setNext(n.getPrev());
n.setPrev(next);
n = next;
}
return list;
}
public DList merge(DList L, DList M){
DList N = new DList();
DNode p = L.getFirst();
DNode q = M.getFirst();
while (p != L.getLast() && q !=M.getLast()) {
N.addLast(p);
N.addLast(q);
p = p.getNext();
q = q.getNext();
}
while(p != L.getLast()){
N.addLast(p);
p = p.getNext();
}
while(q != M.getLast()){
N.addLast(q);
q = q.getNext();
}
return N;
}
public static void main (String args[]) {
EE269 e=new EE269();
DNode node1=new DNode("abc", null, null);
DNode node2=new DNode("bcd", node1, null);
node1.setNext(node2);
DNode node3=new DNode("cde", node2, null);
node2.setNext(node3);
DNode node4=new DNode("def", node3, null);
node3.setNext(node4);
DList list1=new DList();
list1.addFirst(node1);
list1.addAfter(node1, node2);
DList list2=new DList();
list2.addFirst(node3);
list2.addAfter(node3, node4);
e.Concat(list1, list2);
e.merge(list1, list2);
e.reverse(list1);
e.swap(node1, node3);
}
}
//Dnode class:
/** Node of a doubly linked list of strings */
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 class:
/** Doubly linked list with nodes of type DNode storing strings. */
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;
}
}
Note : Do debug the code if you run into any issues. Run the program in debug mode. For queries, drop a comment below.