Search code examples
javalistarraylistlinked-listadt

Java ArrayList: What is Its Abstract Data Type?

Java's "ArrayList" seems like a contradiction to me. An array (static or dynamic) is certainly nothing like a list in a language like c++ or in computer science. What inherits from Java's List and yet seems to be nothing like one is rather silly.

Questions:

  1. What is the abstract data type of the ArrayList? Is it a vector (dynamic array), or is it a linked list?
  2. Why was the name ArrayList chosen? Why was the name List chosen for something that uses indexes to access elements and is sometimes random access (see here)?

NB: I come from a c++ background where a list is a linked list and vector is a vector (self-adjusting dynamic array). Is this terminology different in other languages?

Solution
    1. It's implemented with a dynamic array, in your terminology. (It's actually a static array that just gets replaced when the list needs to be resized.)
    2. It's an implementation of the List interface that is based on arrays. Therefore, it's an Array List.
    3. Yes, the terminology is different. That's not a general use of the term "vector." "List" just refers to a list in plain English: a number of elements of a type.