Structure de données: Liste

IFT1025, Programmation 2

Jian-Yun Nie

Points importants

• Utilité d’une structure de données

• Comment utiliser une structure de données de liste existante

• Comment programmer pour gérer soi-même une liste

• D’autres structures souvent utilisées en informatique

Pourquoi une structure de données?

• Structure de données:– Une organisation des informations– Pour faciliter le traitement efficace (tableau,

liste, …)– Pour mieux regrouper les informations pour le

même concept (classe, …)

Structures de données déjà vues

• Tableau: pour organiser une séquence de données– int [ ] a = new int [10];

• Classe: pour regrouper les attributs du même conceptpublic class C {

int a;String name;

}C ref = new C();

a

ref int a:

String name:

0null

Liste

• Utilité: pour organiser une séquence de données• Une structure plus flexible que tableau

Tableau Liste

Taille fixe Taille variable

Ordre entre éléments Ordre

Insertion et enlèvement difficile Plus facile

Accès rapide Plus lent

Illustration

• Entête (node)• noeuds enchaînés

• Chaque noeud enchaîné:– Valeur stockée (A, B, …)– Référence vers le prochain nœud

node

A B C D

Structure de données: Liste

• Deux parties:– Structure pour l’entête

• Référence vers le premier nœud• D’autres attributs optionnels

– Référence vers le dernier nœud– Nombre de nœuds– …

– Structure pour nœud• Structure (ou classe) pour le stockage d’une valeur• Référence vers le prochain nœud• Facultatif:

– Référence vers le nœud précédent (liste doublement chaînée)

Définition d’une liste simplement chaînée

• Entête contenant une référencepublic class Liste{

Noeud premier;

// méthodes pour traiter une liste}

• Nœud contenant un intpublic class Noeud {

int valeur;Noeud prochain;public Noeud (int v, Noeud p){

valeur = v;prochain = p;

}}

Création• Créer une entête:

Liste l = new Liste();

• Créer des nœuds:l.premier = new Noeud(1,

new Noeud(2,

new Noeud(3,null)));

l

null

l

1 2 3 null

Traverser une listepublic class Liste{

…public void print(){

Noeud n = premier;while (n!=null){

System.out.print(n.valeur + "->");n = n.prochain;

}System.out.println("null");

}…Noeud premier;

}

Résultat: 1->2->3->null

Trouver un élément

public class Liste{ …

public Noeud trouver(int v){

Noeud n = premier;while (n != null && n.valeur != v)

n = n.prochain;return n;

}…Noeud premier;

}

Déterminer la longueurpublic class Liste{ …

public int longueur(){

Noeud n = premier;int nb=0;if (premier == null) return 0; // cette ligne peut être enlevéewhile (n != null) {

nb++;n = n.prochain;

}return nb;

}…Noeud premier;

}

Ajouter un élément au débutpublic class Liste{ …

public void ajoutDebut(int v){

premier = new Noeud(v, premier);}

…}

l

1 2 3 null

5

Ajouter un élément à la finpublic class Liste{ …

public void ajoutFin(int v){ Noeud n = premier;

// cas 1: aucun autre élément ajoutéif (premier == null) premier = new Noeud(v,null);// cas 2: il y a déjà des élémentselse { while (n.prochain != null) n = n.prochain;

n.prochain = new Noeud(v,null);}

}…}• Attention: tester sur le prochain• Pas de limite de taille

l

1 2 3 null

5n

Enlever un élément• Besoin de garder la référence sur le précédent élément • Tester sur le prochainpublic class Liste{ …

public void enlever(int v){

Noeud n = premier;// cas 1: Si le premier est nullif (premier == null) return;// cas 2: Si le premier est à enleverif (premier.valeur == v) {

premier = premier.prochain;return;

}// cas 3: sinon, tester sur les autres élémentswhile (n.prochain != null && n.prochain.valeur != v) n = n.prochain;if (n.prochain != null) n.prochain = n.prochain.prochain;

}…}

• Pas besoin de déplacer les autres éléments pour laisser une place (comme tableau)

Attention à l’ordre des tests

Concatenation de 2 listespublic class Liste{ …

public void concat(Liste l){

if (premier == null) {

premier = l.premier;return;

}Noeud n = premier;while (n.prochain != null) n=n.prochain;n.prochain = l.premier;

}…}

// Aller à la fin

Et si?• Si on a une réf. vers le dernier élément?public class Liste

{Noeud premier, dernier;// méthodes pour traiter une liste?

}• Exemple:

