Grundlegende Listenoperationen Zeitkomplexität

Die folgende Tabelle zeigt die Zeitkomplexität grundlegender Operationen für verkettete Listen.

Suchoperation

Das Suchen in einer verketteten Liste beinhaltet das Durchlaufen der Liste vom Anfang bis das gewünschte Element gefunden wird. Diese Operation hat eine Zeitkomplexität von O(n) sowohl im schlimmsten als auch im durchschnittlichen Fall. Im Gegensatz zu Arrays unterstützen verkettete Listen keinen direkten Zugriff auf Elemente basierend auf ihrem Index, was zu einer linearen Zeitkomplexität beim Suchen führt.

python
Code kopieren
9
1
2
3
4
5
6
7
8
def search_linked_list(head, target):
  
    current = head
    while current:
        if current.val == target:
            return True
        current = current.next
    return False

Einfügeoperation

Das Einfügen eines Elements in eine verkettete Liste kann effizient durchgeführt werden, indem nur wenige Zeiger aktualisiert werden. Insbesondere müssen wir den Zeiger des Elements aktualisieren, nach dem wir das neue Element einfügen, damit es auf das neue Element zeigt, und der Zeiger des neuen Elements muss auf das nächste Element in der Liste zeigen. Diese Operation hat eine Zeitkomplexität von O(1).

python
Code kopieren
99
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

Löschoperation

Genau wie bei der Einfügeoperation müssen wir die Zeiger der benachbarten Knoten aktualisieren, um den gelöschten Knoten zu umgehen. Dadurch haben wir eine Zeitkomplexität von O(1) für die Löschoperation.

python
Code kopieren
99
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

Hinweis

Beim Einfügen oder Löschen eines Elements in einer verketteten Liste muss der Prozess entsprechend die Zeiger anpassen. Im Gegensatz dazu muss bei Arrays ein Segment des Arrays umgeschrieben werden, um die gleiche Operation zu erreichen.