Arraylist vs LinkedList vs LinkedHashSet

[abhijitg ga]

Hello,

Creation : Arraylist if faster to create than linkedlist.

Insertion: Arraylist is slower when inserting objects in the list especially towards the beginning of the list. Linkedlist is much faster than Arraylist for insertion.

access : Arraylist is faster to access than linkedlist.


But can you confirm that LinkedHashSet scores over arraylist and linkedlist in terms of creation, Insertion ( hashsets uses hashing so I guess insertion should be faster) , access ( again due to hashing access should be fast) ???

Also I chose these three for comparison because the insertion order is maintained in all the three...

[Matthew Brown]

You can't really compare access times. LinkedHashSet may maintain insertion order, but it doesn't support random access - because it's a set, not a list. It's very fast to check if something is in the list, but you can't pick out a value. Similarly, it doesn't support insertion, only addition.

[Jesper de Jong]

abhijitg ga wrote:Creation : Arraylist if faster to create than linkedlist.

That completely depends on the implementation of the ArrayList and LinkedList classes. There's no reason to assume that creating an ArrayList would be faster than creating a LinkedList.

abhijitg ga wrote:Insertion: Arraylist is slower when inserting objects in the list especially towards the beginning of the list. Linkedlist is much faster than Arraylist for insertion.

That's true, that's one of the fundamental differences between ArrayList and LinkedList. In an ArrayList, the elements are stored in an array. If you want to insert an element in the middle, then all elements after it have to be moved one place. In a LinkedList, elements have references to their next and previous element. To insert an element in the middle, only the references from the previous and next element have to be updated.

abhijitg ga wrote:access : Arraylist is faster to access than linkedlist.

That's not true in general. An ArrayList has efficient random access by index: if you want to get the element at position N, then in an ArrayList you can access it immediately, but in a LinkedList you have to start at the first element and jump to the next one, the next one, etc. until you've found the N'th element.

abhijitg ga wrote:But can you confirm that LinkedHashSet scores over arraylist and linkedlist in terms of creation, Insertion ( hashsets uses hashing so I guess insertion should be faster) , access ( again due to hashing access should be fast) ???

About creation, it's just as the other two, there's no reason to assume anything about how fast creating a new LinkedHashSet is. Since LinkedHashSet uses a doubly-linked list to maintain the order of its elements, accessing an element by index will be just as inefficient as with LinkedList. Checking if an element exists in the set will be more efficient.

Note that LinkedHashSet is a Set, which is a different thing than a List. A List can have duplicate elements, a Set cannot have duplicate elements. So you cannot just use LinkedHashSet as a replacement for ArrayList or LinkedList in any situation.

[Jeff Verdegan]

abhijitg ga wrote:Hello,

Creation : Arraylist if faster to create than linkedlist.

Maybe, maybe not, but even if it is, the difference will be minuscule, and you will never choose one collection over another based on time to create it. Avoid these kinds of micro-optimizations.

Insertion: Arraylist is slower when inserting objects in the list especially towards the beginning of the list. Linkedlist is much faster than Arraylist for insertion.

For inserting at the end, they're both O(1). That's all that matters. For specific sizes, in absolute times, sometimes one wins, sometimes the other but never by an amount that's likely to be significant in the context of your application's performance. If you're just adding at the end, which is the normal use case, then, again, there's no reason to pick one or the other based on performance.

For inserting anywhere other than at the end, LL is O(1) while AL is O(N), but that's only true once you get to the spot where you want to insert. If you're getting there by index, then LL is O(N) and AL is O(1), so for both of them, to get to the i'th spot and insert an element is O(N). Where LL wins is, for example, if you're in the middle of an iteration and you want to insert something "here".

access : Arraylist is faster to access than linkedlist.

Depends what you mean. For iteration (the normal use case), they're both O(N). For indexed access, LL is O(N) and AL is O(1).

But can you confirm that LinkedHashSet scores over arraylist and linkedlist in terms of creation, Insertion

No. For the normal use case of just calling add(), AL and LL are both O(1), while LHS is O(log N). But LHS serves a different purpose than AL and LL. As a Set, it's for when you want to make sure no element is duplicated. The "Linked" part (as opposed to just plain old HashSet) just adds the feature that iteration order will match insertion order.

The important thing when comparing the performance of collections is not the absolute speed. That's a micro-optimization that can be done if and when you determine by measuring that it's a bottleneck. It's the big-O performance that matters.

If you just want a list to add() to and iterate over, AL is the de facto standard, but LL will work just as well. In most cases you'll never notice any difference.

If you need indexed access (random access), use AL, or something that implements RandomAccess.

If you're going to be adding/removing other than at the end of the list, LL will perform better than AL. But that's only true if you're adds/removes are not mostly by index.

If you need to prevent duplicates, and don't care about order, use a HashSet.

If you need to prevent duplicates, and want iteration order to match insertion order, use a LinkedHashSet.

If you need to prevent duplicates, and want iteration order to be sorted, use a SortedSet, such as TreeSet.

Note how my choices are almost all based on design needs, not performance.

[abhijitg ga]

Jesper de Jong wrote:

abhijitg ga wrote:Creation : Arraylist if faster to create than linkedlist.

That completely depends on the implementation of the ArrayList and LinkedList classes. There's no reason to assume that creating an ArrayList would be faster than creating a LinkedList.

abhijitg ga wrote:See the sample program by Stephan van Hulst at this link : https://coderanch.com/t/370191/java/java/Difference-between-ArrayList-LinkedList. Arraylist is faster to create than linkedlist

Insertion: Arraylist is slower when inserting objects in the list especially towards the beginning of the list. Linkedlist is much faster than Arraylist for insertion.

That's true, that's one of the fundamental differences between ArrayList and LinkedList. In an ArrayList, the elements are stored in an array. If you want to insert an element in the middle, then all elements after it have to be moved one place. In a LinkedList, elements have references to their next and previous element. To insert an element in the middle, only the references from the previous and next element have to be updated.

abhijitg ga wrote:access : Arraylist is faster to access than linkedlist.

That's not true in general. An ArrayList has efficient random access by index: if you want to get the element at position N, then in an ArrayList you can access it immediately, but in a LinkedList you have to start at the first element and jump to the next one, the next one, etc. until you've found the N'th element.

abhijitg ga wrote:But can you confirm that LinkedHashSet scores over arraylist and linkedlist in terms of creation, Insertion ( hashsets uses hashing so I guess insertion should be faster) , access ( again due to hashing access should be fast) ???

About creation, it's just as the other two, there's no reason to assume anything about how fast creating a new LinkedHashSet is. Since LinkedHashSet uses a doubly-linked list to maintain the order of its elements, accessing an element by index will be just as inefficient as with LinkedList. Checking if an element exists in the set will be more efficient.

abhijitg ga wrote:if checking if element is fast (I assume that it uses the hashing to check whether the element exists ) then accessing the same element should also be fast? Or I am missing some difference between accessing an element and checking if the element exists?

Note that LinkedHashSet is a Set, which is a different thing than a List. A List can have duplicate elements, a Set cannot have duplicate elements. So you cannot just use LinkedHashSet as a replacement for ArrayList or LinkedList in any situation.