Meaning of List, Array, Vector, Tuple, Slice, in Programing Languages

By Xah Lee. Date: . Last updated: .

The jargon list, array means quite a lot different things in different langs, but often, when in argument in a particular lang community, the people ignore, deny, any other meanings, insists any other meaning is wrong or troll. This was the case with many common lisp regulars in comp.lang.lisp.

First, we need to distinguish data structure of computer science, and datatype of programing languages.

data structure
A structure for storing data, in computer science. These structures are human created. Different structure are created for their different algorithm properties. i.e. with respect to time efficiency for retrieving an item, change item, or storage size efficiency, etc.

What data structure are there depends on what is the actual machine (the computer), e.g. Electronic computer, abacus, fingers, cellular automata, dna computer, quantum computer.

Given a computer, such as modern electronic computer, what data structure there are, and what algorithm properties it has, also depends on the specific architecture. e.g. typically the physics and design of the memory device.

datatype
A type of value of a given programing language.

In programing languages, we have datatype named list, array, tuple, vector, slice, etc. They corresponds to the various data structures of computer science.

Data Structure Terms

Array (Or Static Array)
Fixed length ordered sequence, with the following algorithmic properties:
  • Random access any element is fast and constant time.
  • Cannot add or delete items.
  • Often requiring all items having the same type.

Programing language datatype:

Linked List
An ordered sequence, with the following algorithmic properties:
  • Allows fast, constant time, adding 1 item (typically called push) or delete 1 item (called pop) at the front. (or both at the end).
  • Access nth element is proportionally slower if n is large.
  • Each item can be any type.

This is the standard structure for implementating stack data structure.

Programing language datatype:

  • In Emacs Lisp and Common Lisp, this datatype is called list. [see Emacs Lisp: List]
Dynamic Array (aka array, list, slice, growable array, resizable array.)
An ordered sequence, that can grow or shrink in length. (aka growable array.)

Start with a fixed array, with length called capacity. E.g. 10. This capacity, an actual length, is hidden from user. Present the user with a length (length ≤ capacity), that is the logical size of the array. When an item is added that exceeded the current capacity, internally create a new array with double the capacity. (or, enlarge the capacity by geometric progression or other.) Automatically manages this hidden size and logical size of the array. Similarly, when capacity is far larger than the logical size to some degree, shrink the array by creating a new one. (to save memory)

Algorithmic property: Like fixed array, but now the array can grow or shrink. Each time capacity is reached, it takes n times proportional to the capacity.

Programing language datatype:

a listy thing that's fixed in length and allow fast random access is most often called “array”, of C's array.

listy thing that's chained as in lisp “cons”, is often called “linked list” or simply “list”. Best example is lisp's list (list 1 2 3), which is really (cons 1 (cons 2 (cons 3 nil))) (Cons Cells - GNU Emacs Lisp Reference Manual)

lisp's “vector” datatype (vector 1 2 3) is array. [see Emacs Lisp: List vs Vector] (Sequences Arrays Vectors - GNU Emacs Lisp Reference Manual)

Mathematica's list List[] is array.

perl's “array” @a = (1,2,3); and python's “list” a = [1,2,3], and ruby's array, are … not sure there's a specific name, but perhaps smart array. That is, array that automatically grows without being slow (the language adds hidden empty elements exponentially). Specifically, it's not lisp's linked list. [see Python: List] [see Perl: List/Array]

what perl calls a “list”, is actually only a syntactic thing. Once it's set to a var, perl calls it array. It also has automatic growth feature. [see Perl: Difference Between List and Array]

PHP's list is a mix of array and hashmap. It's really a hashmap with magic. But when keys are not used/set, it auto default to numbers, as array. PHP doc says “An array in PHP is actually an ordered map.” [see PHP: Array Basics]

JavaScript's array is really a hashmap, what it calls “object”, with magic. The index of js's array is actually just the name of keys that happens to be positive integer…. [see JavaScript: Understanding JavaScript Array]

also, the name for the whole family of listy thing is called by different names in different lang.

lisp calls it “sequence” type. (but not including “hash table”, but includes {list, associative list, vector, string, etc})

          _____________________________________________
         |                                             |
         |          Sequence                           |
         |  ______   ________________________________  |
         | |      | |                                | |
         | | List | |             Array              | |
         | |      | |    ________       ________     | |
         | |______| |   |        |     |        |    | |
         |          |   | Vector |     | String |    | |
         |          |   |________|     |________|    | |
         |          |  ____________   _____________  | |
         |          | |            | |             | | |
         |          | | Char-table | | Bool-vector | | |
         |          | |____________| |_____________| | |
         |          |________________________________| |
         |_____________________________________________|
emacs lisp's sequence datatype.

Java calls it “collection” for list/array/set things [Collection (Java Platform SE 8 )] and calls it “map” for list of pairs things. [Map (Java Platform SE 8 )]

Python wants to call it “sequence”, and if counting {hash, map, sets} it's called “container” type. (4. Built-in Types — Python v3.3.3 documentation #sequence-types-list-tuple-range)

“hash table” is known as “map” in java [Map (Java Platform SE 8 )] , “dictionary” in python, “object” in JavaScript [see What is Object in JavaScript?] , “array” in PHP. But in {perl, ruby, lisp}, it's just called any of {hash, hash map, hash table}.

[see Meaning of Object in Computer Languages]

Programing Language Naming of Things