Comprendre les structures de données linéaires en 10 minutes

Les structures de données sont la base de tout ce que tu fais en informatique. Savoir comment elles fonctionnent et quand les utiliser te donnent un avantage fou. Malgré le fait que tout le monde les utilise, ya beaucoup de monde qui n’a aucune idée de comment ça fonctionne. C’est des concepts hyper simples qui vont te servir toute ta carrière.

C’est quoi une structure de données ?

Les structures de données sont différentes façons d’organiser de la donnée dans ton code. Chaque structure de données va organiser ta donnée d’une façon bien particulière. Chaque structure de données a des avantages et des inconvénients. Tu dois te baser dessus pour choisir quelle structure de données utiliser pour faire du code efficace.

Ce qu’on veut c’est accéder rapidement et facilement à de la donnée dans chaque situation. Si tu connais toutes les structures de données et que tu sais comment les utiliser : t’as un avantage fou.

Pourquoi c’est important ?

Chaque problème devrait te faire penser à une structure de données. Sinon tu pars avec un handicap. Les structures de données sont comme des outils pour un bricoleur. Si tu connais pas tous les outils dans la boite à outils, comment tu sais si tu utilises le plus adapté ?

La première fois qu’on m’a parlé de ces concepts, j’étais en cours. Je faisais déjà des sites Internet sur mon temps libre sans toutes ces notions. Ça me semblait complètement inutile et surtout super chiant. Je savais pas à quel point je me foutais dans la merde.

Quelque temps plus tard, j’ai passé un entretien. La première question de cet entretien c’était d’inverser une liste chaînée. J’étais même pas sûr de ma définition d’une liste chaînée à ce moment-là. J’ai vraiment passé un mauvais moment. De retour chez moi j’ai commencé à ne bosser que là-dessus.

Est-ce que ça va te servir de savoir inverser une liste chaînée dans un vrai travail ? Non. Mais si tu passes pas l’entretien, t’accéderas pas au vrai travail. C’est débile ? Oui. Mais c’est pas moi qui fait passer les entretiens.

Donc en résumé :

• ça te donne un avantage fou dans la résolution de problème
• ça te permet d’être plus serein pour les entretiens

Du coup, ça va être un peu scolaire aujourd’hui. Sortez vos cahiers, page 121, on va se concentrer sur la partie facile des structures de données.

On va parler seulement des structures de données linéaires. Dans l’article suivant on parlera des structures de données non-linéaires. On va également utiliser les termes anglais car c’est ceux que tu verras en permanence. Commençons par une structure de données très simple que tu utilises déjà en permanence.

Array (tableau)

C’est quoi ?

Un array est une collection d’éléments qui sont accédés via un indice. Chaque array est stocké dans la mémoire de ta machine. Chaque élément dans ton array est lié à un index qui fait le lien entre l’adresse mémoire et la valeur de chaque élément. Un beau dessin pour mieux comprendre les entrailles de tout ça.

Le fonctionnement est très simple. Pour obtenir la valeur d’un élément, tu vas utiliser son index pour y accéder. L’index va alors aller chercher la valeur de l’élément via son adresse mémoire. Easy !

La première chose à comprendre c’est qu’un array est une séquence finie d’éléments. Tu crées un tableau avec une taille prédéfinie, cette taille est réservée en mémoire et tu pourras plus la changer. Un array ne permet que de gérer un seul type de donnée. Un tableau d’entiers ne pourra pas accueillir de nombres flottants par exemple.

La dernière affirmation est vraie pour les langages de plus bas niveaux comme C, C++ et Java. Si tu viens de Javascript ou Python, c’est pas le cas dans ton monde.

Je savais que t’étais à deux doigts de m’insulter, donc je le précise. Avec Javascript par exemple : les tableaux que tu utilises sont en réalité des objets. Mais quand on parle de structure de données, on parle pas de langage en particulier. Surtout pas de langage de haut niveau comme Javascript.

Implémentation

