ArrayList Vs LinkedList

by

Remember that big-O complexity describes asymptotic behaviour and may not reflect actual implementation speed. It describes how the cost of each operation grows with the size of the list, not the speed of each operation. For example, the following implementation of add is O(1) but is not fast:

public class MyList extends LinkedList {
    public void add(Object o) {
        Thread.sleep(10000);
        super.add(o);
    }
}

I suspect in your case ArrayList is performing well because it increases it’s internal buffer size fairly aggressively so there will not be a large number of reallocations. When the buffer does not need to be resized ArrayList will have faster adds.

You also need to be very careful when you do this kind of profiling. I’d suggest you change your profiling code to do a warm-up phase (so the JIT has the opportunity to do some optimization without affecting your results) and average the results over a number of runs.

private final static int WARMUP = 1000;
private final static int TEST = 1000;
private final static int SIZE = 500000;

public void perfTest() {
    // Warmup
    for (int i = 0; i < WARMUP; ++i) {
        buildArrayList();
    }
    // Test
    long sum = 0;
    for (int i = 0; i < TEST; ++i) {
        sum += buildArrayList();
    }
    System.out.println("Average time to build array list: " + (sum / TEST));
}

public long buildArrayList() {
    long start = System.nanoTime();
    ArrayList a = new ArrayList();
    for (int i = 0; i < SIZE; ++i) {
        a.add(i);
    }
    long end = System.nanoTime();
    return end - start;
}

... same for buildLinkedList

(Note that sum may overflow and you might be better to use System.currentTimeMillis()).

It’s also possible that the compiler is optimizing away your empty get loops. Make sure the loop actually does something to ensure that the right code is getting called.

More Related Contents:

  1. When to use LinkedList over ArrayList in Java?
  2. Best way to create a hashmap of arraylist
  3. ArrayList vs LinkedList from memory allocation perspective
  4. Initialization of an ArrayList in one line
  5. How do I remove repeated elements from ArrayList?
  6. Sorting an ArrayList of objects using a custom sorting order
  7. Converting ‘ArrayList to ‘String[]’ in Java
  8. How to count the number of occurrences of an element in a List
  9. How to find an object in an ArrayList by property
  10. How to sort an ArrayList in Java [duplicate]
  11. Which Java Collection should I use?
  12. How to detect a loop in a linked list?
  13. How to randomize two ArrayLists in the same fashion?
  14. Reversing a linked list in Java, recursively
  15. How do I make my ArrayList Thread-Safe? Another approach to problem in Java?
  16. Why start an ArrayList with an initial capacity?
  17. How do I create a Linked List Data Structure in Java? [closed]
  18. How to sort an ArrayList using multiple sorting criteria?
  19. What is the best way to combine two lists into a map (Java)?
  20. Add multiple items to an already initialized arraylist in Java
  21. How to remove element from ArrayList by checking its value?
  22. Empty an ArrayList or just create a new one and let the old one be garbage collected? [duplicate]
  23. ArrayList filter [duplicate]
  24. Why doesn’t java.util.Set have get(int index)?
  25. ArrayList: how does the size increase?
  26. What is the Simplest Way to Reverse an ArrayList?
  27. Automatically sorted by values map in Java
  28. Creating a LinkedList class from scratch
  29. Vector vs Collections.synchronizedList(ArrayList)
  30. How to remove common values from two array lists

Leave a Comment