What is the difference between a list, a tuple and an array as data structures?

Question

Here I'm not talking about a particular programming language. I would like to know what is the difference between these things as between different data structures. I assume lists are basically supposed to be resizable whereas arrays are not, but I'm not sure.

Answer 1

Talking about "arrays" and "lists" as abstract data types without referring to any particular implementation can be a bit confusing, because those two are not very well defined.

The two Wikipedia pages List (abstract data type) and Array data type make this ambiguity somewhat evident, with uncertain statements such as "Implementation of the list data structure may provide some of the following operations:".

In many languages, there is a type called list and a type called array and they have some better defined meaning.

Here is a very general summary.

Lists:

• a list is linear, it is an ordered sequence of elements;
• you can access the first element of a list;
• you can add a new element to a list;
• you can access all elements of the list one after the other, starting from the first element. That last operation is done either with "arbitrary access" (accessing elements as l[0], l[1], l[2], etc.) or with two operations called "head" and "tail", where head(l) returns the first element of l and tail(l) returns the sublist obtained by discarding the first element.

In my mind, a list of four elements looks like this:

-> 3 -> 7 -> 12 -> 9

Arrays:

• an array provides "arbitrary access" using indices (accessing elements as a[something]);
• sometimes the index is restricted to integers between 0 and the length of the array; sometimes the index can be anything and everything;
• you can easily modify elements that you access, but you cannot necessarily add new elements.

An array which allows anything to be used as index is usually called a map or a dict in most languages, where array refers strictly to linear structures indexed by integers; but in a few languages, for instance PHP, it is still called an array.

In my mind, an array of four elements looks like this:

+--+--+--+--+
| 0| 1| 2| 3|
+--+--+--+--+
| 3| 7|12| 9|
+--+--+--+--+

Tuples:

• a linear, ordered sequence of elements;
• usually can contain elements of different types, whereas in most languages, all the elements in a list must have the same type;
• usually cannot add/remove elements
• in strongly-typed languages, such as Haskell or OCaml, the type of a tuple is given by its length and the enumeration of the types used in it, for instance the tuple (3, 7, 12.0, "9") has type (int, int, float, string), and a function returning a specific type of tuple cannot suddenly return a tuple of a different type.

Tuples in strongly-typed languages are sometimes called "product types" by analogy with the Cartesian product in mathematics, and are very close to struct in C. Tuples in weakly-typed languages are very close to lists.

Answer 2

Yeah, you are right.

Array can be created with fixed size and it is not possible to add items if array is full.

List is dynamic array and it can add items how many you want. Under the hood array is used in List in some languages, e.g. in C#. When new item is added and an array is full, then new array will be created with doubled size.

You can see the implementation of List<T> in C#