ALD

Vorteile:

• Dynamische Speicherverwaltung
  • Die Liste kann während der Laufzeit wachsen oder schrumpfen, ohne dass ein fester Speicherblock benötigt wird (anders als bei Arrays).

• Effizientes Einfügen und Löschen

  • Einfügen und Löschen von Knoten an beliebigen Positionen (insbesondere am Anfang) ist effizient, da keine Verschiebung von Elementen nötig ist (nur Zeiger werden angepasst).

  • Aufwand: O(1) am Kopf, O(n) an beliebiger Position (weil man bis dorthin traversieren muss).

• Kein Speicherplatzverschwendung durch feste Größe

  • Nur so viel Speicher wird benötigt, wie tatsächlich für die Knoten gebraucht wird (plus Zeiger)

Nachteile:

• Kein direkter Zugriff (Random Access)

  • Zugriff auf ein Element erfordert das sequentielle Durchlaufen der Liste von vorne. Aufwand: O(n).

• Zusätzlicher Speicherbedarf

  • Jeder Knoten benötigt zusätzlichen Speicher für den Zeiger auf den nächsten Knoten.

• Nur in eine Richtung durchlaufbar

  • Man kann nur von Anfang nach Ende traversieren, Rückwärtslaufen ist nicht möglich (anders als bei doppelt verketteten Listen).

• Komplexere Implementierung

  • Im Vergleich zu Arrays ist das Handling (Einfügen, Löschen, Traversieren) fehleranfälliger wegen der Zeiger.

✅ Vorteile:

• Bidirektionale Traversierung: Man kann sowohl vorwärts als auch rückwärts durch die Liste laufen.

• Einfügen und Löschen effizient: Wenn man den Knoten kennt, lassen sich Elemente an beliebiger Stelle in O(1) einfügen oder entfernen (kein Verschieben wie bei Arrays nötig).

• Flexibler als einfach verkettete Listen: Einfacheres Löschen eines Knotens, da der Vorgänger direkt verlinkt ist (kein explizites Durchlaufen nötig, um den Vorgänger zu finden).

Nützlich für bestimmte Anwendungen: Wird oft in Deques, Stacks, Navigationssystemen (z. B. „Vor“ und „Zurück“ im Browser) oder Speicherverwaltung verwendet.

❌ Nachteile:

• Mehr Speicherbedarf: Jeder Knoten benötigt zusätzlich zum Wert zwei Zeiger (statt nur einem bei einfach verketteten Listen).

• Komplexere Implementierung: Verwaltung von zwei Zeigern (prev & next) erhöht die Fehleranfälligkeit (z. B. Gefahr von Speicherlecks oder „dangling pointers“).

• Schlechtere Cache-Lokalität als Arrays: Da die Elemente nicht zwingend im zusammenhängenden Speicher liegen, sind Zugriffe weniger effizient.

• Zugriff auf Index langsam: Wie bei der einfach verketteten Liste ist ein Zugriff auf das i-te Element nur durch Traversieren in O(n) möglich.

✅ Vorteile:

• Direkter Zugriff in O(1): Zufälliger Zugriff auf jedes Element über den Index ist sehr schnell.

• Gute Cache-Lokalität: Elemente liegen zusammenhängend im Speicher, was Zugriffe effizient macht.

• Einfache Implementierung: Weniger komplex als verkettete Listen.

• Iteration sehr effizient: Da die Elemente nebeneinander im Speicher liegen, sind Schleifen über die Liste schneller als bei verketteten Strukturen.

• Gut für „read-heavy“-Szenarien: Wenn man oft liest und selten einfügt/löscht, ist die ArrayList optimal.

❌ Nachteile:

• Einfügen/Löschen ineffizient:

  • Am Ende meist O(1) (außer bei Vergrößerung des Arrays).

  • Am Anfang oder in der Mitte: O(n), da alle nachfolgenden Elemente verschoben werden müssen.

• Feste Größe + Reallokation: Wenn das Array voll ist, muss ein neues, größeres Array erstellt und der Inhalt kopiert werden (teure Operation).

• Speicherplatzverschwendung: Oft wird mehr Speicher reserviert, als gerade benötigt wird (wegen Wachstumsstrategie).

• Keine bidirektionale Verknüpfung: Kein einfaches Einfügen/Löschen durch nur Umhängen von Zeigern wie bei Listen.

Korrektheit: Erfüllt seine zugrunde liegende Spezifikation. Liefert das – und nur das – korrekte Ergebnis seiner Aufgabenspezifikation 

Vollständigkeit: Nicht (nur) auf die reine Funktionalität bezogen. Essentiell wichtige Vor- und Rahmenbedingungen müssen formuliert werden (zb. Verfügbare/notwendige Datenobjekte) 

Eindeutigkeit: Anweisungen und Abfolge dürfen keinen Interpretationsspielraum erlauben.

 Ausführbarkeit: Klarheit über Ausführung der Anweisungen muss gegeben sein. Ausführbarkeit darf nicht unterbrochen sein

Statische Endlichkeit: Definierter „Umfang“ / „Größe“ der Formulierung muss endlich sein. − (endlich viele Seiten, endlich viel Speicherplatz)

Dynamische Endlichkeit / Unendlichkeit: Ein Algorithmus kann nach endlich vielen Schritten terminieren (und ist damit dynamisch endlich) > Ein Algorithmus kann aber nicht terminierend sein und seine Aufgabe unendlich lange ausführen 

Effizienz:  die Aufgabe unter bestmöglicher Ausnutzung vorhandener Ressourcen zu erfüllen − Laufzeit & Speicherverbrauch

Sortieren, Suchen, Verschlüsseln, Klassifizieren, Optimieren, Komprimieren

• Sind – neben Operatoren (+, -, =, …) - elementare Bestandteile eines Algorithmus −
• Unveränderbare Datenobjekte in Form von Literalen oder Konstanten > Math.Pi, > const int x = 17;
• Veränderbare Datenobjekte (= Variablen)
  • > int x = 17;
  • > Eingeschränkte Wertemenge − Integer, Boolean, Character, … −
• Unveränderbare und veränderbare Datenobjekte werden auch als atomare-, elementare-, einfache- oder unstrukturierte Datenobjekte bezeichnet 
• Algorithmen erreichen schnell Komplexitätsgrad, in denen einfache Datenobjekte nicht mehr ausreichen −
• Erweiterte Möglichkeiten zur Datenmodellierung sind erforderlich, in Form von
  • > strukturierten,
  • > dynamischen und
  • > vernetzten Datenobjekten