java linkedlist slower than arraylist when adding elements?

Question

i thought linkedlists were supposed to be faster than an arraylist when adding elements? i just did a test of how long it takes to add, sort, and search for elements (arraylist vs linkedlist vs hashset). i was just using the java.util classes for arraylist and linkedlist...using both of the add(object) methods available to each class.

arraylist out performed linkedlist in filling the list...and in a linear search of the list.

is this right? did i do something wrong in the implementation maybe?

***************EDIT*****************

i just want to make sure i'm using these things right. here's what i'm doing:

public class LinkedListTest {

    private List<String> Names;

    public LinkedListTest(){
            Names = new LinkedList<String>();
    }

Then I just using linkedlist methods ie "Names.add(strings)". And when I tested arraylists, it's nearly identical:

public class ArrayListTest {

    private List<String> Names;

    public ArrayListTest(){
            Names = new ArrayList<String>();
    }

Am I doing it right?

Answer 1

Yes, that's right. LinkedList will have to do a memory allocation on each insertion, while ArrayList is permitted to do fewer of them, giving it amortized O(1) insertion. Memory allocation looks cheap, but may be actually be very expensive.

The linear search time is likely slower in LinkedList due to locality of reference: the ArrayList elements are closer together, so there are fewer cache misses.

When you plan to insert only at the end of a List, ArrayList is the implementation of choice.

Answer 2

Remember that:

• there's a difference in "raw" performance for a given number of elements, and in how different structures scale;
• different structures perform differently at different operations, and that's essentially part of what you need to take into account in choosing which structure to use.

So, for example, a linked list has more to do in adding to the end, because it has an additional object to allocate and initialise per item added, but whatever that "intrinsic" cost per item, both structures will have O(1) performance for adding to the end of the list, i.e. have an effectively "constant" time per addition whatever the size of the list, but that constant will be different between ArrayList vs LinkedList and likely to be greater for the latter.

On the other hand, a linked list has constant time for adding to the beginning of the list, whereas in the case of an ArrayList, the elements must be "shuftied" along, an operation that takes some time proportional to the number of elements. But, for a given list size, say, 100 elements, it may still be quicker to "shufty" 100 elements than it is to allocate and initialise a single placeholder object of the linked list (but by the time you get to, say, a thousand or a million objects or whatever the threshold is, it won't be).

So in your testing, you probably want to consider both the "raw" time of the operations at a given size and how these operations scale as the list size grows.

Answer 3

Why did you think LinkedList would be faster? In the general case, an insert into an array list is simply a case of updating the pointer for a single array cell (with O(1) random access). The LinkedList insert is also random access, but must allocate an "cell" object to hold the entry, and update a pair of pointers, as well as ultimately setting the reference to the object being inserted.

Of course, periodically the ArrayList's backing array may need to be resized (which won't be the case if it was chosen with a large enough initial capacity), but since the array grows exponentially the amortized cost will be low, and is bounded by O(lg n) complexity.

Simply put - inserts into array lists are much simpler and therefore much faster overall.

Answer 4

Linked list may be slower than array list in these cases for a few reasons. If you are inserting into the end of the list, it is likely that the array list has this space already allocated. The underlying array is usually increased in large chunks, because this is a very time-consuming process. So, in most cases, to add an element in the back requires only sticking in a reference, whereas the linked list needs the creation of a node. Adding in the front and the middle should give different performance in for both types of list.

Linear traversal of the list will always be faster in an array based list because it must only traverse the array normally. This requires one dereferencing operation per cell. In the linked list, the nodes of the list must also be dereferenced, taking double the amount of time.

Answer 5

When adding an element to the back of a LinkedList (in Java LinkedList is actually a doubly linked list) it is an O(1) operation as is adding an element to the front of it. Adding an element on the ith position is roughly an O(i) operation.

So, if you were adding to the front of the list, a LinkedList would be significantly faster.