A non-static void method calledsort that takes no parameters. Its goal is to sort the list in ascending order bykey. It will use an outer loop that continues until it is sure the list is sorted (for which you will need a boolean variable.) Inside this loop it then iterates through this list (starting at the head) and swaps any nodes that are out of order. If any swaps were needed, it records that the list is not sorted and continues the outer loop. It can stop the outer loop when an iteration through the list finishes without any swaps. *****************************************************

CODE public class LinkedList { public static class Node{ String key; int value; Node next; Node prev; public Node(String key, int value) { this.key = key; this.value = value; } public Node getNext() { return next; } public Node getPrev() { return prev; } public String getKey() { return key; } public int getValue() { return value; } } private Node head; private Node tail; public LinkedList() { head = null; tail = null; } public Node getHead() { return head; } public Node getTail() { return tail; } public void addHead(String key, int val) { Node n = new Node(key, val); if (head == null) { head = n; tail = n; } else { head.prev = n; n.next = head; head = n; } } public void addTail(String key, int val) { Node n = new Node(key, val); if (tail == null) { head = n; tail = n; } else { tail.next = n; n.prev = tail; tail = n; } } public String toString() { StringBuilder ret = new StringBuilder(); Node curr = head; while (curr != null) { if (curr.next != null) { ret.append(curr.key).append(":").append(curr.value).append(", "); } else { ret.append(curr.key).append(":").append(curr.value); } curr = curr.next; } return ret.toString(); } public Node find(String key) { Node curr = head; while (curr != null) { if (curr.key.equals(key)) { return curr; } curr = curr.next; } return null; } /* If the node is head then we are simply moving head to next position and making its prev to null, so it will be new head. If it's tail, then we are making its previous node's next to null and making it prev. If not either of them, we are linking its previous node, and it's next node by changing the links between them like this n.prev.next = n.next; n.next.prev = n.prev; */ public void unlinkNode(Node n) { if (n == head) { head = head.next; head.prev = null; } else if (n == tail) { n.prev.next = null; tail = n.prev; } else { n.prev.next = n.next; n.next.prev = n.prev; } } /*If Node before is tail then we are simply adding node to next of it and making the new node we just added to tail. If Node before is not tail, then we are adding this node in between the before node, and it's next node by simply changing the links. we are storing the next node from before and then adding it next to before and adding this previous stored to the next of the newly added nodes. Similarly, we are storing the prev values also to maintain a proper connection between them. */ public void addAfter(Node n, Node before) { if (before == tail) { tail.next = n; n.prev = tail; n.next = null; tail = n; } else { Node next = before.next; before.next = n; n.prev = before; n.next = next; next.prev = n; } } /* Here we are checking if the present nodes values are greater than the next nodes value, and if the value is greater than the next node value, we are simply swapping both of these nodes. If the node is tail then we don't swap it as it is the final node, and we return false. If we have done swapping the nodes, we will return true. */ public Boolean swapIfNeeded(Node n) { if (n == tail) { return false; } else { if (n.value > n.next.value) { Node temp = n.next; unlinkNode(n); addAfter(n, temp); return true; } return false; } }

/* enter code for sort() here

*/ }

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

example of what the expected results should look like:

List: hl:58, ci:41, ah:13, ah:63, ai:9, id:70, ah:32, id:92

Expected: ah:13, ah:63, ah:32, ai:9, ci:41, hl:58, id:70, id:92