1

I've been thinking about this over the past few weeks, and I've come up with no good arguments. My perspective is from Java, but if anyone has any language-specific cases outside of this language, I'd love to hear them.

It seems to me that the benefit of using a List over a Deque comes from the fact that one can access the elements within directly via index numbers. While I can see the use in something like a UI (e.g. having a drag-and-drop sortable list), when talking about pure code interaction I see three cases for this:

  1. Iteration. Iterating with a for loop using get(i) and size() is expensive in most implementations, and can usually be better done with iterator(), which is present in every Iterable collection.

  2. Lookup by index. This usually requires a table of indices and a fixed length list, in which case one would get better performance out of an array.

  3. Operating on the front or back of a List. This is what Deque was designed for, and it doesn't require any calls to size().

Collections support is nice, but the only thing I could find offhand that was implemented in Collections but not Arrays was a shuffle() function, which is fairly simple for an experienced programmer to implement (or delegate to Collections, since the overhead for non-primitive arrays isn't too bad IMO).

I feel that everything that one would need a List for can be better filled by either a Deque or an array. I've done some searching for comparisons, but the only info I've found either doesn't really discuss Deques or is written as a "Welcome to Programming" thing and doesn't offer a direct comparison of use cases. I've looked over my code for the past few years and haven't found any Lists outside of UI elements; I usually use a Set or a BlockingQueue for storing variable-length data.

12
  • You might be right about Deque but in Java (at least) arrays have fix size which is simply a nogo in most of my use cases. Feb 2, 2018 at 17:19
  • Yes, I'm aware. But for variable-length data I'm suggesting using a Deque. ArrayDeque is an implementation with about the same performance as ArrayList, and LinkedList also functions as a Deque.
    – ndm13
    Feb 2, 2018 at 17:22
  • 3
    then I simply see it the other way around: i don't use arrays unless I have a really good reason to do so. Feb 2, 2018 at 17:24
  • If you can give the reasons you prefer Lists to arrays for fixed-length data, I'd love to read about it. Programmer opinion, language semantics, and expected behavior are all important factors in choosing a construct. You can feel free to post an answer if you feel like you have enough material for one.
    – ndm13
    Feb 2, 2018 at 17:27
  • 5
    Re, "2. Lookup by index...get better performance out of an array." Performance is not an issue when comparing java.util.List with java.util.Deque. They are interfaces. Performance is only an issue when you choose an implementation. Feb 2, 2018 at 18:07

2 Answers 2

8

A List is general and flexible.

Generalized structures are ideal for return values in business, web, and desktop applications. It's not optimal to return a Deque or an Array if your consumers will be converting to List in most cases anyway. It's potentially less efficient. And, it clutters your consumers' codebases with boilerplate conversions and/or utility libraries to deal with your "more efficient" interfaces.

To be clear: Some structures, like Deque's and Array's are certainly more efficient for particular use cases, but a List is sufficiently efficient for most use cases. List's may be over-used. But, in many domains, the performance hit of using a List over a more well-suited structure is negligible — not even worth a second thought.

Compound that with work-effort versus business value: Choosing a data structure that supports the precise interface I need and no more requires mental effort and time. And those are costs to the business. Sometimes there's a corresponding increase in value. But, in many applications there isn't — neither the business nor the customers will see any difference if you swap your List out for a more-optimized Deque when you're piping 50 rows from the database through your model to your view. (Or whatever.)

That said, there are use-cases that are well-served by List's.

The "need" for a List is more obvious in long-lived, stateful applications, where collections can stick around and be mutated over a long period of time. A text editor, for example, shouldn't automatically create a data[MAX_ROWS][MAX_COLS] array of arrays. And, you certainly could create an array of arrays with some default sizes and scaling behaviors and add methods for insertions and deletions. But, that's precisely what the List interface already does for you. (And the existing implementation already well-tested and optimized!)

My "2 cents": Unless your domain is small, very well-defined, or performance-critical, start with general collections and optimize later. The flexibility is immediate valuable in most business and web applications. Whereas the performance edge is negligible.

And don't forget about stateful applications, where a List interface is more often precisely what you'll end up reinventing if you've defaulted to an array or Deque...


Examples of things where you might favor efficiency over flexibility might include things like system code (OS, driver, firmware), a VM, or other types of "platform" code — like a modern web browser's internal DOM implementation or JavaScript execution engine.

6
  • So you're arguing that public-facing APIs should use Lists over arrays to avoid confusion/hassle? I can completely see that argument. But for internal use, I still feel my points are valid.
    – ndm13
    Feb 2, 2018 at 19:26
  • 2
    Well, not just in the sense of distributed libraries or web API's, if that's what you mean. I mean "internally" too, I usually prefer to consume (and therefore return) List's [when appropriate]. Even within a class, I default to a List over a Queue, Deque, or Array, because the performance implications don't often outweigh the downstream flexibility. Just bear in mind, my advice applies to business systems and web stacks, which I sense most of us (at SE.SE) work on. If you're writing a VM, OS, driver, or firmware, my advice might be the opposite: Favor performance.
    – svidgen
    Feb 2, 2018 at 20:58
  • 1
    FYI, I realize my answer didn't cite a specific example of where a List interface is actually preferred. And, I don't want to give the impression that "I don't know what my callers need" is the only reason for a List. ... So, I'm working on working a more specific use-case in.
    – svidgen
    Feb 2, 2018 at 21:38
  • 1
    @ndm13 Probably not. A List of StringBuilder's is probably good. But, a straight-up StringBuilder will leave you parsing and re-parsing a giant blob when you draw/redraw the characters. If you've already got the character stream separated (indexed) into lines, and you know your scroll position, it's super-efficient to jump to lines[scroll_top_line] (or whatever) and just start drawing...
    – svidgen
    Feb 2, 2018 at 23:10
  • 1
    ... and of course, if you've got any sort of formatting or syntax highlighting going on, your StringBuilder loses its effectiveness at the line-level too. You'll probably want a Token list of some sort. Stuff you probably want to overlay instead of embed into the underlying character data. ... Moot point though. Bottom line is, there are situations where the List interface would have to be re-invented if we avoided using a List. ... Which you're free to do with a StringBuilder or an Array if you like. ... ... Or you could just use a List.
    – svidgen
    Feb 2, 2018 at 23:15
4

Is there a reason to use java.util.List instead of using java.util.Deque?

Yes.

java.util.List has methods to access elements by position. java.util.Deque does not. If you are implementing an algorithm that needs to access elements by position, then Deque is not going to work. The contrapositive is true as well: If your algorithm only needs to look at the items in sequence (i.e., if you can use an Iterator), and if it only needs to mutate the sequence at the two ends (or one end, or not at all), then a Deque will work for you.

The guiding principle is pretty simple: Choose an interface that defines the methods that your application needs to call.


Is java.util.List a well-designed inteface with a clear purpose?

IMO, No. It tries to be too many different things. If I want you to call my function that will randomly access the list elements, then I am not going to allow you to pass in just any List. I am going to make you pass in an ArrayList, or maybe, if we are collaborating on a project where it makes sense to have a lot of custom classes, we will define an interface that defines exactly those operations that my code is going to perform on your list.

7
  • I appreciate this answer, but I'm curious: what types of algorithms would require a List of variable length?
    – ndm13
    Feb 2, 2018 at 20:42
  • 2
    Nothing requires a List. A List is just an easier abstraction than a Deque or Array for algorithms that perform List-like operations, like Add(int,obj) or Remove(int). If I write a simple text editor and a user is actively pressing keys, I want the collection(s) underlying the UI/view code to expose a highly dynamic interfaces. I don't want my view resizing arrays or streaming through a Deque for every keystroke.
    – svidgen
    Feb 2, 2018 at 21:18
  • For UI, I 100% understand the need for Lists: an indeterminate number of elements are getting rendered on a (screen|terminal|page|etc) in a certain order, and they need to be referenced by location. Outside of that, though, I feel like you could substitute any Iterable.
    – ndm13
    Feb 2, 2018 at 21:31
  • 1
    There are a lot of applications that contain long-lived, stateful collections beyond a desktop UI's. It was a single example. I'm sure you can think of other applications that don't fit the request-response model most of us deal in.
    – svidgen
    Feb 2, 2018 at 21:41
  • I can't think of any use case, other than within a UI where a user would be providing an index based on regularly updated, variable length information, where it would be necessary to have an index-addressable collection of variable length. That's the purpose of my question: for index-addressable collections of fixed length, arrays perform better, and for non-indexed collections, a Deque or another Iterable can typically provide all necessary functionality.
    – ndm13
    Feb 2, 2018 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.