Listes - Cours

1 Liste (List)

Une liste est une collection ordonnée d’éléments pouvant être de différents types, avec une longueur dynamique permettant à la liste de varier en taille après sa création. Vous pouvez ajouter ou supprimer des éléments sans avoir besoin de recréer la liste, contrairement aux tableaux.

Figure 1: Créer une liste
Figure 2: Lire la taille de la liste
Figure 3: Lire un élément de la liste
Figure 4: Modifier un élément de la liste
Figure 5: Insérer un élément dans la liste
Figure 6: Enlever un élément de la liste

1.1 Syntaxe et Complexité en temps

# exercice: show
# default_start
# Créer une liste vide
listName = List() # O(1)

# Créer une liste en spécifiant tous ses élements
listName = List([item1, item2, item3, ..., itemN]) # O(n)

# Créer une liste en spécifiant un élément par défaut et sa taille initiale
listName = List([defaultItem] * listSize) # O(n)

# Lire la taille de la liste
listSize = listName.size() # O(1)

# Lire un élément de la liste
item = listName.get(index) # O(1)

# Modifier un élément de la liste
listName.set(index, item) # O(1)

# Insérer un élément à l'indice donné
listName.insert(index, item) # O(n)

# Enlever un élément de la liste
item = listName.remove(index) # O(n)

# default_end

1.2 Exemple

# exercice: demo
# default_start
items = List([1, 2, 3])
print("items:", items, ", size:", items.size())

first1 = items.get(0)
print("first1:", first1)

last1 = items.get(items.size() - 1)
print("last1:", last1)

items.set(items.size() - 1, 4)
print("items:", items, ", size:", items.size())

items.insert(2, 3)
print("items:", items, ", size:", items.size())

items.remove(1)
print("items:", items, ", size:", items.size())
# default_end

1.3 Premier pas

  1. Créer une liste vide \(myList\)
  2. Afficher la chaine de caractère \(\q{myList:}\) suivie de la liste \(myList\)
  3. Insérer sucessivement les valeurs \(3.14\), \(-29\) et \(\q{Hello}\) au début de la liste \(myList\)
  4. Afficher la chaine de caractère \(\q{myList:}\) suivie de la liste \(myList\)
  5. Insérer sucessivement les valeurs \(False\), \(6.27\) et \(27\) à la fin de la liste \(myList\)
  6. Afficher la chaine de caractère \(\q{myList:}\) suivie de la liste \(myList\)
  7. Remplacer les six éléments de la liste \(myList\) par \(10\), \(11\), \(12\), \(13\), \(14\) et \(15\)
  8. Afficher la chaine de caractère \(\q{myList:}\) suivie de la liste \(myList\)
  9. Tant qu’il reste plus de deux éléments dans la liste \(myList\):
    1. Enlever l’élement au début de la liste
    2. Enlever l’élement à la fin de la liste
    3. Afficher la chaine de caractère \(\q{myList:}\) suivie de la file \(myList\)

Votre réponse

# exercice: check 
# default_start
print("Hello, World!")

# default_end
# solution_start
myList = List([])
print("myList:", myList)
myList.insert(0, 3.14)
myList.insert(0, -29)
myList.insert(0, "Hello")
print("myList:", myList)
myList.insert(myList.size(), False)
myList.insert(myList.size(), 6.27)
myList.insert(myList.size(), 27)
print("myList:", myList)
myList.set(0, 10)
myList.set(1, 11)
myList.set(2, 12)
myList.set(3, 13)
myList.set(4, 14)
myList.set(5, 15)
print("myList:", myList)
while myList.size() > 2:
    myList.remove(0)
    myList.remove(myList.size() - 1)
    print("myList:", myList)
# solution_end

2 File (Queue)

Une file (ou queue en anglais) est une liste qui suit le principe FIFO (First In, First Out), où le premier élément ajouté est le premier à être retiré.

Figure 7: Créer une file
Figure 8: Lire la taille de la file
Figure 9: Lire l’élément en tête de file
Figure 10: Enlever l’élément en tête de file
Figure 11: Ajouter un élément à la file

2.1 Syntaxe et Complexité en temps

# exercice: show
# default_start
# Créer une file vide
queueName = Queue() # O(1)

# Créer une file en spécifiant tous ses élements
queueName = Queue([item1, item2, item3, ..., itemN]) # O(n)

# Créer une file en spécifiant un élément par défaut et sa taille initiale
queueName = Queue([defaultItem] * defaultSize) # O(n)

# Lire la taille de la file
queueSize = queueName.size() # O(1)

# Lire l'élement en tête de file
head = queueName.head() # O(1)

# Enlever l'élement en tête de file
head = queueName.dequeue() # O(1)

# Ajouter un élement à la file
queueName.enqueue(item) # O(1)
# default_end

2.2 Exemple

# exercice: demo
# default_start
queue1 = Queue()
print("queue1:", queue1, ", size:", queue1.size())

