1
$\begingroup$

Different languages have different names for the same thing. Off the top of my head, there's:

Some of these names are overloaded ("vector" could mean a SIMD register, for example). However, no single one seems to have "won out" for this specific use case.

What are some arguments for and against each one?

$\endgroup$
1
  • 1
    $\begingroup$ VtCing as opinion-based for now, this could easily be reworded to be more objective tho $\endgroup$ May 17, 2023 at 1:43

2 Answers 2

8
$\begingroup$

For what it's worth, the Wikipedia page about this data structure calls it a

dynamic array, growable array, resizable array, dynamic table, mutable array, or array list

I prefer the term "array list" but that's probably just because of my background, and it's hard to give any objective argument for why one name should be preferred over others, beyond popularity or appeal to authority.

That said, it may be called simply a "list" in contexts where what matters is not the underlying data structure, but the abstract data type it implements. The contrast is between naming things by what they're made of (in this case, an "array list" is a list made from an array) vs. what they're used for. This isn't to imply that the word "list" actually means an array list, only that sometimes the fact that it's a list matters more than the fact that it's an array list.

Lower-level languages will tend to use names which describe the data structure, since programmers want control over which data structures are used; higher-level languages will tend to use names which describe the data type, since the programmers want a general-purpose way of solving problems without having to make choices about such implementation details. So it makes sense that e.g. Python has "lists" and "dictionaries" instead of "dynamic arrays" and "hashtables".

So I'd suggest calling it an "array list" or "dynamic array" if your language is making the programmer choose which data structures to use, or just "list" if your language is trying to make a sensible default choice so the programmer doesn't have to think about it. Put another way, if it's the only kind of list your language has first-class support for, then just call it a list.

$\endgroup$
4
  • $\begingroup$ I really dislike the term "array list". I guess that comes from thinking of lists as "linked lists - implemented by pointers" and "arrays as a heterogeneous 'list' of values usually stored in contiguous memory". The name array list only makes sense coming from a place like Java where the "list" interface is shared between them. In C++ we consider the complexity part of the interface so a vector is not a list because it has O(1) access time for example. The prejudice against the name is so strong I almost downvoted your perfectly correct answer. $\endgroup$ May 30, 2023 at 16:27
  • $\begingroup$ @BruceAdams That's an interesting point about considering complexity part of the interface. But in that case the array-list's O(1) time for random access is within the O(n) bound for that operation on what C++ calls a list. If it's considered important for a C++ list to have O(1) insertion/removal at the start of the sequence then an array-list doesn't fulfil that part of the interface; but it's strange to me that you consider it not to be a list because random access is too fast. $\endgroup$
    – kaya3
    May 30, 2023 at 16:37
  • $\begingroup$ That was inelegant grammar on my part. I meant a list is not a vector because a vector has O(1) access time where a list has O(n) access time using an index. A list has fast insertion and deletion instead. Both lists and vectors can be used as stacks. In C++ we also have a deque which offers fast insertion and both the front and the back in exchange for losing the guarantee of contiguous memory. $\endgroup$ May 30, 2023 at 16:41
  • $\begingroup$ @BruceAdams Ah, sure. Yes, I would say that "vector" is the name of a data structure, not an abstract data type, so any other list data structure is not a vector. Actually I'm somewhat surprised that Wikipedia doesn't list "vector" among the names for this data structure. $\endgroup$
    – kaya3
    May 30, 2023 at 16:43
5
$\begingroup$

C++ uses std::vector for contiguous variable-size containers to distinguish from std::array (fixed size) and std::list (non-contiguous). It's instructive to see how they gave unique names based on the container's properties. Whatever naming scheme you use, make sure the users know what to expect!

A side note: array programming languages like APL and its offspring (j,k,q) expect vector containers to come with vector operations. I.e., users know they can operate directly on a collection without using loops. So again, make sure to play to your users' expectations.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .