I implemented merge sort with my own linked list for a school project. I was not allowed to use anything but the methods you see in the list. It seems to work properly, however, when running the provided testbed, I am told that the implementation is likely \$O(n^2)\$.
I've looked for a long time trying to find where my implementation is \$O(n^2)\$ but have had no luck. I would appreciate:
- any input on the quality of the implementation
- any information on why the implementation is so inefficient
public class Sort {
public static <T extends Comparable<T>> void sort(IUListWithListIterator<T> list) {
_sort(list, 0, list.size() - 1);
}
public static <T extends Comparable<T>> void _sort(IUListWithListIterator<T> list, int low, int high) {
if (low < high) {
int middle = (low + high) / 2;
_sort(list, low, middle);
_sort(list, middle + 1, high);
merge(list, low, middle, high);
}
}
private static <T extends Comparable<T>> void merge(IUListWithListIterator<T> list, int low, int middle, int high) {
IUListWithListIterator<T> temp = new IUDoubleLinkedList<T>();
ListIterator<T> left = list.listIterator(middle);
ListIterator<T> right = list.listIterator(high);
while (left.previousIndex() + 1 >= low && right.previousIndex() + 1 > middle) {
T l = left.previous();
T r = right.previous();
if (l.compareTo(r) > 0) {
temp.addToFront(l);
right.next();
}
else {
temp.addToFront(r);
left.next();
}
}
while (left.previousIndex() + 1 >= low) {
temp.addToFront(left.previous());
}
while (right.previousIndex() + 1 > middle) {
temp.addToFront(right.previous());
}
ListIterator<T> tempIter = temp.listIterator();
left.next();
while(tempIter.hasNext()) {
left.set(tempIter.next());
left.next();
}
}
}
import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;
public class IUDoubleLinkedList<T> implements IndexedUnorderedList<T>, IUListWithListIterator<T> {
private Node head;
private Node tail;
private int size;
public IUDoubleLinkedList() {
head = new Node(null, null, null);
tail = new Node(null, head, null);
head.setNext(tail);
size = 0;
}
public T removeFirst() {
if (size == 0) {
throw new IllegalStateException("Empty list");
}
Node first = head.getNext();
removeNode(first);
return first.getData();
}
public T removeLast() {
if (size == 0) {
throw new IllegalStateException("Empty list");
}
Node last = tail.getPrev();
removeNode(last);
return last.getData();
}
public T remove(T element) {
Node target = findNode(element);
if (target == null) {
throw new NoSuchElementException("Element " + element + " not in list");
}
removeNode(target);
return target.getData();
}
public T first() {
if (size == 0) {
throw new IllegalStateException("Empty list");
}
return head.getNext().getData();
}
public T last() {
if (size == 0) {
throw new IllegalStateException("Empty list");
}
return tail.getPrev().getData();
}
public boolean contains(T target) {
Node found = findNode(target);
return found == null ? false : true;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public String toString() {
StringBuilder b = new StringBuilder();
if (size == 0) {
b.append("[]");
}
else {
b.append("[");
Node currentNode = head.getNext();
while (currentNode != tail) {
b.append(currentNode.getData().toString() + ", ");
currentNode = currentNode.getNext();
}
if (b.length() > 3) {
b = new StringBuilder(b.substring(0, b.length() - 2));
}
b.append("]");
}
return b.toString();
}
public void addToFront(T element) {
addNode(new Node(element), head, head.getNext());
}
public void addToRear(T element) {
addNode(new Node(element), tail.getPrev(), tail);
}
public void addAfter(T element, T target) {
Node targetNode = findNode(target);
if (targetNode == null) {
throw new NoSuchElementException("Element " + target + " not in list");
}
addNode(new Node(element), targetNode, targetNode.getNext());
}
public void add(int index, T element) {
if (index > size || index < 0) {
throw new IndexOutOfBoundsException(index + " is out of bounds");
}
else if (index == 0) {
addToFront(element);
return;
}
else if (index == size) {
addToRear(element);
}
else {
Node targetNode = findNode(index);
addNode(new Node(element), targetNode.getPrev(), targetNode);
}
}
public void set(int index, T element) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException(index + " is out of bounds");
}
Node setNode = findNode(index);
Node newNode = new Node(element, setNode.getPrev(), setNode.getNext());
setNode.getPrev().setNext(newNode);
setNode.getNext().setPrev(newNode);
}
public void add(T element) {
addNode(new Node(element), tail.getPrev(), tail);
}
public T get(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException(index + " is out of bounds");
}
Node target = findNode(index);
return target.getData();
}
public int indexOf(T element) {
int i = 0;
Node currentNode = head.getNext();
while (currentNode != tail) {
if (currentNode.getData().equals(element)) {
return i;
}
currentNode = currentNode.getNext();
i++;
}
return -1;
}
public T remove(int index) {
if (index > size - 1 || index < 0) {
throw new IndexOutOfBoundsException(index + " is out of bounds");
}
Node targetNode = findNode(index);
removeNode(targetNode);
return targetNode.getData();
}
public Iterator<T> iterator() {
return new DLLIterator();
}
private class DLLIterator implements Iterator<T> {
private Node next;
private DLLIterator() {
next = head.getNext();
}
private DLLIterator(int index) {
next = findNode(index);
}
public boolean hasNext() {
return next != tail;
}
public T next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
next = next.getNext();
return next.getPrev().getData();
}
public void remove() {
removeNode(next.getPrev());
}
}
public ListIterator<T> listIterator() {
return new DLLListIterator<T>();
}
public ListIterator<T> listIterator(int startingIndex) {
return new DLLListIterator<T>(startingIndex);
}
private class DLLListIterator<E> implements ListIterator<T> {
Node current;
Node last;
int index;
private DLLListIterator() {
current = head.getNext();
last = null;
index = 0;
}
private DLLListIterator(int startingIndex) {
current = findNode(startingIndex);
index = startingIndex;
}
public boolean hasNext() {
return current != tail;
}
public T next() {
if (current.getNext() == last) {
current = last.getNext();
index++;
return last.getData();
}
last = current;
current = current.getNext();
index++;
return last.getData();
}
public void remove() {
if (last == null) {
throw new IllegalStateException("can't call remove() before calling next() or previous()");
}
removeNode(last);
last = null;
index--;
}
public boolean hasPrevious() {
return current != head;
}
public T previous() {
if (last != null && last.getNext() == current) {
current = last.getPrev();
index--;
return last.getData();
}
last = current;
current = current.getPrev();
index--;
return last.getData();
}
public void add(T element) {
if (last == null) {
addNode(new Node(element), current.getPrev(), current);
}
else if (last.getNext() == current) {
addNode(new Node(element), last, current);
}
else if (current.getNext() == last) {
addNode(new Node(element), current, last);
}
index++;
}
public void set(T element) {
if (last == null) {
throw new IllegalStateException("can't call set(T) before calling next() or previous()");
}
last.setData(element);
}
public int nextIndex() {
return index + 1;
}
public int previousIndex() {
return index - 1;
}
}
private class Node {
private Node prev;
private Node next;
private T data;
public Node(T data, Node before, Node after) {
this.prev = before;
this.next = after;
this.data = data;
}
public Node(T data) {
this.data = data;
}
public Node getPrev() {
return prev;
}
public void setPrev(Node n) {
prev = n;
}
public Node getNext() {
return next;
}
public void setNext(Node n) {
next = n;
}
public T getData() {
return data;
}
public void setData(T d) {
data = d;
}
}
private void addNode(Node n, Node before, Node after) {
before.setNext(n);
after.setPrev(n);
n.setNext(after);
n.setPrev(before);
size++;
}
private void removeNode(Node n) {
if (n == head) {
throw new IllegalStateException("Can't remove the head of the list");
}
if (n == tail) {
throw new IllegalStateException("Can't remove the tail of the list");
}
n.getPrev().setNext(n.getNext());
n.getNext().setPrev(n.getPrev());
size--;
}
private Node findNode(T target) {
Node currentNode = head.getNext();
while (currentNode != tail) {
if (currentNode.getData() == target) {
return currentNode;
}
//System.out.println(currentNode.getData());
currentNode = currentNode.getNext();
}
return null;
}
private Node findNode(int index) {
if (index > size || index < 0) {
throw new IndexOutOfBoundsException();
}
if (index == size) {
return tail;
}
Node currentNode = head.getNext();
for (int i = 0; i < index; i++) {
currentNode = currentNode.getNext();
}
return currentNode;
}
}
_sort(..), you calllist.listIterator(index)every time and it in turn callsfindNode(..)which is O(n). This dramatically inscreases your runtime. I don't see any other reason for the O(n^2) runtime. Take a look at the classical merge sort for linkedlists. \$\endgroup\$