To answer your question, there is no direct equivalent to the cons that you would usually find in what are called "functional" languages (lisp, OCaml, Haskell, etc.)
That's because there are two competing models to represent lists of elements in programming languages.
Linked lists
The one you seem to be familiar with is called a linked list.
A linked list is composed of cons-cells that each contain two references :
- the first one toward an element of the list and is called head
- the other towards the next cons-cell in the list and is the tail
Because lists are rarely infinite, the last const cell would usually point towards a special value, the empty list, sometimes called nil.
If you wanted to save the list in a variable for future reference, you would keep a reference towards the first cons-cell.
Here's a visual representation from Wikipedia.
In this model, every list is necessarily constructed by adding elements to the front by creating a new cons-cell, pointing to the new element as its head and to the previously constructed sublist as its tail. This is why the cons operator is sometimes called the list constructor.
Arrays
This is the model usually preferred by imperative languages such as Python. In this model, a list is just a reference to a range in memory.
Let's suppose you create a list just like so :
l = [1, 2, 3]
Whenever you create a list, Python will assign to it a small range of memory in which to store the elements, with a bit of extra space just in case you want to add elements later. To store it, you would simply store a reference to the first element, and to the size of the memory range, just like so :
l <-- your variable
| ___ ___ ___ ___ ___ ___ ___ ___ ___
|-> | | | | | | | | | |
| 1 | 2 | 3 | | | | | | |
|___|___|___|___|___|___|___|___|___|
If you decide to add an element at the end of the list, you can use append
l.append(4)
Resulting in the following list :
___ ___ ___ ___ ___ ___ ___ ___ ___
| | | | | | | | | |
| 1 | 2 | 3 | 4 | | | | | |
|___|___|___|___|___|___|___|___|___|
Now, let's say you forgot an initial 0, and you now wish to add it to the front. You could really well use the insert method (with an insert position of 0) :
l.insert(0, 0)
But there's no space at the beginning of the list ! Python has no choice but to take each and every element, and copy them one at a time in the spot on the direct right :
___ ___ ___ ___ ___ ___ ___ ___ ___
| | | | | | | | | |
| 1 | 2 | 3 | 4 | | | | | |
|___|___|___|___|___|___|___|___|___|
| | |__ |___
| |___ | | First, Python has to copy the four elements
|___ | | | one space to the right
___ _\/ _\/ \/_ _\/ ___ ___ ___ ___
| | | | | | | | | |
| | 1 | 2 | 3 | 4 | | | | |
|___|___|___|___|___|___|___|___|___|
Only then can it insert the 0 at the beginning
___ ___ ___ ___ ___ ___ ___ ___ ___
| | | | | | | | | |
| 0 | 1 | 2 | 3 | | | | | |
|___|___|___|___|___|___|___|___|___|
It may not seem like much for such a small array, but imagine your array is much bigger, and you repeat this operation many times : you would spend so much time building your list !
That is why you won't find a list constructor in languages using arrays for their lists like Python.
Diving further : why the two different models?
You may now be wondering why different languages would prefer different list models, and if one of the two models is superior.
It's because these two data structures have different performance in different contexts. Two examples :
Accessing an element in the middle
Let's suppose you want to get the fifth element of the list.
In the linked list you would need to get :
- the first cons cell
- then the tail of this cell to get the second element
- then the tail of this cell to get the third element
- then the tail of this cell to get the fourth element
- and finally the tail of this cell to get the fifth element
You would thus have to go through 5 references !
With an array, that's much simpler : you know the reference of the first element. You just need to access the reference 4 spots on the right, given the elements are all in a contiguous memory range !
If you need to access random elements of a very large list a great many times, arrays are thus much better.
Inserting an element in the middle
Imagine you now want to insert an element in the middle.
With a linked list :
- you locate the cons cell corresponding to the last element before the insertion point.
- you create a new cons cell, with a head pointing to the element you want to add and the same tail as the cons cell you just located.
- you can now change the tail of this cell to point to the newly created cell.
With an array, just as when adding an element in the middle, you will need to copy every element to the right of the insertion point one space to the right !
In this situation, that's the linked list that is clearly superior.
