Da das wahrscheinlich 30-40 % meiner bevorstehenden Prüfung ausmacht und ich mich bestmöglich darauf vorbereiten will (da vermutlich etwas unerwartetes drankommt) wollte ich ein paar typische Möglichkeiten, was man mit verketteten Listen alles machen kann.
Was ich kann:
- Ein Element in einem Knoten einfügen
- Das Element wieder entfernen
- Die Häufigkeit eines Elements auslesen
- z.B. alle Zahlen kleiner 0 aus dem Knoten entfernen
- Die Listen um n Stellen nach links rotieren lassen
Außerdem weiß ich wie man einen Binärbaum aufbaut.
Was ich kann:
- Ein Element in einem Knoten einfügen
Java:
public class NumberList {
NumberNode head; // 1. Listenelement = Kopf der Liste
public void add(int value) {
NumberNode q = new NumberNode(value); // neuer Knoten, mit aktuellem Wert
NumberNode p = head; // Hilfsknoten zum Iterieren
NumberNode prev = null;
while (p != null && p.value < value) { // korrekte Position zum Einfügen finden
prev = p; // "Einhängen" des neuen Knotens
p = p.next;
}
q.next = p;
if (p == head) { // neuer Knoten ganz vorne eingefügt? 'head' ist zu ändern!
head = q;
} else {
prev.next = q;
}
}
- Die Häufigkeit eines Elements auslesen
- z.B. alle Zahlen kleiner 0 aus dem Knoten entfernen
- Die Listen um n Stellen nach links rotieren lassen
Außerdem weiß ich wie man einen Binärbaum aufbaut.