Regardons rapidement son implémentation. Trois langages différents pour trois fois plus de plaisir.

C++

#include <iostream>

using namespace std;

int main()
{
    int foo [3] = { 1998, 2006, 2018 };  
    
    cout << foo[1] << endl;

    return 0;
}

Python (3.6.9)

from array import *

foo = array('i', [1998, 2006, 2018])

print(foo[2])

Javascript (NodeJS 12.14.0)

foo = [1998, 2006, 2018]

console.log(foo[2])

Avantages & inconvénients

Avantages

• Tu peux maintenir une grande quantité de données aux mêmes endroits.
• Chacun des éléments peut être accédé en temps constant O(1) via son index
• Comme un array est fixe au niveau de sa taille, tu limites fortement tous les problèmes de mémoire type overflow

Inconvénients

• Comme un array est fixe au niveau de sa taille, il est impossible de le faire grossir sans créer un nouvel array
• Un array ne peut contenir qu’un seul type de donnée à la fois

Stack (pile)

C’est quoi ?

Une stack (pile) est une liste d’éléments qui ne peut être manipulée qu’en ajoutant ou enlevant le sommet de la liste. Pour l’image mentale, tu peux imaginer une pile d’assiettes. Le moyen le plus simple d’empiler ou désempiler une pile d’assiettes c’est depuis le dessus de la pile. Une stack c’est pareil avec une liste de valeurs. Attention dessin sur lequel j’ai passé trop de temps pour pas grand-chose.

Ce qui est important à comprendre c’est que la stack a un mode de fonctionnement dit Last In First Out (LIFO). Les derniers éléments ajoutés seront les premiers enlevés. Ce fonctionnement est géré via une interface avec quatre opérations principales.

• Push : ajouter un nouvel élément au sommet de la stack
• Pop : enlever l’élément au sommet de la stack
• Top : retourner l’élément au sommet de la stack
• IsEmpty : retourner true si la stack est vide

Et le truc de fifou, c’est que toutes ces opérations sont exécutées en temps constant O(1) ! Ça veut dire qu’avec l’algo qui va bien, tu peux traiter de la donnée extrêmement rapidement. Et c’est ça le plan quand tu utilises des structures de données.

Les stacks sont partout. Par exemple si tu regardes ton historique maintenant en faisant un CTRL+H tu vas tomber sur une stack. OK, regardons à quoi ça ressemble si on implémente une stack dans le code.

Implémentation

C++

#include <iostream>
#include <stack>

using namespace std;

int main () 
{
    stack <int> myStack;

    // push operation
    myStack.push(1998); 
    myStack.push(2006); 
    myStack.push(2018); 

    // top operation
    cout << "\ntop of the stack is " << myStack.top(); 

    // pop operation
    myStack.pop(); 

    // isEmpty operation
    cout << "\nstack is empty ? " << myStack.empty() << "\n";

    return 0; 
}

Python (3.6.9)

from collections import deque 
  
myStack = deque() 

# push operation
myStack.appendleft(1998) 
myStack.appendleft(2006) 
myStack.appendleft(2018) 

# top operation
print(myStack[0])
  
# pop operation
print(myStack.popleft()) 

# isEmpty operation
print(len(myStack))

¸Javascript (NodeJS 12.14.0)

myStack = []

// push operation
myStack.push(1998)
myStack.push(2006)
myStack.push(2018)

// top operation
console.log(myStack[myStack.length - 1])

// pop operation
myStack.pop()

// isEmpty operation
console.log(myStack.length)

Avantages & inconvénients

Avantages

• Permets de gérer de la data en mode LIFO
• Certaines opérations seront faites en temps constant O(1)

Inconvénients

• De par la nature LIFO de la stack, tu ne peux pas accéder directement à un élément au milieu de la stack en temps constant O(1) comme avec un array
• Créer trop d’éléments dans une stack peut amener à un débordement. Le fameux stack overflow.

Queue (file)

C’est quoi ?

