The LinkedList code is: import java.util.NoSuchElementException; import java.uti

Question

The LinkedList code is: import java.util.NoSuchElementException; import java.util.Comparator; import java.util.Iterator; import java.util.Iterator;
public interface ReadonlyList<T> extends Iterable<T> { T get(int index); int size(); } public class LinkedList<T> implements List<T> { private ListNode<T> header = new ListNode<T>();    public boolean isEmpty() { return header.getNext() == null; }    public T getFirst() { ListNode<T> first = header.getNext(); if (first == null) { throw new EmptyListException(); } else { return first.getValue(); } }    public void addFirst(T element) { // Create a new node ListNode<T> newNode = new ListNode<T>();    // 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<T> first = header.getNext(); if (first == null) { throw new EmptyListException(); } else { header.setNext(first.getNext()); } }    public void clear() { header.setNext(null); }    private ListNode<T> findByIndex(int index) { int k = 0; ListNode<T> 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<T> 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<T> iterator) { int k = -1;
while (iterator.hasNext()) { k++; iterator.next(); } }    public void add(int index, T element) { ListIterator<T> iterator = listIterator(); scanToIndex(iterator, index - 1); iterator.add(element); }    public void addLast(T element) { ListIterator<T> iterator = listIterator(); scanToEnd(iterator); iterator.add(element); }    public void remove(int index) { ListIterator<T> iterator = listIterator(); scanToIndex(iterator, index); iterator.remove(); }    public void removeLast() { ListIterator<T> iterator = listIterator(); scanToEnd(iterator); iterator.remove(); }    public int size() { int k = 0; ListNode<T> current = header.getNext();
while (current != null) { k++; current = current.getNext(); }    return k; }    public String toString() { ListNode<T> 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<T> c) { // This is part of written assignment 3! throw new UnsupportedOperationException(); }    public LinkedListIterator<T> iterator() { return new LinkedListIterator<T>(header); }    public LinkedListIterator<T> listIterator() { return new LinkedListIterator<T>(header); } } import java.util.NoSuchElementException; import java.util.Comparator; import java.util.Iterator; import java.util.Iterator;
public interface ReadonlyList<T> extends Iterable<T> { T get(int index); int size(); } import java.util.Iterator;
public interface ReadonlyList<T> extends Iterable<T> { T get(int index); int size(); } public class LinkedList<T> implements List<T> { private ListNode<T> header = new ListNode<T>();    public boolean isEmpty() { return header.getNext() == null; }    public T getFirst() { ListNode<T> first = header.getNext(); if (first == null) { throw new EmptyListException(); } else { return first.getValue(); } }    public void addFirst(T element) { // Create a new node ListNode<T> newNode = new ListNode<T>();    // 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<T> first = header.getNext(); if (first == null) { throw new EmptyListException(); } else { header.setNext(first.getNext()); } }    public void clear() { header.setNext(null); }    private ListNode<T> findByIndex(int index) { int k = 0; ListNode<T> 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<T> 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<T> iterator) { int k = -1;
while (iterator.hasNext()) { k++; iterator.next(); } }    public void add(int index, T element) { ListIterator<T> iterator = listIterator(); scanToIndex(iterator, index - 1); iterator.add(element); }    public void addLast(T element) { ListIterator<T> iterator = listIterator(); scanToEnd(iterator); iterator.add(element); }    public void remove(int index) { ListIterator<T> iterator = listIterator(); scanToIndex(iterator, index); iterator.remove(); }    public void removeLast() { ListIterator<T> iterator = listIterator(); scanToEnd(iterator); iterator.remove(); }    public int size() { int k = 0; ListNode<T> current = header.getNext();
while (current != null) { k++; current = current.getNext(); }    return k; }    public String toString() { ListNode<T> 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<T> c) { // This is part of written assignment 3! throw new UnsupportedOperationException(); }    public LinkedListIterator<T> iterator() { return new LinkedListIterator<T>(header); }    public LinkedListIterator<T> listIterator() { return new LinkedListIterator<T>(header); } } 2. [20 points] 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 (Tl] a, Comparator c) boolean swapped true: int limit = a.length; while (1imit 1 && swapped) swapped-false,; int j-0 while (j + 1 != limit) if (c.compare (alj+1, alj)0) swapped-true Ttemp = a[j +1]; a [j] = temp ; j++i limit-

Explanation / Answer

---------------------Code------------------

public void sort(Comparator<T> c)

{

boolean swapped = true;

int limit = size();

if(limit==0)

return;

while(limit!=1 && swapped){

swapped = false;

int j = 0;

ListNode<T> current = header.getNext();

while(j+1 != limit){

T next = current.getNext().getValue();

T curr = current.getValue();

if(c.compare(next,curr) < 0){

swapped = true;

current.setValue(next);

current.getNext().setValue(curr);

}

j++;

current = current.getNext();

}

limit = j;

}

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.