0

For a project I am required to write a method that times the traversal of a LinkedList filled with 5 million random Integers using a listIterator, then with LinkedList's get(index) method.

I had no problem traversing it with the listIterator and it completed in around 75ms. HOWEVER, after trying the get method traversal on 5 million Integers, I just stopped the run at around 1.5 hours.

The getTraverse method I used is something like the code below for example (however mine was grouped with other methods in a class and was non-static, but works the same way).

public static long getTraverse(LinkedList<Integer> list) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < linkedList.size(); i++) {
        linkedList.get(i);
    }
    long stop = System.currentTimeMillis();
    return stop - start;
}

This worked perfectly fine for LinkedLists of Integers of sizes 50, 500, 5000, 50000, and took quite a while but completed for 500000.

My professor tends to be extremely vague with instructions and very unhelpful when approached with questions. So, I don't know if my code is broken, or if he got carried away with the Integers in the guidelines. Any input is appreciated.

dimo414
  • 47,227
  • 18
  • 148
  • 244
Cole Dooley
  • 47
  • 1
  • 7
  • 2
    The lesson your instructor is trying to teach you, is that `LinkedList`s are very slow with large numbers of values. There isn't a random access method. To `get(n)` it has to start with with the first element and iterate to `n`. – Elliott Frisch Feb 17 '17 at 01:13
  • Okay just making sure then! I assumed it would take a very long time but thought I must be doing something wrong to wait for hours. My last project took 30 minutes to run. That makes sense! – Cole Dooley Feb 17 '17 at 01:16
  • I'm wondering if something is missing from the problem statement. The random numbers won't affect list traversal time. However, if the list with random numbers is sorted (assuming that only the links are updated), then then traversal of the list will involve non-cache friendly random access of memory, which would significantly increase the time it would take for traversal. – rcgldr Feb 17 '17 at 01:22
  • When you're unsure if there's a bug in your code it's useful to share a complete [MCVE](http://stackoverflow.com/help/mcve) (rather than just a single method) so that we can run it and replicate what you're seeing. In this case it's fairly clear that the issue stems from calling `LinkedList.get()` in a loop, but "*I don't know if my code is broken*" questions can be best answered if you share the exact code in question. – dimo414 Feb 17 '17 at 01:29
  • Related (not a dupe, imo): http://stackoverflow.com/q/10656471/113632 – dimo414 Feb 17 '17 at 01:32

2 Answers2

1

A LinkedList is optimised for insertion, which is a constant time operation.

Searching a LinkedList requires you to iterate over every element to find the one you want. You provide the index to the get method, but under the covers it is traversing the list to that index.

If you add some print statements, you'll probably see that the first X elements are retrieved pretty fast and it slows down over time as you index elements further down the list.

An ArrayList (backed by an array) is optimised for retrieval and can index the desired element in constant time. Try changing your code to use an ArrayList and see how much faster get runs.

Matt
  • 3,677
  • 1
  • 14
  • 24
  • Great! I'll try implementing it on an ArrayList. I figured the get traversal would be slow, but did not expect exactly how slow. I even added a prompt to skip the get traversal altogether while testing it out of frustration haha. – Cole Dooley Feb 17 '17 at 01:34
1

Think about how a LinkedList is implemented - as a chain of nodes - and you'll see that to get to a particular node you have to start at the head and traverse to that node.

You're calling .get() on a LinkedList n times, which requires traversing the list until it reaches that index. This means your getTraverse() method takes O(n^2) (or quadratic) time, because for each element it has to traverse (part of) the list.

As Elliott Frisch said, I suspect you're discovering exactly what your instructor wanted you to discover - that different algorithms can have drastically different runtimes, even if in principle they do the same thing.

dimo414
  • 47,227
  • 18
  • 148
  • 244
  • Ahh yes I definitely discovered that! I guess I was being impatient because the execution time seemed excessive. After studying Big-O, I guess I could have predicted the horrendously long runtime. Just going to let it run now. – Cole Dooley Feb 17 '17 at 01:39
  • @ColeDooley Here's a follow-on question to ponder. LinkedList contains an optimization to get(n) which is that if n is closer to the end of the list, the traversal starts from the end and proceeds backwards. This is a great optimization, because on average it cuts the search time in half! Explain what impact this has on the Big-O analysis. – Stuart Marks Feb 17 '17 at 16:48