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

0: Read Chapter 4 from the textbook. (Doubly linked lists and dummy nodes are explained in Section 4.6.) 1: Use Eclipse. Create a new project with the name, say, lab5. Import the above files DNode.java and DList.java into the project. You will be just using these two classes in your project; their code should not be modified. Create a new class in the project with the name DLinkTester. Write the following methods in the class DLinkTester: 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 do 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.) Note: Specifications for all the methods which you implement should be included as comments in your code. Also, please use inline comments, meaningful variable names, indentation, formatting and whitespace throughout your program to improve its readability