In situations where there is no clear advantage between a LinkedList and an ArrayList, which should be used?

In a case where the only operation being performed on a list is non-rand开发者_如何学Com access (no removals, additions, or other tom-foolery), would it be advisable to use an array, ArrayList, LinkedList, or something else? or is it irrelevant which is selected?

Except in some specific situations (like embedded systems), you are likely working with a hierarchical and/or virtual memory system.

While the implementation details of this have been sufficiently abstracted by the operating system or hardware so that it is transparent to you, there are still some important considerations.

An array based implementation will exhibit a higher degree of spatial locality between elements than independently linked elements.

http://en.wikipedia.org/wiki/Locality_of_reference

In computer science, locality of reference, also known as the principle of locality, is the phenomenon of the same value or related storage locations being frequently accessed. There are two basic types of reference locality. Temporal locality refers to the reuse of specific data and/or resources within relatively small time durations. Spatial locality refers to the use of data elements within relatively close storage locations. Sequential locality, a special case of spatial locality, occurs when data elements are arranged and accessed linearly, e.g., traversing the elements in a one-dimensional array.

Locality is merely one type of predictable behavior that occurs in computer systems. Systems which exhibit strong locality of reference are good candidates for performance optimization through the use of techniques, like the cache and instruction prefetch technology for memory, or like the advanced branch predictor at the pipelining of processors.

Based on this, all other things being equal, I would choose ArrayList over LinkedList.

I think your question answers itself to some extent: if it doesn't matter which one is chosen, then it doesn't matter which one you choose; if it does matter, then pick the best one.

This is mildly tongue-in-cheek but in the absence of specifics, it's what the choice boils down to.

If it helps, the Java Collections Tutorial seems to recommend ArrayList as the general-purpose list implementation when there aren't any pertinent criteria:

In each case, one implementation — HashSet, ArrayList, and HashMap — is clearly the one to use for most applications, all other things being equal.

Certainly the third party code I've seen (and first-party code I've written) adopts this principle as well.

From your question, it sounds like all you're doing is iterating through the list (no adds, no deletes, no random lookups). As such, there shouldn't be much of a difference between the two implementations (as you noted).

The only thing I can think of that makes a difference is space and object creation. An ArrayList needs less memory to store it's data (array vs node:data+next+prev). As such, my default option would be to use ArrayList.

If the data is static and you're just doing lookups, use an array. If you use an ArrayList you'll have some initialization time, and a LinkedList will have slower lookups + the initialization.

LinkedList is actually pretty specialized; I would only use it with a large, quite dynamic list requiring only sequential access.

If your list is small or requires random access or does not have many insertions and deletions, use an ArrayList.

A LinkedList would have additional memory overhead for the link references. I don't think there's much difference between an ArrayList and an array if you use the constructor to set the initial capacity of the ArrayList, so I tend to use ArrayList whenever I see no clear advantage. It's situational though...for example if I am using vararg parameters for input I might keep everything as arrays for simplicity.