Complement : les fonctions incontournables des Listes Chainées

Dans cet article , on va rappeler en quelque lignes comment déclarer une liste chaînée , puis on va donner des fonctions souvent utilisées et souvent demandées a l'examen dans les listes chaînées sous formes de questions :
Déclarations d'une Liste , ajouter les éléments dans la liste , supprimer , trier ...
c'est fonctions comme indiqué dans le titre de cet article , elles sont incontournables , vous devez absolument les connaitre .

Comment déclarer une liste chaînée

La liste chaînée est un enchaînement de plusieurs éléments . pour créer la liste en commence par créer ses éléments .

les éléments de la liste chaînée sont toujours des type personnalisé c-a-d des structures , ces structures contient toujours :

• des Champs pour stocker les informations .
• un Champ pour le pointeur contenant l'adresse de l’élément suivant .

la création de la liste chaînée commence toujours par la création d'un pointeur qui pointe sur NULL .

pour accéder a la liste chaînée on est besoin juste du pointeur sur le premier élément . en le note souvent tête ( la tête de la liste ) ou tous simplement L .

Les fonctions

Soit la liste déclarée comme suivant :

typedef struct element{

    // Les champs de stockage
    int a;

    // Le champ du chainage
    struct element * suivant;
};
element * L = NULL ; // la liste contient aucun élément .

L est le pointeur sur le premier élément de la liste , il pointe sur NULL : la liste est vide .

Fonction 1 : element * creerElement( int a )

element * creerElement( int a ){

    element * P;
// En langage C
    P = ( element * )malloc( sizeof(element) );
// En langage C++ 
    P = new element;
// le reste est valable pour les 2 langages
    P->a = a;
    P->suivant = NULL;
    return P;
}

Fonction 2 : element * ajoutElement_fin( element * L , int a )

Maintenant on a la liste , en veut ajouter des éléments a la fin de cette liste .

element * ajoutElement_fin( element * L , int a ){
 
    element * P;
    P = creerElement( a );

    if ( L == NULL ) { return P; }
    else {
        element * R = L;

        while( R->suivant != NULL ) { R = R->suivant; }

            R->suivant = P;
            return L;
    }
}

Fonction 3 : element * ajoutElement_debut( element * L , int a )

element * ajoutElement_debut( element * L , int a ){

    element * P;
    P = creerElement( a );

    P->suivant = L;

    return P;
}

Fonction 4 : void trierListe( element * L )

void trierListe( element * L ){

    if ( L != NULL ){

        element * min = L, *R;

        while ( min->suivant != NULL ){

            R = min->suivant;

            while ( R != NULL ) {
    
                if ( min->a > R->a ) {
                    c = R->a;
                    R->a = min->a;
                    min->a = c;
                }
                R=R->suivant;
            }
            min = min->suivant;
        }
    }
}

Fonction 5 : element * ajout_milieu( element * L , int a )

si on a une liste chaînée triée on peut ajouter un élément a cette liste dans sa place approprie pour que la liste reste triée .

element * ajout_milieu( element * L , int a ){
    element * P;
    P = creerElement( a );

    if ( L==NULL ) return P;
    else {
        if ( L->a > a ) {
            P->suivant = L;
            return P;
        }
        else {
            element * R=L;

            while ( R->suivant->a < a ){

                P->suivant = R->suivant;
                R->suivant = P;

            }
            return L;
        }
    }
}

Fonction 6 : element * chercher( element * L , int a )

cette fonction revoit un pointeur sur l’élément cherché .

element * chercher( element * L , int a ){
    element * R = L;

    while ( R != NULL ) {

        if ( R->a == a ) return R;

        R = R->suivant;
    }

    return NULL;
}