Le tableau suivant montre la complexité temporelle des opérations de base pour les listes chaînées.

Opération de Recherche

La recherche dans une liste chaînée implique de parcourir la liste depuis le début jusqu'à ce que l'élément souhaité soit trouvé. Cette opération a une complexité temporelle de O(n) dans les pires et les cas moyens. Contrairement aux tableaux, les listes chaînées ne prennent pas en charge l'accès direct aux éléments en fonction de leur index, ce qui entraîne une complexité temporelle linéaire pour la recherche.

def search_linked_list(head, target):
  
    current = head
    while current:
        if current.val == target:
            return True
        current = current.next
    return False

Opération d'Insertion

Insérer un élément dans une liste chaînée peut être fait efficacement en mettant à jour seulement quelques pointeurs. Plus précisément, nous devons mettre à jour le pointeur de l'élément après lequel nous insérons le nouvel élément, en veillant à ce qu'il pointe vers le nouvel élément, et le pointeur du nouvel élément doit pointer vers l'élément suivant dans la liste. Cette opération a une complexité temporelle de O(1).

def insert_node(head, val, position):
   
    if position == 0:
        new_node = ListNode(val)
        new_node.next = head
        return new_node
    
    current = head
    for _ in range(position - 1):
        if current is None:
            raise ValueError("Position out of range")
        current = current.next
    
    new_node = ListNode(val)
    new_node.next = current.next
    current.next = new_node
    
    return head

Opération de Suppression

Tout comme dans l'opération d'insertion, nous devons mettre à jour les pointeurs des nœuds adjacents pour contourner le nœud supprimé. En conséquence, nous avons une complexité temporelle de O(1) pour l'opération de suppression.

def delete_node(head, target):
    
    # If the list is empty, return None
    if not head:
        return None
    
    # If the target is at the head, move the head to the next node
    if head.val == target:
        return head.next
    
    # Search for the target value while keeping track of the previous node
    prev = head
    current = head.next
    while current:
        if current.val == target:
            prev.next = current.next
            return head
        prev = current
        current = current.next
    
    return head

Note

Lors de l'insertion ou de la suppression d'un élément dans une liste chaînée, le processus implique d'ajuster les pointeurs en conséquence. En revanche, lors du travail avec des tableaux, pour réaliser la même opération, un segment du tableau doit être réécrit.