7

From this CodeReview answer,

You seem to use ArrayList for all purposes. There are other List-types in Java that suit certain situations better than an ArrayList. You should have a look at those and try to get a feeling when to use which list. In this particular case i.E. a LinkedList is better.

I also tend to use ArrayList fairly heavily, and don't see the logic behind selecting another list type.

The List docs show five main List subclasses: ArrayList, CopyOnWriteArrayList, LinkedList, Stack, and Vector.

From the ArrayList docs,

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.

This suggests that ArrayList will often outperform LinkedList (an assertion supported by this heavily upvoted question), although the LinkedList docs don't give a good idea of performance:

All of the operations perform as could be expected for a doubly-linked list.

CopyOnWriteArrayList only seems useful for unchanging lists, since the full snapshot on every modification seems ridiculously expensive for normal use.

Even the Stack docs don't recommend using it:

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

Since Vector is synchronized and the rest of the List subclasses are not, it seems to me that Vector would be the best choice in a threadsafe environment.

Even after reading through the docs, however, I still don't think I understand where TwoThe's answer came from. CopyOnWriteArrayList and Vector each seem to have one specialized use case, Stack doesn't seem worth using, and ArrayList seems superior to LinkedList.

What am I missing here, and under what circumstances would another List implementation be superior to ArrayList?

Community
  • 1
  • 1
cf-
  • 8,598
  • 9
  • 36
  • 58
  • 1
    FYI: `Vector` is generally consider to be deprecated, if you need the synchronized functionality, you can use `Collections.synchronizedList` – MadProgrammer Feb 13 '16 at 03:18
  • It's not always possible to know which one will always be right (for the method/API). In some case you will want random access, which an `ArrayList` is good at, sometimes you want serial/linear access, which `LinkedList` is good at. Normally, if my method, internally, uses an `ArrayList`. I will make the method return `List`, if I want to use a `LinkedList`, I might consider returning `Iterator`, this forces the use into a serial access mode, but you don't always know what other people might want from your data – MadProgrammer Feb 13 '16 at 03:22
  • For event firing, CopyOnWrite is almost certainly the correct implementation. Concurrency is a big issue. Reads happen way more often than writes. – user949300 Feb 13 '16 at 06:05

2 Answers2

0

Simply put, you are correct and TwoThe is incorrect in this particular case. As you have pointed out, since all you're doing here is adding and looping, a LinkedList would only slow you down. This is a perfectly valid use case of ArrayList, and there is nothing wrong with defaulting to ArrayList when you're not quite sure which List to use.

For a more detailed explanation of when you should use a LinkedList, the answers to this question may be helpful.

Community
  • 1
  • 1
Sam Estep
  • 12,974
  • 2
  • 37
  • 75
0

I agree that ArrayList is the right choice for many uses. LinkedList uses 8 or 16 bytes of memory per element for pointers, and indexing is O(length) as you've said.

What are LinkedLists advantages, then?

  • Deletion with remove() during iteration is constant time. With ArrayList it's O(length).
  • Adding a new list node always requires the same amount of time. When ArrayLists run out of space, a bigger block of memory is allocated behind the scenes, and all contents are copied. While the amortized time for this over many operations is constant per element, the cost of an individual add() is O(length). If this kind of periodic delay is not acceptable, you can't use ArrayList.

As to the others, Vector goes back to the earliest days of Java. It's thread safe. Because this adds cost to each operation, its use is more-or-less deprecated in favor of ArrayList. When you need thread safety, you can use the SynchronizedList wrapper around an ArrayList. Similarly Stack is more-or-less deprecated in favor of the more modern and not threadsafe Deque.

CopyOnWriteArrayList is a thread safe data list that gets its safety through the somewhat unusual measure of making a copy of the complete array any time the any element changes. While this sounds crazy, it makes sense if there are many threads iterating over the same array because the change doesn't have to wait for the iterations all to complete, which with other concurrent lists is normally the case.

Gene
  • 46,253
  • 4
  • 58
  • 96