1
\$\begingroup\$

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;
}

}
\$\endgroup\$
  • \$\begingroup\$ You are taking an index-based approach to a problem in which there is no use of index at all. In _sort(..), you call list.listIterator(index) every time and it in turn calls findNode(..) 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\$ – sonnet Dec 18 '16 at 18:23
  • 1
    \$\begingroup\$ @sonnet I rewrote the algorithm based on your comment and it passes the speed test :) you should write an answer. \$\endgroup\$ – MikeJava Dec 18 '16 at 23:06
1
\$\begingroup\$

You are taking an index-based approach to a problem in which there is no use of index at all. In _sort(..), you call list.listIterator(index) every time and it in turn calls findNode(..) which is \$O(n)\$. This dramatically increases your runtime. I don't see any other reason for the overall \$O(n^2)\$ runtime. Take a look at the classical merge sort for linked lists.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.