CODEWITHSUNDEEP
javalinked-list
waddington
waddington

Reputation: 365

Why doesn't this algorithm for reversing a LinkedList in java fit θ(N)?

A question on an assignment that I have is to write an algorithm to reverse a LinkedList producing a new list in θ(N) time.

The code I have come up with does not meet the time requirements and I cannot work out why.

public Node reverse() {

    if (this == Node.NIL) {
        return Node.NIL;
    }

    if (this.getNext() == Node.NIL) {
        return new Node(this.getItem(), this.getNext());
    }

    Node curNode = new Node(this.getItem(), this.getNext());
    Node front = curNode;

    Node nextNode = null;
    Node prevNode = null;

    while (curNode.getNext() != Node.NIL) {
        nextNode = new Node(curNode.next.item, curNode.next.next);
        curNode.next = prevNode;
        prevNode = curNode;
        curNode = nextNode;
    }

    curNode.next = prevNode;
    front.setNext(Node.NIL);
    return curNode;
}

There is a node called NIL which should be referred to as Node.NIL which is always the first node created in the provided lists to reverse, so if Node.NIL is the next node you will be at the end of the list.

Each node has 2 attributes, "next" and "item" - "next" being the next node in the list, and "item" being the data it carries which is an Object in this case.

This is the test that is being used (NCASES = 20):

@Test
public void testReverseTiming() {
    int i;
    long diff = 0;
    for (i = 0; i < NCASES - 1; i++) {
        long start = System.nanoTime();
        Node result = nodes2[i].reverse();
        long end = System.nanoTime();
        diff = end - start;
        if (diff/1000000 > 250) {
            i++;
            break;
        }
    }
    long start = System.nanoTime();
    Node result = nodes2[i].reverse();
    long end = System.nanoTime();
    long diff2 = end - start;
    double ratio = (double) diff2 / (double) diff;
    assertTrue("reverse should scale linearly with list size", ratio > 1.2);
    assertTrue("reverse should scale linearly with list size", ratio < 2.5);
}

The ratio that my code produces ranges from 25 to 35 whereas it needs to be between 1.2 and 2.5.

Upvotes: 0

Views: 71

Answers (1)

Rolf Rander
Rolf Rander

Reputation: 3321

Since your code seems to iterate through the list only once, it seems to be, infact, O(n).

However, you allocate objects inside your look (new Node()), so the actual performance will depend on memory allocation (which will include OS-calls for large datasets) and garbage collection. Both of which takes an undetermined amount of time. This means that even if the algorithm (in theory) is O(n), the measured runtimes will depend on other factors than n.

You should try to rewrite your algorithm to change the links of existing nodes instead of creating new nodes. (I assume the assignment is to reverse the existing list in place, not create a reversed copy of the list)

Upvotes: 3

Related Questions