Think Data Structures

Chapter 4. LinkedList

This chapter presents solutions to the previous exercise and continues the discussion of analysis of algorithms.

Classifying MyLinkedList Methods

My implementation of indexOf is the following code snippet. Read through it and see if you can identify its order of growth before you read the explanation:

    public int indexOf(Object target) {
        Node node = head;
        for (int i=0; i<size; i++) {
            if (equals(target, node.data)) {
                return i;
            }
            node = node.next;
        }
        return -1;
    }

Initially node gets a copy of head, so they both refer to the same Node. The loop variable, i, counts from 0 to size-1. Each time through the loop, we use equals to see if we’ve found the target. If so, we return i immediately. Otherwise we advance to the next Node in the list.

Normally we would check to make sure the next Node is not null, but in this case it is safe because the loop ends when we get to the end of the list (assuming size is consistent with the actual number of nodes in the list).

If we get through the loop without finding the target, we return -1.

So what is the order of growth for this method?

1. Each time through the loop we invoke equals, which is constant time (it might depend on the size of target or data, but it doesn’t depend on the size of the list). The other operations in the loop are also constant time.

2. The loop might run n times, because in the worse case, we might have to traverse the whole list.

So the runtime of this method is proportional to the length of the list.

Next, here ...