Einfügen in einer Linked List vs Double Linked List: Linked List:

• Um ein Element am Anfang einzufügen, erstellen wir einfach einen neuen Knoten, setzen seinen next Zeiger auf den aktuellen Kopf der Liste und aktualisieren dann den Kopf der Liste auf den neuen Knoten.
• Um ein Element am Ende einzufügen, müssen wir die gesamte Liste durchlaufen, um den letzten Knoten zu finden, und dann den nextZeiger des letzten Knotens auf den neuen Knoten setzen.
• Das Einfügen in der Mitte erfordert auch das Durchlaufen der Liste bis zur gewünschten Position.

Double Linked List:

• Das Einfügen am Anfang oder am Ende ist ähnlich wie bei der Linked List, aber wir müssen auch den prev Zeiger des neuen Knotens bzw. des nachfolgenden Knotens aktualisieren.
• Das Einfügen in der Mitte ist etwas einfacher, da wir nicht die vorherige Position finden müssen (wie bei der Linked List), da jeder Knoten einen Zeiger auf den vorherigen Knoten hat.

Löschen in einer Linked List vs Double Linked List: Linked List:

• Um ein Element zu löschen, müssen wir die Liste durchlaufen, um den vorherigen Knoten des zu löschenden Knotens zu finden, und dann den nextZeiger des vorherigen Knotens auf den Knoten nach dem zu löschenden Knoten setzen.
• Wenn der zu löschende Knoten der Kopf der Liste ist, setzen wir einfach den Kopf auf den nächsten Knoten.

Double Linked List:

• Um ein Element zu löschen, setzen wir einfach den nextZeiger des vorherigen Knotens auf den Knoten nach dem zu löschenden Knoten und den prevZeiger des nachfolgenden Knotens auf den Knoten vor dem zu löschenden Knoten.
• Wenn der zu löschende Knoten der Kopf oder der Schwanz der Liste ist, aktualisieren wir einfach den Kopf oder den Schwanz auf den nächsten oder vorherigen Knoten.
• Es ist nicht notwendig, die Liste zu durchlaufen, um den vorherigen Knoten zu finden, da jeder Knoten einen Zeiger auf den vorherigen Knoten hat.

Comparable

• Dieses Interface wird in der Klasse des Objekts implementiert, das wir vergleichen möchten.
• Es hat eine Methode namens compareTo(T obj), die verwendet wird, um das aktuelle Objekt mit einem anderen zu vergleichen.

public class Student implements Comparable<Student> {
    private String name;

    // constructor, getters and setters

    @Override
    public int compareTo(Student other) {
        return this.name.compareTo(other.getName());
    }
}

Comparator

• Dieses Interface wird verwendet, wenn Sie eine andere Ordnung als die natürliche Ordnung definieren möchten, oder wenn Sie Objekte einer Klasse sortieren möchten, die das Comparable-Interface nicht implementiert.
• Es hat eine Methode namens compare(T obj1, T obj2), die verwendet wird, um zwei Objekte zu vergleichen.

public class StudentAgeComparator implements Comparator<Student> {
    @Override
    public int compare(Student s1, Student s2) {
        return s1.getAge() - s2.getAge();
    }
}

Zeitkomplexität:

• Wenn Ihr Algorithmus eine feste Anzahl von Operationen ausführt, unabhängig von der Größe der Eingabe, hat er eine Zeitkomplexität von O(1), auch bekannt als konstante Zeit.
• Wenn Ihr Algorithmus jedes Element in den Eingabedaten einmal verarbeitet, hat er eine Zeitkomplexität von O(n), auch bekannt als lineare Zeit.
• Wenn Ihr Algorithmus eine Schleife innerhalb einer Schleife (oder mehrere Schleifen) hat, die jeweils über die Eingabedaten iterieren, hat er eine Zeitkomplexität von O(n^2), auch bekannt als quadratische Zeit. Dies ist häufig in Algorithmen wie Bubble Sort oder Insertion Sort.
• Wenn Ihr Algorithmus die Eingabedaten bei jedem Schritt halbiert (oder einen konstanten Bruchteil), hat er eine Zeitkomplexität von O(log n), auch bekannt als logarithmische Zeit. Dies ist häufig in Algorithmen wie Binary Search.
• Wenn Ihr Algorithmus die Eingabedaten bei jedem Schritt halbiert (oder einen konstanten Bruchteil) und auch alle Daten verarbeitet, hat er eine Zeitkomplexität von O(n log n). Dies ist häufig in Algorithmen wie Quicksort oder Mergesort.

