EMZETT.LinkedList
Kurz: Eine List-Implementierung aus verketteten Knoten — jeder Knoten kennt nur seinen Vorgänger und Nachfolger, statt in einem zusammenhängenden Speicherblock zu liegen.
Genauer: Einfügen/Entfernen am Anfang oder in der Mitte ist bei einer LinkedList schnell (kein Verschieben nötig), dafür ist der Zugriff per Index langsam, da die Liste von vorn durchlaufen werden muss. LinkedList implementiert zusätzlich Deque, kann also auch als Stack oder Warteschlange genutzt werden.
Im Detail
LinkedList<String> warteschlange = new LinkedList<>();
// Als Warteschlange (FIFO) nutzen - über das Deque-Interface
warteschlange.addLast("Erster");
warteschlange.addLast("Zweiter");
System.out.println(warteschlange.removeFirst()); // "Erster" - kommt zuerst raus
// Als Stack (LIFO) nutzen
LinkedList<Integer> stack = new LinkedList<>();
stack.push(1); stack.push(2); stack.push(3);
System.out.println(stack.pop()); // 3 - zuletzt rein, zuerst raus
// Einfügen am Anfang - O(1) bei LinkedList, O(n) bei ArrayList!
warteschlange.addFirst("Ganz vorn");Der entscheidende Performance-Unterschied zu ArrayList zeigt sich beim Einfügen/Entfernen AM ANFANG oder in der Mitte: eine ArrayList muss dabei alle nachfolgenden Elemente im Speicher verschieben (O(n)), während eine LinkedList nur die Verkettung zwischen den betroffenen Knoten anpasst (O(1), sofern man bereits eine Referenz auf die Einfügestelle hat). Dafür verliert LinkedList beim direkten Indexzugriff (get(i)) deutlich, weil sie sich von einem Ende der Liste bis zur gesuchten Position vorhangeln muss, statt (wie ArrayList) direkt an die berechnete Speicheradresse zu springen. In der Praxis ist ArrayDeque für reine Stack-/Queue-Anwendungsfälle heute meist die bessere Wahl als LinkedList, weil es intern ein Array statt einzelner Knoten nutzt und dadurch cache-freundlicher (und damit in der Praxis oft schneller) ist.