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

Computer Science “Data Structure” vs Programing Language “Datatype”

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:

• Python: Tuple
• Elisp: Vector
• Golang: Array
• Java: Array
• Wolfram: List

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:

• JS: Array
• Python: List
• Ruby: Array
• Perl: List, Array
• Golang: Slice

Linked List

An ordered sequence, with the following algorithmic properties:

• Allows fast, constant time, adding 1 item (typically called push) to the end, or delete 1 item (called pop) at the end. (in lisp, it's add or remove to the front.).
• 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:

• Elisp: List

Programing Language Datatype Terms

e.g. in emacs lisp, the term “list” means the data structure so-called “linked list” . in python, the term “list” means the data structure so-called “dynamic array”.

Datatype terms in different programing languages for list kinda things

• Array
• Vector
• Tuple
• List
• Sequence

Datatype terms in different programing languages for key-value pairs kinda things

• Dictionary
• Map
• Hash-table
• Association list
• Association

Sequence Names (List, Array, Tuple, Vector)

The name for the whole family of ordered collection of items is called by different names in different lang.

• Java: Collection
• Python: Sequence Types
• Elisp: Sequence Type

Names for List of Pairs: Dictionary, Hash Table, Map, Associative Array

This is a collection of key and value pairs, with unique keys, 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:

• JS: Object Type and JS: Map Tutorial
• Python: Dictionary
• PHP: Array
• Perl: Hash Table
• Ruby: Hash Table
• Elisp: Hash Table
• Golang: Map
• Java: Map

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

see also Perl: Difference Between List and Array

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:

• JS: Array
• PHP: Array

But JavaScript has dedicated map. JS: Map Tutorial

see also Perl: Difference Between List and Array