1. Write a Java method called swap to swap two nodes x and y (and not just their contents) in a doubly linked list L given references only to x and y. You need to change links in nodes x, y, and their neighbors; data elements in x and y do not change. Your method should work correctly when nodes x and y are not next to each other in the list, node x is the previous node of node y in the list, node x is the next node after node y in the list, x and y refer to the same node (in this case they should not be changed). Method swap should have two parameters of type DNode (references to nodes x and y). It should swap x and y and return true if none of x and y are null as well as none of their neighbors (previous of x, next of x, previous of y, next of y) are null. Otherwise (if any of these nodes are null), the method should not change anything and return false (the nodes are not swapped). 2. Write a Java method called concat for concatenating two doubly linked lists L and M, with head and tail dummy nodes, into a new single doubly linked list N. (In a concatenation the elements of the second list are appended to the end of those of the first list.) Lists L and M should remain unchanged. The method should work for all lists, including empty lists. The method concat should have two parameters of type DList (references to lists L and M). It should return the reference (of type DList) to the created list N. 3. Write a Java method called reverse to reverse the order of elements in a given doubly linked list. (Do not create a new list, reverse the elements in the existing list. Do not allocate any new nodes.) The method should work for all lists, including empty lists. If the list is empty the method should so nothing. The method should have one parameter of type DList (reference to the list which elements are to be reversed). The method should not return anything (return type is void). 4. Write a Java method merge to create a new doubly linked list N that contains elements alternately from two given doubly linked lists L and M. If you run out of elements in one of the lists, then append the remaining elements of the other list to N. Lists L and M should remain unchanged. The method should work for all lists, including empty lists. If any one of the two lists is empty, then the method should return a copy of the second list. For example, if list L contains 4 elements one, two, three, four, and list M contains 6 elements a, b, c, d, e, f, then list N should contain the following elements: one, a, two, b, three, c four, d, e, f. The method merge should have two parameters of type DList (references to lists L and M). It should return a reference (of type DList) to the created list N. 5. The main method of DLinkTester class should test all your methods. Make sure to fully exercise the code of the methods (see p. 28 of the textbook). (Note: DList class has toString method that you can use to output list contents.)

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

**********************************************

/** 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;

}

}