ALD

✅ 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 

1. Zeit und Arbeitsspeicher messen, bei gleichen Eingabewerten

• Probleme:
  • abhängig von Leistung des Computers
  • abhängig was Computer sonst so macht
  • abhängig von Programmiersprache und Implementierung
  • Algorithmen müssen bereits implementiert sein!

2. Zählen und gewichten der Rechenschritte (Feinanalyse)

• Problem: hoher Aufwand 

3. Grobes Zählen der Rechenschritte (Grobanalyse)

• Aufwand geringer als bei Feinanalyse
• nur den am schnellsten wachsenden Term berücksichtigen
  • (=> ergibt Komplexitätsklasse)

• Iteration
  • Einzelne Anweisungen werden wiederholt ausgeführt
  • Einsatz von Schleifen −
• Rekursion
  • Methode ruft sich selbst rekursiv (wiederholend) auf
  • Abbruchbedingung muss gegeben sein
    • − Viele Problemlösungen verleiten zum rekursiven Ansatz
    • − Rekursiver Ansatz jedoch in den meisten Fällen nicht optimal, weil
    •  Abbruchkriterium muss sichergestellt sein Speicherverbrauch / Stack Overflow

Graphen sind (mathematische) Modelle für netzartige Strukturen

• Verkehrsnetze
• Computernetze
• elektr. Schaltungen