Structure des nœuds de la liste chaînée

Pour implémenter une liste chaînée doublement liée, chaque nœud doit contenir un pointeur vers le nœud suivant, un pointeur vers le nœud précédent, et les données qu'il stocke. Nous utilisons un modèle de classe pour permettre aux nœuds de stocker n'importe quel type de données.

template<class T>
struct list_node {
    list_node<T>* next;
    list_node<T>* pre;
    T data;

    // Constructeur pour initialiser un nœud avec une valeur par défaut
    list_node(const T& val = T())
        : next(nullptr), pre(nullptr), data(val) {}
};

Encapsulation des itérateurs

Afin de fournir une interface d'accès aux éléments siimlaire à celle des conteneurs STL comme std::vector, nous devons encapsuler les pointeurs de nœuds dans une classe d'itérateur. Cette clase doit surcharger les opérateurs ++, --, * et -> pour permettre la navigation et l'accès aux données.

La classe d'itérateur est rendue générique avec trois modèles : T pour le type de données, Ref pour le type de référence retourné par operator*, et f pour le type de pointeur retourné par operator->. Ceci est crucial pour distinguer les itérateurs modifiables des itérateurs constants.

template<class T, class Ref, class Ptr>
struct list_iterator {
    using node = list_node<T>;
    using self = list_iterator<T, Ref, Ptr>;
    node* _node; // Pointeur vers le nœud actuel

    // Constructeur de l'itérateur
    list_iterator(node* n) : _node(n) {}

    // Opérateur pour accéder aux membres de l'objet pointé (ex: it->member)
    Ptr operator->() {
        return &(_node->data);
    }

    // Opérateur de déréférencement (ex: *it)
    Ref operator*() {
        return _node->data;
    }

    // Opérateur d'incrémentation préfixée (ex: ++it)
    self& operator++() {
        _node = _node->next;
        return *this;
    }

    // Opérateur d'incrémentation postfixée (ex: it++)
    self operator++(int) {
        self temp(_node);
        _node = _node->next;
        return temp;
    }

    // Opérateur de décrémentation préfixée (ex: --it)
    self& operator--() {
        _node = _node->pre;
        return *this;
    }

    // Opérateur de décrémentation postfixée (ex: it--)
    self operator--(int) {
        self temp(_node);
        _node = _node->pre;
        return temp;
    }

    // Opérateurs de comparaison pour vérifier l'égalité des itérateurs
    bool operator==(const self& other) const {
        return _node == other._node;
    }

    bool operator!=(const self& other) const {
        return _node != other._node;
    }
};

Implémentation de la classe list

Constructeurs

La liste utilise un nœud sentinelle (_head) pour simplifier la gestion des cas limites (liste vide, insertion/suppression aux extrémités). Les constructeurs permettent d'initialiser la liste vide, à partir d'une plage d'itérateurs, par copie, ou via une liste d'initialisation.

template<class T>
class list {
private:
    using Node = list_node<T>;
    Node* _head; // Nœud sentinelle
    size_t _size;

    // Initialise la liste avec un nœud sentinelle
    void emptylist() {
        _head = new Node();
        _head->next = _head;
        _head->pre = _head;
        _size = 0;
    }

public:
    // Alias pour les types d'itérateurs
    using iterator = list_iterator<T, T&, T*>;
    using const_iterator = list_iterator<T, const T&, const T*>;

    // Constructeur par défaut (liste vide)
    list() {
        emptylist();
    }

    // Constructeur à partir d'une liste d'initialisation
    list(std::initializer_list<T> il) {
        emptylist();
        for (const auto& elem : il) {
            push_back(elem);
        }
    }

    // Constructeur à partir d'une plage d'itérateurs
    template<class InputIterator>
    list(InputIterator first, InputIterator last) {
        emptylist();
        while (first != last) {
            push_back(*first);
            ++first;
        }
    }

    // Constructeur de copie
    list(const list& other) {
        emptylist();
        for (const auto& elem : other) {
            push_back(elem);
        }
    }

