Verkettete Liste
(nicht vollständig)
Eine verkettete Liste ist eine Datenstruktur in der Informatik, die aus einer Reihe von Elementen besteht, die als "Knoten" bezeichnet werden. Jeder Knoten enthält sowohl die eigentlichen Daten als auch eine Referenz oder einen Zeiger auf das nächste Element in der Liste. Diese Verknüpfung ermöglicht es, die Elemente in einer nicht zusammenhängenden Weise im Speicher zu speichern.
Es gibt verschiedene Arten von verketteten Listen, darunter:
- Einfach verkettete Liste: Jeder Knoten verweist nur auf das nächste Element in der Liste.
- Doppelt verkettete Liste: Jeder Knoten verweist sowohl auf das vorherige als auch auf das nächste Element in der Liste.
- Dies ermöglicht eine bidirektionale Traversierung der Liste.
- Kreisförmige verkettete Liste: Die letzte Elementreferenz verweist auf das erste Element, wodurch eine geschlossene Schleife entsteht.
Verkettete Listen bieten mehrere Vorteile, darunter:
- Einfügen und Löschen von Elementen: Das Einfügen oder Löschen eines Elements in einer verketteten Liste erfordert nur die Aktualisierung der betreffenden Zeiger, im Vergleich zu Arrays, bei denen Verschiebungen erforderlich sein können.
- Dynamische Größe: Verkettete Listen ermöglichen das Hinzufügen oder Entfernen von Elementen während der Laufzeit, ohne im Voraus den Speicher zu reservieren.
- Geringer Speicherplatzbedarf: Verkettete Listen können Speicherplatz effizienter nutzen, da sie nicht notwendigerweise zusammenhängend im Speicher liegen müssen.
Allerdings haben verkettete Listen auch einige Nachteile, wie einen leicht höheren Overhead aufgrund der zusätzlichen Zeiger und den Zugriff auf Elemente, der im Durchschnitt langsamer sein kann als bei Arrays, da keine direkte Indexierung möglich ist. Die Wahl zwischen Arrays und verketteten Listen hängt von den spezifischen Anforderungen und Einsatzszenarien ab.
Prinzip der verketteten Liste. 
Einfügen am Beginn einer verketteten Liste. 
Einfügen am Ende einer verketteten Liste. 
Löschen am Ende einer verketteten Liste. 
Wir können demnach folgende Operationen festlegen:
- void addFirst(Object obj) fügt das Objekt obj als erstes Element in die Liste ein.
- Object getFirst() liefert das erste Element der Liste.
- Object removeFirst() entfernt das erste Element der Liste und gibt es gleichzeitig als Ergebnis zurück.
- void addLast(Object obj) hängt das Objekt obj als letztes Element an die Liste an.
- Object getLast() liefert das letzte Element der Liste.
- Object removeLast() entfernt das letzte Element der Liste und gibt es gleichzeitig als Ergebnis zurück.
Knoten
public class Node {
Object element; // Element
Node next; // Verweis auf Nachfolger
public Node() {
element = null;
next = null;
}
// Konstruktoren element = o;
public Node(Object o, Node n) {
element = o;
next = n;
}
public void setElement(Object o) {
element = o;
}
// Element neu belegen
public Object getElement() { // Zugriff auf Element
return element;
}
public void setNext(Node n) {
next = n;
}
public Node getNext() { // Zugriff auf Nachfolger
return next;
}
}
Verkettete Liste
public class MyList {
private Node head = null;
public MyList() {
head = new Node();
}
public void addFirst(Object obj) {
Node n = new Node(obj, head.getNext());
head.setNext(n);
}
public Object getFirst() {
if (isEmpty()) {
System.out.println("Die Liste ist leer");
return null;
} else {
return TODO;
}
}
public Object removeFirst() {
if (isEmpty()) {
System.out.println("Die Liste ist leer");
return null;
} else {
Object o = head.getNext().getElement();
head.setNext( TODO );
return o;
}
}
public void addLast(Object obj) {
Node last = head;
while (last.getNext() != null) {
last = last.getNext();
}
Node ne = new Node(obj, null);
last.setNext(ne);
}
public Object getLast() {
if (isEmpty()) {
System.out.println("Die Liste ist leer");
return null;
} else {
Node l = head;
while (l.getNext() != null) {
// TODO
}
return l.getElement();
}
}
public Object removeLast() {
if (isEmpty()) {
System.out.println("Die Liste ist leer");
return null;
} else {
Node l = head;
while (l.getNext().getNext() != null) {
// TODO
}
Object o = l.getNext().getElement();
l.setNext(null);
return o;
}
}
public boolean isEmpty() {
return TODO
}
public void size() {
int s = 0;
Node n = head;
while (n.getNext() != null) {
s++;
n = n.getNext();
}
System.out.println("Size : " + s);
}
}
Test
MyList list = new MyList();
list.addFirst("eins");
System.out.println((String)list.getFirst()); // eins
list.addFirst("zwei");
System.out.println((String)list.getLast()); // eins
System.out.println((String)list.getFirst()); // zwei
list.removeFirst();
System.out.println((String)list.getFirst()); // eins
list.addLast("drei");
System.out.println((String)list.getLast()); // drei
list.removeLast();
System.out.println((String)list.getLast()); // eins