queue1.enqueue(1)
print("queue1:", queue1, ", size:", queue1.size())

queue1.enqueue(2)
print("queue1:", queue1, ", size:", queue1.size())

queue1.enqueue(3)
print("queue1:", queue1, ", size:", queue1.size())

item1 = queue1.head()
print("item1:", item1)

item2 = queue1.dequeue()
print("queue1:", queue1, ", size:", queue1.size())

item3 = queue1.dequeue()
print("queue1:", queue1, ", size:", queue1.size())

item4 = queue1.dequeue()
print("queue1:", queue1, ", size:", queue1.size())
# default_end

2.3 Premier pas

  1. Créer une file vide \(myQueue\);
  2. Afficher la chaine de caractère \(\q{myQueue:}\) suivie de la file \(myQueue\)
  3. Ajouter sucessivement les valeurs \(3.14\), \(-29\) et \(\q{Hello}\) à la fin de la file \(myQueue\)
  4. Afficher la chaine de caractère \(\q{myQueue:}\) suivie de la file \(myQueue\)
  5. Tant que la file \(myQueue\) n’est pas vide:
    1. Créer une variable \(item\) qui contient la tête de la file \(myQueue\)
    2. Afficher la chaine de caractère \(\q{item:}\) suivie de la variable \(item\)
    3. Enlever la tête de la file
    4. Afficher la chaine de caractère \(\q{myQueue:}\) suivie de la file \(myQueue\)

Votre réponse

# exercice: check 
# default_start
print("Hello, World!")

# default_end
# solution_start
myQueue = Queue([])
print("myQueue:", myQueue)
myQueue.enqueue(3.14)
myQueue.enqueue(-29)
myQueue.enqueue("Hello")
print("myQueue:", myQueue)
while myQueue.size() > 0:
    item = myQueue.head()
    print("item:", item)
    myQueue.dequeue()
    print("myQueue:", myQueue)
# solution_end

3 Pile (Stack)

Une pile (ou stack en anglais) est une liste qui suit le principe LIFO (Last In, First Out), où le dernier élément ajouté est le premier à être retiré.

Figure 12: Créer une pile
Figure 13: Lire la taille de la pile
Figure 14: Lire l’élément en tête de pile
Figure 15: Enlever l’élément en tête de pile
Figure 16: Ajouter un élément à la pile

3.1 Syntaxe et Complexité en temps

# exercice: show
# default_start
# Créer une pile vide
stackName = Stack() # O(1)

# Créer une pile en spécifiant tous ses élements
stackName = Stack([item1, item2, item3, ..., itemN]) # O(n)

# Créer pile en spécifiant un élément par défaut et sa taille initiale
stackName = Stack([defaultItem] * defaultSize) # O(n)

# Lire la taille de la pile
stackSize = stackName.size() # O(1)

# Lire l'élement en tête de pile
head = stackName.head() # O(1)

# Enlever l'élement en tête de pile
head = stackName.destack() # O(1)

# Ajouter un élement en tête de pile
stackName.enstack(item) # O(1)
# default_end

3.2 Exemple

# exercice: demo
# default_start
stack1 = Stack()
print("stack1:", stack1, ", size:", stack1.size())

stack1.enstack(1)
print("stack1:", stack1, ", size:", stack1.size())

stack1.enstack(2)
print("stack1:", stack1, ", size:", stack1.size())

stack1.enstack(3)
print("stack1:", stack1, ", size:", stack1.size())

item1 = stack1.head()
print("item1:", item1)

item2 = stack1.destack()
print("stack1:", stack1, ", size:", stack1.size())

item3 = stack1.destack()
print("stack1:", stack1, ", size:", stack1.size())

item4 = stack1.destack()
print("stack1:", stack1, ", size:", stack1.size())
# default_end

3.3 Premier pas

  1. Créer une pile vide \(myStack\)
  2. Afficher la chaine de caractère \(\q{myStack:}\) suivie de la pile \(myStack\)
  3. Ajouter sucessivement les valeurs \(3.14\), \(-29\) et \(\q{Hello}\) en tête de la pile \(myStack\)
  4. Afficher la chaine de caractère \(\q{myStack:}\) suivie de la pile \(myStack\)
  5. Tant que la pile \(myStack\) n’est pas vide:
    1. Créer une variable \(item\) qui contient la tête de la file \(myStack\)
    2. Afficher la chaine de caractère \(\q{item:}\) suivie de la variable \(item\)
    3. Enlever la tête de la pile
    4. Afficher la chaine de caractère \(\q{myStack:}\) suivie de la pile \(myStack\)

Votre réponse

# exercice: check 
# default_start
print("Hello, World!")

# default_end
# solution_start
myStack = Stack([])
print("myStack:", myStack)
myStack.enstack(3.14)
myStack.enstack(-29)
myStack.enstack("Hello")
print("myStack:", myStack)
while myStack.size() > 0:
    item = myStack.head()
    print("item:", item)
    myStack.destack()
    print("myStack:", myStack)
# solution_end