Is Java linkedlist slower than arraylist when adding items?

Question

I thought that linked lists should have been faster than arraists when adding items? I just checked how long it takes to add, sort and search for elements (arraylist vs linkedlist vs hashset). I just used java.util classes for arraylist and linked list ... using both add (object) methods available for each class.

arraylist out did a linked list when filling out a list ... and in a linear list search.

Is that right? I did something wrong in the implementation, maybe?

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

I just want to make sure that I use these things correctly. that's what I'm doing:

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

Then I just use the linked list methods, that is, "Names.add (strings)". And when I tested the arraists, it is almost 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 need to do a memory allocation for each insert, and an ArrayList allowed to execute fewer of them, giving it a cushioned O (1) insert . Memory allocation looks cheap, but can actually be very expensive.

Linear search time is probably slower in LinkedList due to the locality of the link: ArrayList elements are closer to each other, so there are fewer cache misses .

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

Answer 2

Remember, that:

• there is a difference in raw performance for a given number of elements and in how different structures scale ;
• different structures are performed differently in different operations and that is essentially part of what you need to consider when choosing a structure to use.

So, for example, a linked list has more options for adding to the end, because it has an additional object for allocation and initialization for each added item, but no matter what the “internal” cost for an item, both structures will have O (1 ) to add to the end of the list, i.e. Have an effective “constant” time to add any size to the list, but this constant will be different between ArrayList and LinkedList and may be larger for the latter.

On the other hand, a linked list has a constant time to add to the top of the list, whereas in the case of an ArrayList the elements must be “shuftied” together, an operation that takes some time proportional to the number of elements. But, for a given list size, say, 100 items, it can still be faster to “shufty” 100 items than assigning and initializing one placeholder in a linked list (but by the time you get, say, a thousand or a million objects or whatever the threshold, it will not).

Thus, when testing, you probably want to consider both the raw time of operations with a given size and how these operations scale as the size of the list increases.

Answer 3

When you add an item to the end of a LinkedList (there is actually a doubly linked list in Java LinkedList), this is O(1) operation since adding the item to it. Adding an item at the i th position is roughly an O(i) operation.

So, if you add to the top of the list, LinkedList will be significantly faster.

Answer 4

Why do you think LinkedList will be faster? In the general case, inserting into the list of arrays is just a case of updating the pointer for one cell of the array (with random access O (1)). The LinkedList insert is also random access, but must allocate a "cell" object to hold the record and update a couple of pointers, and also ultimately establish a link to the inserted object.

Of course, it may be necessary to periodically change the size of the ArrayList support array (which would not be the case if it was selected with a sufficiently large initial capacity), but since the array grows exponentially, the amortized cost will be low and limited by O(lg n) complexity.

Simply put - inserting into array lists is much simpler and therefore much faster.

Answer 5

A linked list can be slower than an array list in these cases for several reasons. If you insert at the end of the list, it is likely that this space is already allocated in the list of arrays. The main array usually grows in large pieces, because it is a very time-consuming process. Therefore, in most cases, adding an element to the back only requires linking to the link, while the linked list needs to be created by a node. Adding to the beginning and middle should lead to different performance for both types of list.

Linear traversal of the list will always be faster in an array-based list, because it should only go in the usual way. This requires one dereferencing operation per cell. In a linked list, list nodes must also be dereferenced, doubling the amount of time.

Answer 6

ArrayList accesses random index data faster, but slower when inserting items in the middle of a list, because using a linked list, you just need to change the reference values. But in the list of arrays you need to copy all the elements after the inserted index, one index at a time.

EDIT: Is there a linked list implementation that takes into account the last element? Performing this method will speed up pasting using a linked list.