Meaning of List, Array, Vector, Tuple, Slice, in Programing Languages
The jargon list, array means quite a lot different things in different langs.
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 in a 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.
in statically typed languages, sometimes requiring all items having the same type.
Example:
- Dynamic Array (aka array, list, slice, growable array, resizable array.)
-
An ordered sequence, that can grow or shrink in length.
This is done by having a static array internally, but present to programers with a array with a “virtual” length, while the actual length is hidden. When the array grows beyond actual length, internally the static array is recreated. (when this happens, it takes n time proportional to the new length to recreate the array.) Likewise, when the array shrinks significantly, the array is recreated internally. (to save memory.)
In some languages, when creating a array for the first time, an optional parameter capacity is presented to programers as the starting actual length.
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.
Example:
- 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.
Example:
Sequence Names (List, Array, Tuple, Vector)
The name for the whole family of listy thing is called by different names in different lang.
Names for List of Pairs: Dictionary, Hash Table, Map, Associative Array
This is a collection of key and value pairs, and lets you efficiently:
- Insert a key value pair.
- Remove a key value pair.
- Lookup by key.
- Insertion order may or may not be kept.
example:
What is Associative Array?
Associative array, aka associative list, is basically a list of ordered key value pairs.
The implementation (and algorithmic properties) depends on the language.
- In Python since 3.7 (May 2018), its dictionary maintains order. Python: Dictionary
- In Ruby since v1.9 (year 2009), its hashmap is ordered. Ruby: Hash Table
- In WolframLang since version 10 (year 2014), added a ordered key value pairs datatype, called Association. Wolfram: Association (Key Value List)
- In Emacs Lisp, it's simply a linked list were each item is a pair. Elisp: Association List
Merged Array with Dictionary
Some dynamic languages, have a datatype that merges the concept of dynamic array and dictionary, where array is just a dictionary with integer keys generated automatically.
Example:
But JavaScript has dedicated map. JS: Map (aka Dictionary)