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

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Linked List Time Complexities</title>
    <style>
        table {
            width: 80%;
            margin: 20px auto;
            border-collapse: collapse;
            border: 1px solid #ddd;
        }

        th,
        td {
            padding: 10px;
            text-align: left;
        }

        th {
            background-color: #f2f2f2;
        }

        tr:nth-child(even) {
            background-color: #f2f2f2;
        }

        tr:hover {
            background-color: #ddd;
        }

        th strong {
            font-weight: bold;
        }

        td strong {
            font-weight: bold;
        }
    </style>
</head>

<body>

    <table>
        <tr>
            <th><strong>Operation</strong></th>
            <th><strong>Best Case Time Complexity</strong></th>
            <th><strong>Worst Case Time Complexity</strong></th>
            <th><strong>Average Case Time Complexity</strong></th>
        </tr>
        <tr>
            <td><strong>Insert</strong></td>
            <td>O(1)</td>
            <td>O(1)</td>
            <td>O(1)</td>
        </tr>
        <tr>
            <td><strong>Delete</strong></td>
            <td>O(1)</td>
            <td>O(1)</td>
            <td>O(1)</td>
        </tr>
        <tr>
            <td><strong>Search</strong></td>
            <td>O(1)</td>
            <td>O(n)</td>
            <td>O(n)</td>
        </tr>
    </table>

</body>

</html>


## 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
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
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
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.

Welche der folgenden Aussagen über verkettete Listen ist wahr?

Das Verständnis von Datenstrukturen und Algorithmen: Dies ist es, was fortgeschrittene Fachleute von den anderen unterscheidet. In der modernen Welt wachsender Daten ist es sehr wichtig, große Datenmengen effizient verarbeiten zu können.

In diesem Kurs werden Sie die grundlegendsten Datenstrukturen studieren, die uns helfen, mit großen Datenmengen umzugehen, sowie die grundlegendsten und entscheidenden Konzepte selbst implementieren, damit Sie ein tieferes Verständnis dafür bekommen, wie jede Datenstruktur funktioniert und Sie in der Lage sein werden, zu entscheiden, welche Datenstruktur am besten für Ihre Aufgabe geeignet ist.

Wenn wir etwas Neues lernen, ist es sehr wichtig, sich zuerst mit dem Thema unserer Studie vertraut zu machen. Also lassen Sie uns tiefer eintauchen, was wir in diesem Kurs lernen werden.

Arrays und Listen dienen als grundlegende Datenstrukturen in der Programmierung, wobei Python sie umfassend einsetzt. Dieser Abschnitt bietet einen Überblick über diese Strukturen, geht auf ihre Konzepte ein und hebt ihre Implementierungsnuancen innerhalb der Programmiersprache Python hervor.

Es gibt viele angewandte Aufgaben, bei denen es notwendig ist, mit großen Mengen an strukturierten Daten zu arbeiten, und einfache Datenstrukturen wie ein Array oder eine verkettete Liste möglicherweise nicht mehr ausreichen. In diesem Abschnitt betrachten wir das Konzept eines abstrakten Datentyps und wie verschiedene ADTs es uns ermöglichen, große Datenmengen effizient zu verwalten.

In der realen Welt muss man oft Aufgaben bewältigen, bei denen es notwendig ist, komplexe Abhängigkeiten zwischen verschiedenen Knoten eines Systems oder einer Domäne zu modellieren. Graphen können uns dabei helfen. In diesem Abschnitt werden wir lernen, was ein Graph ist und wie man ihn effizient im Computerspeicher darstellt.

Überblick Über Algorithmen und Datenstrukturen

Grundlegende Listenoperationen Zeitkomplexität

Suchoperation

Einfügeoperation

Löschoperation