# Portabilitaet: UNIVERSAL
# Zuletzt validiert: 2026-01-28 (Gemini)
# Naechste Pruefung: 2027-01-28
# Quellen: [informatik/datenstrukturen/README.txt]

ARRAYS UND LISTEN
=================

Stand: 2026-01-28

DAS FUNDAMENT ALLER DATENSTRUKTUREN
-----------------------------------
Nahezu jede komplexere Struktur basiert entweder auf Arrays (contiguous memory) oder Linked Lists (pointer-based memory).

ARRAYS (FELDER)
---------------
Ein Array ist ein fixer, zusammenhaengender Speicherblock.
- **Zugriff:** O(1) - Sofort via Index (`arr[5]`). Prozessor-freundlich (Cache Locality).
- **Suche:** O(n) linear, O(log n) wenn sortiert (Binary Search).
- **Einfuegen:** O(n) - Schlecht! Alles dahinter muss verschoben werden.
- **Groesse:** Statisch. Wenn voll, muss ein ganz neues, groesseres Array erstellt und alles kopiert werden (Dynamic Array / ArrayList).

LINKED LISTS (VERKETTETE LISTEN)
--------------------------------
Elemente (Nodes) sind im Speicher verstreut. Jedes Element kennt seinen Nachfolger (`next`).
- **Zugriff:** O(n) - Schlecht! Man muss von Anfang an "durchklicken".
- **Suche:** O(n).
- **Einfuegen:** O(1) - Genial! Nur Pointer umbiegen (wenn man die Position hat).
- **Groesse:** Völlig dynamisch. Waechst elementweise.

VARIANTEN VON LISTEN
--------------------
- **Singly Linked:** Nur `next` Pointer. Vorwaerts-Iteration.
- **Doubly Linked:** `next` und `prev` Pointer. Vor- und Zurueck. Mehr Speicherbedarf.
- **Circular:** Der Letzte zeigt auf den Ersten.

PYTHON IMPLEMENTIERUNG
----------------------
In Python ist die Standard-`list` (`[]`) technisch ein **Dynamic Array**, keine Linked List!
- Zugriff ist O(1).
- Append am Ende ist O(1) (amortisiert).
- Insert am Anfang ist O(n).

Wer eine echte Linked List / Queue in Python braucht, nutzt `collections.deque` (Doubly Linked List).

WANN WAS NEHMEN?
----------------
- **Array:** Wenn du oft auf Elemente via Index zugreifen musst oder die Datenmenge stabil ist.
- **List:** Wenn du sehr oft Elemente in der Mitte/am Anfang einfuegen oder loeschen musst.

SIEHE AUCH
----------
wiki/informatik/algorithmen/komplexitaet.txt
wiki/python/datentypen/
