Doppelt verkettete Liste, Java?

Am besten bei solche sachen: aufmalen.

Mal einfach mal drei Kästchen hintereinander auf, als ob du drei Zug-Waggons malen würdest.

Jetzt zeigt Waggon Nummer 1 auf Waggon Nummer 2 und umgekehrt. Dazu malst du da zwei Pfeile dran. Das machst du jetzt zwischen zwei und drei ebenfalls.

Wenn du jetzt noch die Pfeile gedanklich durch Referenzen ersetzt, hast du die Hälfte schon.

Beispiel Psudocode:

Waggon {
    Waggon prev; // vorheriger Waggon
    Waggon next; // nächste Waggon

    //...
}

Zug {
    Waggon lok // erster Waggon

    void hintenAnkoppeln(Waggon waggon){
        Zug z = lok;
        while(z.hasNext()){
            z = z.next();
        }
        z.insert(waggon);
    }

    boolean insert(Waggon waggon){...}

    //...
}

In der Methode "insert(Waggon waggon)" muss nun ein Waggon auf die "next"-Referenz gesetzt werden und dessen "prev"-Refernz auf das Objekt, auf dem du insert aufrufst.

Wichtig: immer Skizzen machen!

LinkedLists sind relativ einfach umzusetzen (gibts sogar in Collections):

Zuerst mal brauchst du natürlich eine Klasse (die Liste) mit TypVariable, diese speichert das Element an der Stelle 0 und noch die größe (wahlweise auch das letzte Element).
Dann brauchst du noch eine private interne Klasse welche du zB Container nennst, diese hat auch eine TypVariable und speichert ganz simpel das Objekt, den Container davor und den Container danach.

Einfügen:
An der letzten Position ist das ganz einfach (da ist es nützlich die letzte zu haben), da musst du einfach nur an den letzten Container einen neuen hinzufügen, und musst natürlich den letzten Container ersetzen und die größe erhöhen. Selbes gilt für einfügen an der ersten Posititon.
Mittendrin ist auch nicht so schwierig, du ersetzt einfach die Verweise von den Containern davor und danach durch welche für den neuen Container und passt wieder die größe an.

Entfernen:
Das ist im Prinzip das gleiche wie Einfügen, bloß umgekehrt.

Suchen:
Auch relativ einfach, wenn du eine contains Methode haben willst dann einfach alle Container durchsuchen. Ein Objekt an einer bestimmten Position zu bekommen ist auch nicht gerade schwierig, man muss einfach nur solange den nächsten Container aufrufen bis man an einer bestimmten Position ist.

Falls du noch spezifischere Besipiele brauchst, kannst du ja wie schon gesagt einfach die LinkedList von Java selber anschauen, die ist jedenfalls ziemlich gut gemacht.