There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Campbell Ritchie wrote:LinkedLists are slower at finding elements in the middle, but it may be faster to insert if you can use an insertAfter method.
Campbell Ritchie wrote:Unfortunately java.util.LinkedList hasn't got an insertAfter method.
And Fred's answers were so much better phrased than mine.
Campbell Ritchie wrote:But add(E) adds an element at the end of the List, and add(E, int) would have to iterate through the List to find its insertion location.
SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6
How To Ask Questions How To Answer Questions
Muhammad Ali Khojaye wrote:True, ArrayList gives better performance when accessing and iterating objects whereas LinkedList gives better performance when adding and removing objects from beginning and end. LinkedList become worse when adding/removing objects from middle.
Jesper Young wrote:- ArrayList is slow at inserting elements (head, tail or in the middle), because all elements have to be shifted.
Rob Prime wrote:
Jesper Young wrote:- ArrayList is slow at inserting elements (head, tail or in the middle), because all elements have to be shifted.
Not 100% correct. Granted, inserts at the start or middle are slow because of the shifting. However, inserts at the tail can be fast if the backing array still has capacity left. It can then simply store the element at the next available spot and increase the count. It becomes slow again if the capacity is not sufficient, because a new array must be created and all elements must be copied.
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
...
Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.
Thank you. I was mistaken there. Sorry.Rob Prime wrote:Henry was talking about ListIterator's add(E) method.
Bob Wheeler wrote:This is really an interesting discussion. Looking at the API, they say for the inserting operation (add) it needs amortized constant time. They also say, that by adding elements to the array the capicity grows automatically and the growth policy is not specified. So how should we know what the effect is? is it negligible or not?
Rob Prime wrote:
Bob Wheeler wrote:This is really an interesting discussion. Looking at the API, they say for the inserting operation (add) it needs amortized constant time. They also say, that by adding elements to the array the capicity grows automatically and the growth policy is not specified. So how should we know what the effect is? is it negligible or not?
Well, I usually start by looking at the source of the class (current implementation). That shows me that the size of the backing array is increased with at least 50% if it needs to be. Afterwards, all data is copied to the new array using System.arraycopy (in the end). That copying is O(list.size()).
Rob Prime wrote:
I don't really buy that amortized constant time. If you add many objects without using addAll (addAll moves everything as much as needed, so only one move for all elements combined), that can potentially cause many resizing and shift operations. For instance, an empty ArrayList with initial capacity of 10, with 1000 objects added individually at index 0, will require 11 resizing operations*, and 999 shift operations. Those shift operations range from 1 element to 999 elements. Including the copying during the resizing operations, that's 1010 calls to System.arraycopy, all with O(list.size()). In the end, 501500 objects are copied, for an average of over 501 per added object. No, you can't tell me that's even remotely constant time. Even adding at the center (rounding up) requires 251500 objects copied, or an average of over 251 per added object.
Adding at the end, sure, that's only 11 System.arraycopy calls. Using addAll there is at most 2 (one for resizing, optionally one for shifting). Compared to the 1000 added elements, that's negligible. (And because the list is initially empty there will actually be 0 copied objects.)
*10 -> 16 -> 25 -> 38 -> 58 -> 88 -> 133 -> 200 -> 301 -> 452 -> 679 -> 1019
Jesper Young wrote:
- LinkedList is fast at inserting elements (head, tail or in the middle), because the new element can just be linked in, existing elements to not have to be moved.
Action | ArrayList | ArrayDequeue | LinkedList |
---|---|---|---|
get from the beginning or end of list | O(1) | O(1) | O(1) |
get from the middle of list | O(1) | O(1) | O(N) |
add/delete at beginning of list | O(N) | O(1) | O(1) |
add/delete at end of list | O(1) | O(1) | O(1) |
add/delete in middle of list by random access | O(N) | O(N) | O(N) |
add/delete in middle of list using an iterator | O(N) | O(N) | O(1) |
Mike Simmons wrote:I added ArrayDequeue to my last post, as it's an excellent alternative for some cases. Good call, Campbell.
Also, I agree with Campbell's last post - the ArrayList API did a poor job of saying what they meant, but I'm sure they were just thinking of the one-argument add(), not the two-argument version.
* Omit parentheses for the general form of methods and constructors
When referring to a method or constructor that has multiple forms, and you mean to refer to a specific form, use parentheses
and argument types. For example, ArrayList has two add methods: add(Object) and add(int, Object).
However, if referring to both forms of the method, omit the parentheses altogether. It is misleading to include empty parentheses,
because that would imply a particular form of the method. The intent here is to distinguish the general method from any of its
particular forms. Include the word "method" to distinguish it as a method and not a field.
Steve
Coming from Mike Simmons that means a lot. Thank you.Mike Simmons wrote:Good call, Campbell.
Mike Simmons wrote:Agreed. But it's not as if everything in the standard Java API was written by a single person, and it's reasonable to imagine that not everyone was on the same page at all times. Also, to imagine that those individual persons might simply make mistakes. To me, it seems like it is (or at least, should have been) very, very obvious to anyone who thought a moment about it, that add(E, int) could not be O(1). And so I think it's far more believable that they simply forgot to consider the more general meaning of "add" (sans parentheses) or they were unaware of it. Well, even if they were unaware, it should have been obvious on consideration that the given API did not distinguish between the different cases. So I think they just overlooked it entirely, having been more concerned with implementation than documentation. That's just a guess, of course.
Steve
permaculture is a more symbiotic relationship with nature so I can be even lazier. Read tiny ad:
We need your help - Coderanch server fundraiser
https://coderanch.com/wiki/782867/Coderanch-server-fundraiser
|