public void ajoutFin(int v){ Noeud n = premier;

// cas 1: aucun autre élément ajoutéif (premier == null) premier = dernier = new Noeud(v,null);// cas 2: il y a déjà des élémentselse { dernier.prochain = new Noeud(v,null);

dernier = dernier.prochain;}

}

Traitement récursif

• Itératif: Liste = suite d’éléments– Traitement typique: parcourir la liste avec while

• Récursif: Liste = un élément + reste (une plus petite liste)– Traitement récursif

• Traiter un élément• Traiter le reste par un appel récursif

• Décomposition générale– Cas 1: liste vide (cas d’arrêt de récursion)– Cas 2: liste non vide

• L’élément courant• Appel récursif pour la suite

Déterminer la longueur• Longueur =

– 0, si la liste est vide– 1 + longueur du reste, sinon.

public class Liste{ Noeud premier;

public int longueur(){

if (premier == null) return 0;else return premier.longueur();

}}public class Nœud // Premier option: utiliser la récursion sur les noeuds{ public int longueur()

{// cas 1: pas de récursionif (prochain==null) return 1;// cas 2: récursionelse return 1+ prochain.longueur();

}}

Cet appel est possible seulement quand premier!=null

Illustration

public class Nœud{ public int longueur()

{// cas 1: pas de récursionif (prochain==null) return 1;// cas 2: récursionelse return 1+ prochain.longueur();

}}

l

1 2 3 null

premier.longueur()= longueur()=

1 + ?longueur()=1 + ?

longueur()=1 12

3

Déterminer la longueur (bis)public class Liste{ Noeud premier;

public int longueur(){

return longueur(premier);}

// Deuxième option: utiliser la récursion dans Liste, avec nœud comme paramètrepublic int longueur(Noeud n){

if (n==null) return 0;else return 1+ longueur(n.prochain);

}}

Cet appel est possible même si premier==null

Ajouter à la finpublic class Liste{ …

public void ajoutFin(int v){

// cas 1: aucun autre élément ajoutéif (premier == null) premier = new Noeud(v,null);// cas 2: il y a déjà des élémentselse premier.ajoutFin(v);

}}public class Noeud{

public void ajoutFin(int v){

if (prochain == null) prochain = new Noeud(v,null);else prochain.ajoutFin(v);

}…}

Traiter le cas d’une liste vide

Ajouter un élément dans une liste non-vide

Ajouter à la fin (bis)public class Liste{ …

public void ajoutFin(int v){

// cas 1: aucun autre élément ajoutéif (premier == null) premier = new Noeud(v,null);// cas 2: il y a déjà des élémentselse ajoutFin(premier, v);

}public void ajoutFin(Noeud n, int v) //même nom: ça fonctionne,

//mais déconseillé{

if (n.prochain == null) n.prochain = new Noeud(v,null);else ajoutFin(n.prochain,v);

}…}

Ajouter à la fin (bis-bis)public class Liste{ …

public void ajoutFin(int v){

premier = ajoutFin(premier, v);}public Noeud ajoutFin(Noeud n, int v){

if (n == null) return new Noeud(v,null);else {

n.prochain = ajoutFin(n.prochain,v);return n;

}}

…}

Réflexions

• Les façons récursives d’implanter les autres méthodes:– Enlever un élément– Ajouter au début– Insérer dans l’ordre– Inverser la liste– Concaténer deux liste– Obtenir le i-ième noeud– …

Notion de complexité asymptotique 

• Ne pas mesurer le traitement en temps réel sur un ordinateur (dépendant de l’ordinateur)

• Déterminer une expression de complexité en fonction du nombre d’éléments à traiter (n)

• Notation grand O:– Une approximation– Ignore les constantes:

• O(n+3) = O(n)

• O(4n) = O(n), O(10) = O(1)

– Déterminer par le plus grand facteur• O(n+n2) = O(n2) (car n2 > n)• O(n2+n log n) = O(n2) (car n2 > n log n)

Complexité des opérations

• Longueur: O(n) – n éléments déjà dans la liste

• Trouver un élément: O(n)– En moyenne O(n/2)=O(n)

• Enlever un élément: O(n)– En moyenne O(n/2)

• Ajouter au début: O(1)– Quelques opérations – nombre constante

• Ajouter à la fin: O(n)– Aller à la fin, et ajouter– Améliorable ?

Liste simplement chaînée: amélioration

• Ajouter une référence au dernier élémentpublic class Liste{

Noeud premier;Noeud dernier;

public void ajoutFin(int v){

if (premier==null) premier = dernier = new Noeud(v,null);else {

dernier.prochain = new new Noeud(v,null);dernier = dernier.prochain;

}}…

}

