public class SinglyLinkedList implements Cloneable { private static class Node {

private E element; // reference to the element stored at this node

private Node next; // reference to the subsequent node in the list

public Node(E e, Node n) { element = e; next = n; }

public E getElement() { return element; }

public Node getNext() { return next; }

public void setNext(Node n) { next = n; } } //----------- end of nested Node class -----------

// instance variables of the SinglyLinkedList /** The head node of the list */ private Node head = null; // head node of the list (or null if empty)

/** The last node of the list */ private Node tail = null; // last node of the list (or null if empty)

/** Number of nodes in the list */ private int size = 0; // number of nodes in the list

/** Constructs an initially empty list. */ public SinglyLinkedList() { } // constructs an initially empty list

public int size() { return size; }

public boolean isEmpty() { return size == 0; }

public E first() { // returns (but does not remove) the first element if (isEmpty()) return null; return head.getElement(); }

public E last() { // returns (but does not remove) the last element if (isEmpty()) return null; return tail.getElement(); }

// update methods public void addFirst(E e) { // adds element e to the front of the list head = new Node<>(e, head); // create and link a new node if (size == 0) tail = head; // special case: new node becomes tail also size++; }

public void addLast(E e) { // adds element e to the end of the list Node newest = new Node<>(e, null); // node will eventually be the tail if (isEmpty()) head = newest; // special case: previously empty list else tail.setNext(newest); // new node after existing tail tail = newest; // new node becomes the tail size++; }

public E removeFirst() { // removes and returns the first element if (isEmpty()) return null; // nothing to remove E answer = head.getElement(); head = head.getNext(); // will become null if list had only one node size--; if (size == 0) tail = null; // special case as list is now empty return answer; }

@SuppressWarnings({"unchecked"}) public boolean equals(Object o) { if (o == null) return false; if (getClass() != o.getClass()) return false; SinglyLinkedList other = (SinglyLinkedList) o; // use nonparameterized type if (size != other.size) return false; Node walkA = head; // traverse the primary list Node walkB = other.head; // traverse the secondary list while (walkA != null) { if (!walkA.getElement().equals(walkB.getElement())) return false; //mismatch walkA = walkA.getNext(); walkB = walkB.getNext(); } return true; // if we reach this, everything matched successfully }

@SuppressWarnings({"unchecked"}) public SinglyLinkedList clone() throws CloneNotSupportedException { // always use inherited Object.clone() to create the initial copy SinglyLinkedList other = (SinglyLinkedList) super.clone(); // safe cast if (size > 0) { // we need independent chain of nodes other.head = new Node<>(head.getElement(), null); Node walk = head.getNext(); // walk through remainder of original list Node otherTail = other.head; // remember most recently created node while (walk != null) { // make a new node storing same element Node newest = new Node<>(walk.getElement(), null); otherTail.setNext(newest); // link previous node to this one otherTail = newest; walk = walk.getNext(); } } return other; }

public int hashCode() { int h = 0; for (Node walk=head; walk != null; walk = walk.getNext()) { h ^= walk.getElement().hashCode(); // bitwise exclusive-or with element's code h = (h << 5) | (h >>> 27); // 5-bit cyclic shift of composite code } return h; }

public String toString() { StringBuilder sb = new StringBuilder("("); Node walk = head; while (walk != null) { sb.append(walk.getElement()); if (walk != tail) sb.append(", "); walk = walk.getNext(); } sb.append(")"); return sb.toString(); } //main method public static void main(String[] args) { SinglyLinkedList list = new SinglyLinkedList(); list.addFirst("MSP"); list.addLast("ATL"); list.addLast("BOS"); // list.addFirst("LAX"); System.out.println(list); // } }

In this exercise, you will add a method swapNodes to SinglyLinkedList class from above examples. This method should swap two nodes node1 and node2 (and not just their contents) given references only to node1 and node2. The new method should check if node1 and node2 are the same node, etc. Write the main method to test the swapNodes method. Hint: You may need to traverse the list.