Une queue (file) est une liste d’éléments qui ne peut être manipulée qu’en ajoutant un élément à l’arrière (rear) de la liste ou en enlevant un élément à l’avant (front) de la liste. C’est très simple d’en faire une image mentale puisque c’est le même fonctionnement que n’importe quelle vraie file d’attente dans la vraie vie. Allez, une oeuvre d’art de plus.

Comme pour la stack, ce qui est important de comprendre avec la queue c’est son fonctionnement dit First In First Out (FIFO). On retrouve également une interface avec quatre opérations.

• Push (enqueue) : ajouter un nouvel élément à l’arrière de la queue
• Pop (dequeue) : enlever un élément à l’avant de la queue
• Front (peek) : retourner l’élément à l’avant de la queue
• IsEmpty : retourner true si la queue est vide

Évidement, tout ça en temps constant O(1) comme pour la stack. Les queues sont également présentes partout en informatique. Du fonctionnement d’une imprimante à RabbitMQ les exemples sont légions.

Regardons à quoi ça ressemble maintenant !

Implémentation

C++

#include <iostream> 
#include <queue> 
  
using namespace std; 
  
int main() 
{ 
    queue <int> myQueue;

    // push operation
    myQueue.push(1998);
    myQueue.push(2006);
    myQueue.push(2018);
    
    // pop operation
    myQueue.pop();

    // top operation
    cout << "\nfront of the queue is " << myQueue.front();

    // isEmpty operation
    cout << "\nqueue is empty ? " << myQueue.empty() << "\n";

    return 0; 
} 

Python (3.6.9)

from collections import deque 
  
myQueue = deque() 

# push operation
myQueue.append(1998) 
myQueue.append(2006) 
myQueue.append(2018) 

# top operation
print(myQueue[0])
  
# pop operation
print(myQueue.popleft())

# isEmpty operation
print(len(myQueue))

¸Javascript (NodeJS 12.14.0)

myQueue = []

// push operation
myQueue.push(1998)
myQueue.push(2006)
myQueue.push(2018)

// top operation
console.log(myQueue[0])

// pop operation
myQueue.shift()

// isEmpty operation
console.log(myQueue.length)

Avantages & inconvénients

Les avantages et les inconvénients sont très proches de la stack !

Avantages

• Permet de gérer de la data en mode FIFO
• Certaines opérations seront faites en temps constant O(1)

Inconvénients

• De par la nature FIFO de la stack, tu ne peux pas accéder directement à un élément au milieu de la stack en temps constant O(1) comme avec un array

Linked List (liste chaînée)

C’est quoi ?

Une linked list (liste chaînée) est une séquence de nœuds liés aux autres via un pointeur de façon unidirectionnelle. Chaque séquence commence avec un nœud appelé HEAD qui signale le point d’entrée de la liste. Chaque nœud peut contenir la data que tu veux et à une structure bien particulière composée de deux éléments.

1. Value : la valeur de la donnée contenue dans le nœud
2. Next : la référence (pointeur) vers le node suivant

Ça ressemble comme deux gouttes d’eau au fonctionnement de la blockchain dont on avait discuté. Je vois ça dans ma tête quand j’imagine une linked list.

Tu l’as deviné, tu ne peux pas accéder directement à un nœud comme avec un array, avec une linked list. Accéder directement à un nœud avec une linked list ne peut être fait qu’en temps linéaire O(n). Et aujourd’hui, on parle que de linked list unidirectionnel, mais sache que les variantes bidirectionnelles et circulaires existent aussi. On en parlera plus tard dans l’année.

Concernant les opérations, les plus utilisées sont les suivantes :

• Insert : ajouter un nouveau nœud après un nœud existant
• Remove : supprimer un nœud après un nœud existant
• Front : retourner le premier nœud (HEAD)
• IsEmpty : retourner true si la linked list est vide

Allez, on met les mains dedans.

Implémentation

C++

#include<iostream> 
#include<forward_list>  

using namespace std; 

