Listes - Cours

1 Fonctions de base des listes

Une liste est une collection ordonnée d’éléments, pouvant être de types différents. On accède à chaque élément par son index, qui commence à \(0\) et va jusqu’à \(N-1\), où \(N\) est le nombre d’éléments.

1.1 Syntaxe et Complexité en temps

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

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

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

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

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

# Modifier un élément de la liste
listName[index] = item # O(1)

# Insérer un élément dans la liste à un index spécifique
listName.insert(index, item) # O(n)

# Enlever un élément de la liste à un index spécifique
poppedItem = listName.pop(index) # O(n)
# default_end

1.2 Exemple

# exercice: demo
# forbidden_keywords: for, in
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
items = []
print("items:", items, ", size:", len(items))

items = [3.14] * 3
print("items:", items, ", size:", len(items))

items = ["Hello", -29, 3.14, False, 2.72, 27]
print("items:", items, ", size:", len(items))

first1 = items[0]
print("first1:", first1)

last1 = items[len(items) - 1]
print("last1:", last1)

items[len(items) - 1] = "World"
print("items:", items, ", size:", len(items))

items.insert(2, True)
print("items:", items, ", size:", len(items))

items.pop(1)
print("items:", items, ", size:", len(items))
# 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\)

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

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

1.4 Exercice

Comprendre

Quelle est la sortie de ce programme ?

# forbidden_keywords: for, in
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def mystere(list1):
    result = []
    if len(list1) > 0:
        size = len(list1)
        mid = size // 2
        if size % 2 == 1:
            result = [list1[mid]]
        else:
            result = [list1[mid - 1], list1[mid]]
    return result
# default_end
# test_start
print(mystere([1, 2, 3, 4, 5]))
print("C683AKRMaR")
print(mystere([1, 2, 3, 4]))
print("C683AKRMaR")
print(mystere([42]))
print("C683AKRMaR")
print(mystere([]))
# test_end

# default_start
def mystere(list1):                                 # list1 = [1, 2, 3, 4, 5]       | list1 = [1, 2, 3, 4]
    result = []                                     # result = []                   | result = []
    if len(list1) > 0:                              # len(list1) = 5 > 0 -> True    | len(list1) = 4 > 0 -> True
        size = len(list1)                           # size = 5                      | size = 4
        mid = size // 2                             # mid = 5 // 2 = 2              | mid = 4 // 2 = 2
        if size % 2 == 1:                           # 5 % 2 = 1 -> True             | 4 % 2 = 0 -> False
            result = [list1[mid]]                   # result = [list1[2]] = [3]     | 
        else:                                       #                               | 
            result = [list1[mid - 1], list1[mid]]   #                               | result = [list1[1], list1[2]] = [2, 3]
    return result                                   # return [3]                    | return [2, 3]
print(mystere([1, 2, 3, 4, 5]))
print(mystere([1, 2, 3, 4]))
# default_end

Analyser

Quelle est la complexité en temps de la fonction mystere ci-dessus ?

• \(O(1)\) - Constante
• \(O(log(n))\) - Logarithmique
• \(O(n)\) - Linéaire
• \(O(nlog(n))\) - Log Linéaire
• \(O(n^2)\) - Quadratique
• \(O(n^3)\) - Cubique
• \(O(2^n)\) - Exponentielle
• \(O(n!)\) - Factorielle

# default_start
def mystere(list1):
    result = []                                     # 1 affectation + 1 création de liste vide en O(1)
    if len(list1) > 0:                              # 1 comparaison
        size = len(list1)                           # 1 affectation + 1 longueur
        mid = size // 2                             # 1 affectation + 1 division entière
        if size % 2 == 1:                           # 1 comparaison + 1 modulo
            result = [list1[mid]]                   # 1 affectation + 1 accès + 1 création de liste de taille 1 en O(1)
        else:                                       # 1 comparaison
            result = [list1[mid - 1], list1[mid]]   # 1 affectation + 2 accès + 1 création de liste de taille 2 en O(1)
    return result                                   # 1 retour
# T(n) = 2 + 1 + 2 + 2 + max(2 + 3, 2 + 4) + 1
#      = 14
#      = O(1)
# default_end

Concevoir

Écrire une fonction \(firstAndLastItems(list1)\) qui prend en entrée une liste d’éléments \(list1\) et qui retourne une nouvelle liste contenant le premier et le dernier élément de la liste. Si la liste contient un seul élément, la fonction doit retourner une liste contenant cet élément deux fois (comme premier et dernier élément). Si la liste est vide, la fonction doit retourner une liste vide.

# exercice: show
# forbidden_keywords: for, in
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def firstAndLastItems(list1):
    return None
# default_end
# test_start
print(firstAndLastItems([1, 2, 3, 4, 5]))
print("C683AKRMaR")
print(firstAndLastItems(["a", "b", "c"]))
print("C683AKRMaR")
print(firstAndLastItems([True, False]))
print("C683AKRMaR")
print(firstAndLastItems([42]))
print("C683AKRMaR")
print(firstAndLastItems([]))
# test_end
# solution_start
def firstAndLastItems(list1):
    result = []
    if len(list1) > 0:
        result = [list1[0], list1[len(list1) - 1]]
    return result
# solution_end