O(n) O(1)

Liste doublement chaînée• Référence vers le prochain nœud• Référence vers le précédent nœud

public class Noeud

{

int valeur;

Noeud prochain;

Noeud precedent;

…

}

• Permet d’avancer et reculer dans la liste

Exemple: Enleverpublic class Liste{

public void enlever(int v){

Noeud n = premier;if (premier == null) return;if (premier.valeur == v) {

premier = premier.prochain;if (premier==null) dernier = null;return;

}while (n != null && n.valeur != v) n = n.prochain;if (n != null) {

n.precedent.prochain = n.prochain;if (n.prochain != null) n.prochain.precedent = n.predcedent;

}}

null

n

1 2 3

Généralisation

• Définir un nœud pour contenir tout Objectpublic class Noeud

{

Object element;

Noeud prochain;

Noeud precedent;

…

}

Réflexion

• Adapter les traitements à cette structure générale avec Object

Tableau v.s. Liste• Tableau (array)

– Taille fixe– Accès rapide avec index (O(1))– Ajouter/enlever un élément: plus difficile (O(n))– À utiliser si

• Beaucoup d’accès aléatoire• Pas besoin de modifier souvent l’ordre des éléments• Nombre d’éléments à stocker déterminée (ou une limite existe)

• Liste– Taille flexible– Accès plus lent (O(n))– Ajouter/enlever un élément: plus facile (O(1))– À utiliser si

• Peu d’accès aléatoire (souvent un parcours de tous les éléments) • Nombre d’élément très variable• Éléments sont souvent re-ordonnés, ajoutés ou enlevés

Allocation de mémoire

• La mémoire est allouée quand on crée un nœud

• Les nœuds enlevés ne sont plus utilisés– Gabbage collector: récupère les mémoires qui

ne sont plus utilisées– Pas besoin de gérer l’allocation et

désallocation de mémoire en Java

De l’implantation vers un type abstrait

• Implantation de Liste pour les éléments contenant int, Object, etc.

• Généralisation– Définir les opérations sur la liste pour tout type de données– Les opérations communes sur une liste: (interface List)

• Ajouter à la fin: boolean add(Object o)• Ajouter à une position: void add(int index, Object o)• Enlever tout: void clear()• Contanir un élément? Boolean contains(Object o)• Vide?: boolean empty()• Enlever le premier o: boolean remove(Object o)• Taille: int size()• …• Iterator: Iterator irerator()

Implantation avec une liste chaînée

• LinkedList

public class LinkedList<E> extends AbstractList<E> {

… private class Node { // an inner class only used in LinkedList private E element; private Node next;

// Create a Node containing specified element. public Node (E element) { this.element = element; this.next = null; }} // end of class Node

} // end of class LinkedList

Implantation LinkedList (cont.)

public class LinkedList<E> extends AbstractList<E> {

private int size;private Node first;

// Create an empty LinkedList<E>.public LinkedList () {

size = 0;first = null;

}…

}

Implantation LinkedList (cont.)• Une méthode interne pour obtenir le i-ième élément/** * The i-th node of this LinkedList. * The LinkedList must be non-empty. * require 0 <= i && i < this.size() */private Node getNode (int i) {

Node p = first;int pos = 0; // p is pos-th Nodewhile (pos != i) {

p = p.next;pos = pos + 1;

}return p;

}

public E get (int index) {Node p = getNode(index);return p.element;

}

Dans LinkedList:abstract Object get(int index)

Implantation LinkedList

• Enlever le i-ième élément

public void remove (int index) {if (index == 0)

if (first!==null) {first = first.getNext(); size--;}else {

Node p = getNode(index-1);if (p!==null) {p.setNext(p.getNext().getNext());

size--;}}

}

Implantation avec tableau?

• À réflechir• Exemple:

– Création: créer un tableau de 10 éléments (à agrandir si nécessaire)

– Chercher le i-ième élément (si i<longueur, retourner tab[i], sinon null)

– Ajouter à la position courante– Ajouter à la fin (ajouter à tab[longueur], longueur++)– Insérer à la i-ième place (déplacer i:fin, ajouter à i)– …

Exemplepublic class ArrayList

{

public ArrayList()

{

tab = new Object[10];

position = 0;

size = 0; //nombre d’éléments

capacity = 10; //taille de tableau

}

public void add(Object o)

{

if (position >= capacity) { …} // doubler la taille

tab[position] = o;

position++;

size++;

}

…

private int size, capacity;

private Object[] tab;

private int position;

}