int main() 
{
    forward_list<int> myLinkedList;

    myLinkedList.assign({1998, 2018, 2020});

    // insert operation
    myLinkedList.insert_after(myLinkedList.begin(), 2006);

    // remove operation
    myLinkedList.remove(2020);

    // front  operation
    cout << "Show front on the linked list : " << myLinkedList.front() << "\n";

    // isEmpty operation
    cout << "\nqueue is empty ? " << myLinkedList.empty() << "\n";

    cout << "The forward list after insert_after operation : ";

    for (int&node : myLinkedList) 
        cout << node << " ";
    cout << endl;

    return 0;
}

Python (3.6.9)

class Node:
    def __init__(self, value = None):
        self.value = value
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None


    def __iter__(self):
        node = self.head

        while node is not None:
            yield node
            node = node.next


    def insertAtBegining(self, node):
        node.next = self.head
        self.head = node


    def isEmpty(self):
        if not self.head:
            return 1
        return 0


    def removeNode(self, node_to_remove):
        if self.head == node_to_remove:
            self.head = self.head.next
            return

        previous_node = self.head
        for node in self:
            if node == node_to_remove:
                previous_node.next = node.next
                return
            previous_node = node


myLinkedList = LinkedList()

firstNode = Node(1998)
secondNode = Node(2006)
badNode = Node(2020)
thirdNode = Node(2018)

secondNode.next = badNode
badNode.next = thirdNode

myLinkedList.head = secondNode

# insert operation
myLinkedList.insertAtBegining(firstNode)

# remove operation
myLinkedList.removeNode(badNode)

# front operation
print(myLinkedList.head.value)

# isEmpty operation
print(myLinkedList.isEmpty())

# show linked list
for node in myLinkedList:
    print(node.value)

Javascript (NodeJS 12.14.0)

class Node {
    constructor (value = null) {
        this.value = value
        this.next = null
    }
}

class LinkedList {
    constructor () {
        this.head = null
    }

    * nodes() {
        let node = this.head

        while (node != null){
            yield node
            node = node.next
        }
    }

    insertAtBegining(node) {
        node.next = this.head
        this.head = node
    }

    isEmpty() {
        if(!this.head) return 1

        return 0
    }

    removeNode(nodeToRemove) {
        if (this.head === nodeToRemove) {
            this.head = this.head.next
            return
        }

        let previous_node = this.head

        for(let node of this.nodes()) {
            if (node === nodeToRemove) {
                previous_node.next = node.next
                return
            }

            previous_node = node
        }
    }
}

const myLinkedList = new LinkedList()

firstNode = new Node(1998)
secondNode = new Node(2006)
badNode = new Node(2020)
thirdNode = new Node(2018)

secondNode.next = badNode
badNode.next = thirdNode

myLinkedList.head = secondNode

// insert operation
myLinkedList.insertAtBegining(firstNode)

// remove operation
myLinkedList.removeNode(badNode)

// front operation
console.log(myLinkedList.head.value)

// isEmpty operation
console.log(myLinkedList.isEmpty())

// show linked list
for(let node of myLinkedList.nodes()) {
    console.log(node.value)
}

Avantages & Inconvénients

Avantages

• La taille d’une linked list n’est pas fixée dans la mémoire, c’est donc très flexible à l’utilisation
• Certaines opérations d’insertion et de suppression peuvent être faites en temps constant O(1)

Inconvénients

• Tu ne peux pas accéder directement à un élément au milieu de la stack comme avec un array
• De l’espace mémoire, en plus de la valeur, est utilisé pour chaque nœud pour les pointeurs

Avec tout ça, tu as déjà une bonne base pour la suite. On est déjà prêt pour l’article de la semaine prochaine !

Épilogue

Voilà, fin du cours. Évidemment, c’est juste une introduction. Tu devrais aller mettre les mains dedans par toi même pour vraiment comprendre. Je te dis à la semaine prochaine pour discuter des structures de données non linéaires !