    // Opérateur d'affectation par copie
    list& operator=(const list& other) {
        if (this != &other) {
            clear(); // Libère les ressources actuelles
            for (const auto& elem : other) {
                push_back(elem);
            }
        }
        return *this;
    }

    // Destructeur
    ~list() {
        clear();
        delete _head;
        _head = nullptr;
    }

    // Méthode pour échanger le contenu de deux listes
    void swap(list& other) {
        std::swap(this->_head, other._head);
        std::swap(this->_size, other._size);
    }

    // Itérateurs begin() et end()
    iterator begin() {
        return iterator(_head->next);
    }

    iterator end() {
        return iterator(_head);
    }

    const_iterator begin() const {
        return const_iterator(_head->next);
    }

    const_iterator end() const {
        return const_iterator(_head);
    }

    size_t size() const {
        return _size;
    }

    bool empty() const {
        return _size == 0;
    }
};

Insertion et suppression

Les opérations d'insertion et de suppression sont réalisées en manipulant les pointeurs next et pre des nœuds adjacents. La méthode insert insère un nouvel élément avant l'itérateur spécifié, tandis que erase supprime l'élément pointé par l'itérateur et retourne un itérateur vers l'élément suivant.

    // Ajoute un élément à la fin de la liste
    void push_back(const T& val) {
        Node* newNode = new Node(val);
        Node* lastNode = _head->pre;

        newNode->pre = lastNode;
        newNode->next = _head;
        lastNode->next = newNode;
        _head->pre = newNode;
        ++_size;
    }

    // Supprime le dernier élément de la liste
    void pop_back() {
        if (empty()) return;
        Node* toDelete = _head->pre;
        Node* prevNode = toDelete->pre;

        prevNode->next = _head;
        _head->pre = prevNode;
        delete toDelete;
        --_size;
    }

    // Ajoute un élément au début de la liste
    void push_front(const T& val) {
        insert(begin(), val);
    }

    // Supprime le premier élément de la liste
    void pop_front() {
        if (empty()) return;
        erase(begin());
    }

    // Insère un élément avant la position spécifiée par l'itérateur
    void insert(iterator pos, const T& val) {
        Node* newNode = new Node(val);
        Node* prevNode = pos._node->pre; // Le nœud avant la position d'insertion

        newNode->pre = prevNode;
        newNode->next = pos._node;
        prevNode->next = newNode;
        pos._node->pre = newNode;
        ++_size;
    }

    // Supprime l'élément à la position spécifiée par l'itérateur
    // Retourne un itérateur vers l'élément suivant
    iterator erase(iterator pos) {
        if (empty() || pos == end()) return end();

        Node* toDelete = pos._node;
        Node* prevNode = toDelete->pre;
        Node* nextNode = toDelete->next;

        prevNode->next = nextNode;
        nextNode->pre = prevNode;
        delete toDelete;
        --_size;
        return iterator(nextNode); // Retourne l'itérateur vers le nœud suivant
    }

    // Supprime tous les éléments de la liste (sauf le nœud sentinelle)
    void clear() {
        iterator it = begin();
        while (it != end()) {
            it = erase(it); // erase retourne l'itérateur vers le prochain élément valide
        }
    }

Gession des types personnalisés

Lorsque la liste contient des types personnalisés, il est nécessaire de s'assurer que ces types supportent les opérations requises (comme l'affectation, la copie, et potentiellement l'opérateur << pour l'affichage). L'opérateur -> de l'itérateur est particulièrement utile pour accéder aux membres des objets personnalisés directement via l'itérateur.

void list_test_custom_type() {
    struct Data {
        int id;
        std::string name;
    };

    jcm::list<Data> dataList;
    dataList.push_back({1, "Alpha"});
    dataList.push_back({2, "Beta"});

    // Utilisation de l'itérateur avec operator->
    auto it = dataList.begin();
    while (it != dataList.end()) {
        std::cout << "ID: " << it->id << ", Name: " << it->name << std::endl;
        ++it;
    }
}