In this assignment, use the code for DoublyLinkedList we have developed in class (you can also write your own implementation which behaves in the same way). The task is to add two new methods to that implementation void public Node swapNodes(Node n, Node m); void public selectionSort(); 1) The swapNodes function assumes that two valid nodes of the list have been passed to it (similar to the methods removeAfter and insertAfter). In addition, swapNodes assumes that the node m is to the right of n (the nodes could be equal though). This method should return the reference to the rightmost of the nodes after the swap. 2) Using the swapNodes method implement the sorting algorithm selectionSort which works as follows: a. Scan all the nodes of the given list for the node which contains the minimal item. b. Swap the node containing the minimal item with the first node on the list. c. After step b, the first item in the final sorted list will be fixed. d. Now restrict your focus to the sub-list starting from the second element of the list you obtained, and go to step a. e. Keep doing this until the list under consideration shrinks to a single node, at which point the algorithm will finish and the original list will be sorted.

code -

public class Node { public T item_; public Node prev_; public Node next_; public Node(T item) { item_ = item; prev_ = null; next_ = null; } public String toString() { String outStr = ""; if (item_ != null) { outStr += "item = " + item_.toString() + " "; } else { outStr += "item = null "; } if (prev_ != null) { outStr += "prev_ hash code = " + prev_.hashCode() + " "; } else { outStr += "prev_ hash code = null "; } if (next_ != null) { outStr += "next_ hash code = " + next_.hashCode() + " "; } else { outStr += "next_ hash code = null "; } return outStr; } }

public class DoublyLinkedList> implements LinkedListI { Node head_; Node tail_; DoublyLinkedList() { head_ = null; tail_ = null; } public String toString() { String outStr = ""; Node node = head_; while (node != null) { outStr += node.item_.toString() + " -> "; node = node.next_; } outStr += "++++++++++++++"; return outStr; } @Override public void prepend(T item) { Node node = new Node(item); if (head_ == null) { head_ = node; tail_ = node; return; } node.next_ = head_; head_.prev_ = node; head_ = node; } @Override public void append(T item) { Node node = new Node(item); if (head_ == null) { head_ = node; tail_ = node; return; } node.prev_ = tail_; tail_.next_ = node; tail_ = node; } @Override public Node removeFirst() { if (head_ == null) { return head_; }

Node retNode = head_; if (head_.next_ == null) { head_ = null; tail_ = null; return retNode; } head_ = head_.next_; head_.prev_ = null; return retNode; } @Override public Node removeLast() { // What if the list is empty if (head_ == null) return null; // Need to return a node Node retNode = tail_; // What if there's only one node? if (head_.next_ == null) { head_ = null; tail_ = null; return retNode; } // Typical case Node prev = tail_.prev_; prev.next_ = null; tail_ = prev; return retNode; } // We're expecting here a correct location @Override public void insertAfter(Node location, T item) { // Convention: if location is null, prepend & return if (location == null) { prepend(item); return; } // If location is tail_ append and return if (location == tail_) { append(item); return; } // We have at least two nodes Node node = new Node(item); Node sucNode = location.next_;

node.next_ = sucNode; sucNode.prev_ = node; node.prev_ = location; location.next_ = node; } // We're expecting here a correct location @Override public Node removeAfter(Node location) { // Convention: if location is null, remove first and return if (location == null) { return removeFirst(); } // if location is tail_, there's nothing to remove if (location == tail_) return null; // if location is penultimate node remove lastj if (location.next_ == tail_) { return removeLast(); } // Finally, we have a typical case Node retNode = location.next_; Node sucNode = location.next_.next_; location.next_ = sucNode; sucNode.prev_ = location; return retNode; } @Override public Node search(T item) { Node scanNode = head_; while (scanNode != null) { if (scanNode.item_ == item) { return scanNode; } scanNode = scanNode.next_; } return null; } public void insertionSort() { // If we have no nodes or exactly one, there's nothing to do if (head_ == null || head_.next_ == null) return;

// Start from the second node Node curNode = head_.next_; while (curNode != null) { Node prevCur = curNode.prev_; Node scanNode = prevCur; while (scanNode != null) { T curItem = curNode.item_; T scanItem = scanNode.item_; if (scanItem.compareTo(curItem) <= 0) { // remove curNode // put curNode after scanNode Node removedNode = removeAfter(prevCur); insertAfter(scanNode, removedNode.item_); break; } scanNode = scanNode.prev_; } if (scanNode == null) { Node removedNode = removeAfter(prevCur); prepend(removedNode.item_); } curNode = curNode.next_; } // Scan rightward for a node that's <= than the node at the right edge of the // already sorted list; then swap } public static void main(String[] args) { DoublyLinkedList sList = new DoublyLinkedList(); sList.append("alpha"); sList.append("beta"); sList.append("gamma"); sList.append("delta"); sList.prepend("epsilon"); sList.prepend("phi"); sList.prepend("kappa"); sList.prepend("mu"); System.out.println(sList); Node alphaNode = sList.search("alpha"); Node removedNode = sList.removeAfter(alphaNode); System.out.println("*************************** " + sList + "\ n******************* " + removedNode + " --------------------------- ");