Write an implementation of bubble sort as an instance method called sort() for the LinkedList class developed in lecture. sort()should take a Comparator as a parameter. You may not use arrays in your implementation. Hint 1: The simplest solution to this question will not involve changing the structure of the linked list. That is, the values in the linked list may change, but the links between nodes will not change. Hint 2: You may find it helpful to refer to the following alternative implementation of bubble sort over arrays as a reference for your implementation over linked lists.

public static void bubbleSort(T[] a, Comparator c) { boolean swapped = true; int limit = a.length; while (limit != 1 && swapped) { swapped = false; int j = 0; while (j + 1 != limit) { if (c.compare(a[j + 1], a[j]) < 0) { swapped = true; T temp = a[j + 1]; a[j + 1] = a[j]; a[j] = temp; } j++; } limit = j; } }

import java.util.NoSuchElementException; import java.util.Comparator; import java.util.Iterator; public class LinkedList implements List { private ListNode header = new ListNode(); public boolean isEmpty() { return header.getNext() == null; } public T getFirst() { ListNode first = header.getNext(); if (first == null) { throw new EmptyListException(); } else { return first.getValue(); } } public void addFirst(T element) { // Create a new node ListNode newNode = new ListNode(); // Store the new element in the new node newNode.setValue(element); // Link the new node to the old first node newNode.setNext(header.getNext()); // Set the new node as the first node header.setNext(newNode); } public void removeFirst() { ListNode first = header.getNext(); if (first == null) { throw new EmptyListException(); } else { header.setNext(first.getNext()); } } public void clear() { header.setNext(null); } private ListNode findByIndex(int index) { int k = 0; ListNode current = header.getNext(); while (k < index && current != null) { k++; current = current.getNext(); } if (current == null) { throw new IndexOutOfBoundsException( "Index: " + index + ", Size: " + k); } else { return current; } } public T get(int index) { return findByIndex(index).getValue(); } public void set(int index, T element) { findByIndex(index).setValue(element); } private void scanToIndex(Iterator iterator, int index) { int k = -1; while (k < index && iterator.hasNext()) { k++; iterator.next(); } if (k < index) { throw new IndexOutOfBoundsException( "Index: " + index + ", Size: " + (k + 1)); } } private void scanToEnd(Iterator iterator) { int k = -1; while (iterator.hasNext()) { k++; iterator.next(); } } public void add(int index, T element) { ListIterator iterator = listIterator(); scanToIndex(iterator, index - 1); iterator.add(element); } public void addLast(T element) { ListIterator iterator = listIterator(); scanToEnd(iterator); iterator.add(element); } public void remove(int index) { ListIterator iterator = listIterator(); scanToIndex(iterator, index); iterator.remove(); } public void removeLast() { ListIterator iterator = listIterator(); scanToEnd(iterator); iterator.remove(); } public int size() { int k = 0; ListNode current = header.getNext(); while (current != null) { k++; current = current.getNext(); } return k; } public String toString() { ListNode current = header.getNext(); if (current == null) { return "[]"; } else { StringBuilder stringBuilder = new StringBuilder("["); stringBuilder.append(current.getValue()); while(current.getNext() != null) { stringBuilder.append(", "); current = current.getNext(); stringBuilder.append(current.getValue()); } stringBuilder.append("]"); return stringBuilder.toString(); } } public void sort(Comparator c) { // This is part of written assignment 3! throw new UnsupportedOperationException(); } public LinkedListIterator iterator() { return new LinkedListIterator(header); } public LinkedListIterator listIterator() { return new LinkedListIterator(header); } }