Data structures

Array

An array is a contiguous (non-breaking) memory space which contains a certain amount of bytes. How the memory is interpreted depends on how the compiler is configured.

Example: an array with 3 entries interpreted differently.

// Schematic view of a 8 bits / 1 byte array.
[00, 00, 00]
 --  --  --
 0   1   2

// Schematic view of a 16 bits / 2 bytes array.
[00 00, 00 00, 00 00]
 -----  -----  -----
   0      1      2

// Schematic view of a 32 bits / 4 bytes array.
[00 00 00 00, 00 00 00 00, 00 00 00 00]
 -----------  -----------  -----------
      0            1            2

Taking all this into account, it means an array has absolutely no functions like push or pop or shift available in modern languages, where arrays are therefore, more than arrays.

Knowing this, how do you manipulate data?

Get

To access a value, you need to move along the contiguous data. Add the offset multiplied by how big the type is. Ex: Moving to the third entry in a 8 bits array: 2×8 = 16. Skip 16 bits / 2 bytes.

Insert

You cannot grow an array size, which means an insertion will overwrite the existing data.

Delete

You cannot reduce an array size, which means a deletion will replace the existing data with something interpreted as nothing. In some way, a deletion is an insertion.

Linked list

A linked list can be seen as a series of nodes where each node contains a value and points to another node.

There are two versions:

1. A singly linked list can only go forward. The nodes don't have a reference of what came before them.
2. A doubly linked list can go forward or backward. The nodes have a reference to what came before them.

For example:

A singly linked list
-------------
A → B → C → D

A doubly linked list
-------------
A ↔ B ↔ C ↔ D

Inserting, reordering or deleting data means changing the references of the different nodes.

Insert F between A and B:

A → F
F → B
F ← B
A ← F

Logically, linked lists are not contiguous, don't have an index, and can be stored anywhere (which is sometimes referred as heap allocation).

This type of structure has strengths and weaknesses:

• Operations performed at the head or tail of the list are extremely fast (get, insert, delete, etc.)
• Operations performed in the middle of the list require traversing it using a loop since there is no index. It can be slow if the list is big.

Since none of the size of the input or the existing size of the list matters, linked lists have a notation of O(1).