Eine **verkettete Liste** ist eine Datenstruktur, die aus einer Sequenz von Elementen besteht, die als **Knoten** bezeichnet werden. Jeder Knoten enthält Daten und eine **Referenz** auf den nächsten Knoten in der Sequenz.     
Im Gegensatz zu Arrays haben verkettete Listen **keine feste Größe im Speicher** und **speichern keine Elemente in zusammenhängenden Speicherorten**. Stattdessen verwenden sie Zeiger, um Knoten zu verbinden, was eine dynamische Speicherzuweisung und eine effiziente Einfügung und Löschung von Elementen ermöglicht.

Der nächste Abschnitt des Codes veranschaulicht dieses Konzept.

<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Linked List vs Array Comparison</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>Feature</strong></th>
        <th><strong>Linked List</strong></th>
        <th><strong>Array</strong></th>
    </tr>
    <tr>
        <td><strong>Dynamic Size</strong></td>
        <td>Linked lists can dynamically grow or shrink in size by allocating or deallocating memory for nodes.</td>
        <td>Arrays have a fixed size defined at the time of declaration and cannot easily change size during runtime.</td>
    </tr>
    <tr>
        <td><strong>Memory Allocation</strong></td>
        <td>Each node in a linked list occupies memory dynamically, allowing for efficient memory usage.</td>
        <td>Arrays store elements in contiguous memory locations, which may lead to memory wastage or insufficient memory for large arrays.</td>
    </tr>
    <tr>
        <td><strong>Insertion/Deletion</strong></td>
        <td>Linked lists offer efficient insertion and deletion operations by adjusting pointers.</td>
        <td>Arrays may require shifting elements to accommodate insertions or deletions in the middle, resulting in less efficient operations.</td>
    </tr>
    <tr>
        <td><strong>Random Access</strong></td>
        <td>Linked lists do not support efficient random access to elements, requiring traversal from the beginning to locate an element.</td>
        <td>Arrays support efficient random access to elements using indexing, allowing direct access to any element in constant time.</td>
    </tr>
    <tr>
        <td><strong>Traversal</strong></td>
        <td>Linked lists require traversal from the beginning to the desired position, which may result in slower access time for large lists.</td>
        <td>Arrays allow for fast traversal using indexing, providing efficient access to elements at any position.</td>
    </tr>
</table>

</body>
</html>


## Implementierung einer verketteten Liste

from lolviz import *
from IPython.display import display_png

class Node:

  def __init__(self, data):
    self.value = data
    self.next = None

# Let's create some nodes
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

# Then let's couple them into a linked list
node1.next = node2
node2.next = node3

display_png(objviz(node1))

>Hinweis
>
>Beachten Sie, dass die eingebaute `list`-Struktur in Python konzeptionell keine Liste ist - die `list`-Struktur wird als **dynamisches Array** implementiert, das Elemente verschiedener Datentypen aufnehmen kann. Es ist einem Array ähnlich, bietet jedoch zusätzliche Funktionalitäten und Optimierungen.

Im Gegensatz zu einem Array, bei dem wir direkten Zugriff auf jedes Element haben, haben wir in der verketteten Liste **nur direkten Zugriff auf das erste Element**, und wir können auf jedes andere Element nur über die Kette von Referenzen zugreifen.

In einer verketteten Liste, was ist der Zweck des "next"-Zeigers?

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

Verkettete Liste Datenstruktur

Verkettete Liste vs Array

Implementierung einer verketteten Liste