Was ist eine einfach verkettete Liste und wie lässt sie sich implementieren?

Eine Liste ist in Java ein Behälter (Container), der Objekte in einer festen Abfolge enthält. Im Gegensatz zu Arrays, deren Elemente im Speicher in fortlaufender Reihenfolge abgelegt werden und deren Größe aus diesem Grund ohne Neuinitialisierung unveränderbar ist, können Listen flexible Mengen an Objekten enthalten. Diesem nicht unerheblichen Vorteil steht der Nachteil des etwas zeitintensiveren Suchens nach einzelnen Elementen gegenüber, da die Liste zu diesem Zweck jedes Mal erneut durchlaufen werden muss. Listen werden aus diesem Grund hauptsächlich für Zwecke verwendet, bei denen es auf die Arbeit mit dem Anfang oder dem Ende der Liste ankommt.
Eine Liste besteht aus einzelnen Elementen, den Knoten. Bei einer einfach verketteten Liste kennt bis auf das letzte Element jeder Knoten seinen Nachfolger, besitzt somit also eine Referenz auf das nächste Objekt.

Die Klasse ListElement repräsentiert im Beispiel die Knoten. Sie deklariert zwei Instanzvariablen, die auf den Inhalt des Knotens und seinen Nachfolger in der Liste verweisen. Klassen, die Elemente des eigenen Typs enthalten bezeichnet man auch als rekursiv.
Die Klasse EinfachVerketteteListe stellt die eigentliche Listenimplementierung dar.
Die Methode getFirstElem() liefert den Kopf der Liste, die Methode getLastElem() durchläuft die Liste und gibt das letzte Element zurück.
In addLast(Object o) wird das letzte Element über das Durchlaufen der Liste ermittelt und dies mit einem neuen Listenelement so verknüpft, dass dies als Nachfolger des ehemals letzten, nunmehr vorletzten Elementes dient.
Die Methode insertAfter(Object prevItem, Object newItem) fügt ein neues Listenelement an einer vorgegebenen Stelle ein. Hierzu wird als erstes das erste Element hinter dem Kopf in der Variablen pointerElem abgelegt. Die Liste wird anschließend von vorne nach hinten so lange durchlaufen, bis der Einfügepunkt erreicht wird. Er wird über den Inhalt der Elemente ermittelt. Hier liegt ein Haken dieser Listenimplementierung: Der Inhalt eines Listenelementes muss in der Liste einmalig sein. Falls dies nicht der Fall ist, wird als Einfügepunkt das Element mit dem ersten Vorkommen des entsprechenden Inhaltes verwendet. Ist der Einfügepunkt erreicht, wird das Element des gesuchten Vorgängerobjektes mit einem neugebildeten Listenelement als seinem Folgeelement verknüpft. Das neue Element erhält das Folgeelement des ursprünglich gesuchten als Folgeelement.
Um ein Listenelement zu entfernen, wird in der Methode delete(Object o) die Liste wiederum von vorne nach hinten durchlaufen. Wenn das nächste Element dem gesuchten entspricht wird der Durchlauf abgebrochen und es wird geprüft, ob dieses Element wiederum ein Nachfolgeelement besitzt. Ist dies nicht der Fall, so handelt es sich um das letzte Element der Liste und das gesuchte Element kann durch Zuweisung von null einfach gelöscht werden. Existiert ein Nachfolgeelement, muss das aktuelle mit dem übernächsten Element verbunden werden. Ein neues Element wird unter Verwendung des als Methodenparameters übergebenen Objektes gebildet und mit dem Nachfolgeelement wechselseitig verknüpft.
Das Suchen und finden eines Elementes gestaltet sich recht einfach: Die Liste wird einfach so lange durchlaufen, bis das gesuchte Objekt dem Inhalt des aktuellen Elementes entspricht.

public class EinfachVerketteteListe {

    ListElement startElem = new ListElement("Kopf");

    public EinfachVerketteteListe() {}

    public void addLast(Object o){
        ListElement newElem = new ListElement(o);
        ListElement lastElem = getLastElem();
        lastElem.setNextElem(newElem);
    }

    public void insertAfter(Object prevItem, Object newItem) {
        ListElement newElem, nextElem, pointerElem;
        pointerElem = startElem.getNextElem();
        while(pointerElem != null && !pointerElem.getObj().equals(prevItem)){
            pointerElem = pointerElem.getNextElem();
        }
        newElem = new ListElement(newItem);
        nextElem = pointerElem.getNextElem();
        pointerElem.setNextElem(newElem);
        newElem.setNextElem(nextElem);
    }

    public void delete(Object o){
        ListElement le = startElem;
        while (le.getNextElem() != null && !le.getObj().equals(o)){
            if(le.getNextElem().getObj().equals(o)){
                if(le.getNextElem().getNextElem()!=null)
                    le.setNextElem(le.getNextElem().getNextElem());
                else{
                    le.setNextElem(null);
                    break;
                }
            }
            le = le.getNextElem();
        }
    }

    public boolean find(Object o){
        ListElement le = startElem;
        while (le != null){
            if(le.getObj().equals(o))
            return true;
            le = le.nextElem;
        }
        return false;
    }

    public ListElement getFirstElem() {
        return startElem;
    }

    public ListElement getLastElem() {
        ListElement le = startElem;
        while(le.getNextElem() != null){
            le = le.getNextElem();
        }
        return le;
    }

    public void writeList() {
        ListElement le = startElem;
        while(le != null){
            System.out.println(le.getObj());
            le = le.getNextElem();
        }
    }

    public static void main(String[] args) {
        EinfachVerketteteListe list = new EinfachVerketteteListe();
        list.addLast("1");
        list.addLast("2");
        list.addLast("3");
        list.addLast("4");
        list.addLast("5");
        list.insertAfter("2", "neu");
        list.delete("3");
        list.writeList();
        System.out.println("erstes Element: " + list.getFirstElem().getObj());
        System.out.println("ist '3' enthalten? " + list.find("3"));
        System.out.println("ist '5' enthalten? " + list.find("5"));
        System.out.println("letztes Element: " + list.getLastElem().getObj());
    }
}

class ListElement {

    Object obj;

    ListElement nextElem;

    public ListElement(Object obj) {
        this.obj = obj;
        nextElem = null;
    }

    public void setNextElem(ListElement nextElem) {
        this.nextElem = nextElem;
    }

    public ListElement getNextElem() {
        return nextElem;
    }

    public Object getObj() {
        return obj;
    }
}

Wenn Ihnen javabeginners.de gefällt, freue ich mich über eine Spende an diese gemeinnützigen Organisationen.