java the linked list code is 2. [20 points] Write an implementation of bubble so
ID: 3914732 • Letter: J
Question
java
the linked list code is
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,; while (j + 1 != limit) if (c.compare (alj+1, a j)0) swapped-true T temp alj 11 a[j] = temp ; j++i limitExplanation / Answer
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts. Thanks
// LinkedList.java (modified)
import java.util.Comparator;
import java.util.NoSuchElementException;
import java.util.Iterator;
public class LinkedList<T> implements ReadonlyList<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 NoSuchElementException("List is empty, no item to get!");
} else {
return first.getValue();
}
}
public void addFirst(T value) {
// Create a new node
ListNode<T> newNode = new ListNode<T>();
// Store the new value in the new node
newNode.setValue(value);
// 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 NoSuchElementException(
"List is empty, no item to remove!");
} else {
header.setNext(first.getNext());
}
}
public T get(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.getValue();
}
}
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();
}
}
/**
* method to sort the list by using the given comparator
*
* @param c
* - comparator which tells how the elements should be sorted
*/
public void sort(Comparator<T> c) {
/**
* using the bubble sort algorithm you mentioned in the image
*/
boolean swapped = true;
int limit = size();
while (limit != 1 && swapped) {
swapped = false;
int j = 0;
while (j + 1 != limit) {
// comparing values of nodes at j+1 and j
if (c.compare(get(j + 1), get(j)) < 0) {
swapped = true;
// getting value at j+1
T temp = get(j + 1);
// setting the value at j+1 to value at j
set(j + 1, get(j));
// setting value at j to temp
set(j, temp);
}
j++;
}
limit = j;
}
}
/**
* a private helper method defined to assist the above sort method, so that
* the sort method doesn't look messy. This method sets the value of node at
* given index to the given value
*
* @param index
* - index of node
* @param value
* - new value
*/
private void set(int index, T value) {
int k = 0;
ListNode<T> current = header.getNext();
while (k < index && current != null) {
k++;
current = current.getNext();
}
if (current != null) {
current.setValue(value);
}
}
/**
* As you have not provided the LinkedListIterator class, I'm commenting it
*/
/*
* public LinkedListIterator<T> iterator() { return new
* LinkedListIterator<T>(header); }
*/
/**
* as per the interface, you have to implement iterator() method according
* to this syntax, I'm doing nothing as it is not mentioned
*/
@Override
public Iterator<T> iterator() {
return null;
}
}
// ReadonlyList.java (as the interface is public it should be declared as a separate .java file)
import java.util.Iterator;
public interface ReadonlyList<T> {
T get(int index);
int size();
Iterator<T> iterator();
}
// Test.java (used to test the new sort method)
import java.util.Comparator;
public class Test {
public static void main(String[] args) {
/**
* creating an integer list and adding some values
*/
LinkedList<Integer> intList = new LinkedList<Integer>();
intList.addFirst(123);
intList.addFirst(3);
intList.addFirst(-22);
intList.addFirst(73);
intList.addFirst(100);
intList.addFirst(20);
/**
* displaying list
*/
System.out.println("List: " + intList);
/**
* sorting the list using an anonymous comparator class which sorts
* integers in ascending order
*/
intList.sort(new Comparator<Integer>() {
@Override
public int compare(Integer i1, Integer i2) {
return i1.compareTo(i2);
}
});
/**
* displaying sorted list
*/
System.out.println("Sorted List: " + intList);
}
}
/*OUTPUT*/
List: [20, 100, 73, -22, 3, 123]
Sorted List: [-22, 3, 20, 73, 100, 123]
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.