HashSet vs. TreeSet

1. Interne Datenstruktur: ****HashSet verwendet eine Hash-Tabelle als interne Datenstruktur, während TreeSet einen Baum (genauer gesagt, einen Rot-Schwarz-Baum) verwendet.
2. Sortierung der Elemente: In einem HashSet sind die Elemente nicht sortiert, während in einem TreeSet die Elemente natürlich sortiert sind (basierend auf ihrem natürlichen Vergleichsverfahren, d.h. sie müssen das Comparable-Interface implementieren) oder durch einen benutzerdefinierten Comparator, der bei der Erstellung des TreeSets bereitgestellt wird.
3. Performance: Operationen wie Hinzufügen, Entfernen und Überprüfen, ob ein Element vorhanden ist, haben in einem HashSet eine konstante Zeitkomplexität von O(1). In einem TreeSet haben diese Operationen eine logarithmische Zeitkomplexität von O(log(n)) aufgrund der Baumstruktur.
4. Null-Elemente: HashSet erlaubt ein Null-Element, während TreeSet dies nicht erlaubt, wenn ein natürlicher Vergleich oder ein benutzerdefinierter Comparator verwendet wird.

Topologische Sortierung

1. Wähle Knoten ohne Vorgänger aus Graph
2. Lösche diesen Knoten aus dem Graph
3. Wiederholen, bis kein Knoten im Graphen mehr vorhanden ist

Traveling Salesman

• Eine Heuristik im Zusammenhang mit dem Traveling-Salesman-Problem (TSP) ist eine Technik, mit der das Problem schneller als mit klassischen Methoden gelöst werden kann, indem eine Annäherung an die optimale Lösung erfolgt.
• Heuristiken garantieren nicht die beste Lösung, aber sie liefern eine gute Lösung in einer angemessenen Zeit.
• Eine gängige Heuristik für das TSP ist die "Nearest Neighbor"-Heuristik, bei der man bei einer zufälligen Stadt beginnt und wiederholt die nächstgelegene Stadt besucht, bis alle Städte besucht wurden.
• Dies führt zwar nicht immer zur besten Route, aber es ist schnell und in der Regel gut genug.

Backtracking

• Depth-First Search
• Backtracking liefert immer die perfekte/beste Lösung eines Problems.
• Backtracking ist im Prinzip systematisches Probieren aller Möglichkeiten ("Brute Force").
• Nachteil des Backtrackings ist seine Laufzeit.
• Da im schlimmsten Fall alle Möglichkeiten durchprobiert werden müssen, steigt die Laufzeit mit der Anzahl der Knoten/Kanten exponentiell.

Bounding-Funktion

• Eine Bounding-Funktion in einem Backtracking-Algorithmus ist eine Funktion, die verwendet wird, um zu bestimmen, ob eine teilweise Lösung das Potenzial hat, zu einer vollständigen Lösung zu führen.
• Wenn die Bounding-Funktion feststellt, dass eine teilweise Lösung nicht zu einer vollständigen Lösung führen kann, wird diese teilweise Lösung verworfen und der Algorithmus geht einen Schritt zurück, um eine andere Möglichkeit zu erkunden.
• Im Kontext des Rucksackproblems könnte eine Bounding-Funktion beispielsweise das aktuelle Gesamtgewicht der ausgewählten Gegenstände mit dem Gewichtslimit des Rucksacks vergleichen.
• Wenn das aktuelle Gesamtgewicht das Gewichtslimit überschreitet, würde die Bounding-Funktion feststellen, dass diese Auswahl von Gegenständen nicht zu einer gültigen Lösung führen kann, und der Backtracking-Algorithmus würde diese Auswahl verwerfen und eine andere Möglichkeit erkunden.

Branch and Bound

• Breadth-First-Search