Tableau Creux

Un tableau creux optimise le stockage des matrices contenant majoritairement des valeurs par défaut (généralement 0). Il conserve uniquement les éléments non-défaut avec leurs coordonnées, réduisant ainsi l'empreinte mémoire.

Principe :

1. Compression : Stocke exclusivement les valeurs non-nulles et leurs positions
2. Accès rapide : Permet une indexation efficace via mappage spatial

public class MatriceCreuse {
    public static void main(String[] args) {
        int[][] matrice = new int[8][8];
        matrice[1][2] = 5;
        matrice[3][4] = 7;
        
        int elementsNonNuls = 0;
        for (int[] ligne : matrice) {
            for (int val : ligne) {
                if (val != 0) elementsNonNuls++;
            }
        }
        
        int[][] creuse = new int[elementsNonNuls + 1][3];
        creuse[0] = new int[]{8, 8, elementsNonNuls};
        
        int index = 1;
        for (int i = 0; i < matrice.length; i++) {
            for (int j = 0; j < matrice[i].length; j++) {
                if (matrice[i][j] != 0) {
                    creuse[index++] = new int[]{i, j, matrice[i][j]};
                }
            }
        }
        
        int[][] matriceRestituee = new int[creuse[0][0]][creuse[0][1]];
        for (int k = 1; k < creuse.length; k++) {
            int[] elem = creuse[k];
            matriceRestituee[elem[0]][elem[1]] = elem[2];
        }
    }
}

File d'Attente Circulaire

Structure linéaire respectant le principe FIFO (First-In-First-Out), implémentée via un buffer circulaire.

class FileCirculaire {
    private int capacite;
    private int tete;
    private int queue;
    private int[] elements;
    
    public FileCirculaire(int taille) {
        capacite = taille;
        elements = new int[capacite];
        tete = queue = -1;
    }
    
    public boolean estVide() {
        return tete == -1;
    }
    
    public boolean estPleine() {
        return (queue + 1) % capacite == tete;
    }
    
    public void enfiler(int valeur) {
        if (estPleine()) throw new IllegalStateException("File saturée");
        if (estVide()) tete = 0;
        queue = (queue + 1) % capacite;
        elements[queue] = valeur;
    }
    
    public int defiler() {
        if (estVide()) throw new IllegalStateException("File vide");
        int valeur = elements[tete];
        if (tete == queue) tete = queue = -1;
        else tete = (tete + 1) % capacite;
        return valeur;
    }
}

Liste Chaînée Simple

Structure séquentielle composée de nœuds liés linéairement, chaque nœud contenant des données et une référence au successeur.

class Noeud {
    int identifiant;
    String donnee;
    Noeud suivant;
    
    Noeud(int id, String data) {
        identifiant = id;
        donnee = data;
    }
}

class ListeChainee {
    private Noeud racine = new Noeud(0, "");
    
    void insererTri(Noeud nouveau) {
        Noeud courant = racine;
        while (courant.suivant != null && courant.suivant.identifiant < nouveau.identifiant) {
            courant = courant.suivant;
        }
        nouveau.suivant = courant.suivant;
        courant.suivant = nouveau;
    }
    
    void supprimer(int id) {
        Noeud precedent = racine;
        while (precedent.suivant != null && precedent.suivant.identifiant != id) {
            precedent = precedent.suivant;
        }
        if (precedent.suivant != null) {
            precedent.suivant = precedent.suivant.suivant;
        }
    }
}

Liste Doublement Chaînée

Variante de liste chaînée avec des références bidirectionnelles permetttant des traversées avant/arrière et des suppressions effciaces.

class NoeudDouble {
    int cle;
    String contenu;
    NoeudDouble precedent;
    NoeudDouble suivant;
}

class ListeDouble {
    private NoeudDouble sentinelle = new NoeudDouble();
    
    void ajouter(NoeudDouble n) {
        NoeudDouble dernier = sentinelle;
        while (dernier.suivant != null) {
            dernier = dernier.suivant;
        }
        dernier.suivant = n;
        n.precedent = dernier;
    }
    
    void eliminer(int cle) {
        NoeudDouble courant = sentinelle.suivant;
        while (courant != null) {
            if (courant.cle == cle) {
                courant.precedent.suivant = courant.suivant;
                if (courant.suivant != null) {
                    courant.suivant.precedent = courant.precedent;
                }
                return;
            }
            courant = courant.suivant;
        }
    }
}