• Eine LinkedList selbst programmieren - Teil 1

    Eine LinkedList ist eine Liste, deren Elemente als doppelt verkettete Liste gehalten werden d.h. mit Ausnahme des ersten und letzten Elements ist jedes Element mit seinem Vorgänger und Nachfolger verkettet. Dies bedeutet, dass die Elemente in einer LinkedList eine Ordnung aufweisen, also geordnet sind (nicht sortiert!). In Java existiert diese Klasse bereits, welche u.a. die Collection Interfaces List und Queue implementiert. Weiterführende Detail sind unter http://javase/7/docs/api/java/util/LinkedList.html zu finden.

    In diesem Tutorial will ich eine eigene LinkedList programmieren. Dies setzt zwar einerseits gewisse Kenntnisse über die Funktionsweise dieser Collection voraus, andererseits ist ein vertieftes Verständnis das Ziel des vorliegenden Tutorials. Ich werde mich auf die funktionalen Schwerpunkte konzentrieren. Diese sind:


    1. Die Liste verwaltet Objekte eines beliebigen Typs
    2. Die Liste verfügt über eine Methode add(), welche die Elemente doppelt verkettet speichert.
    3. Die Methode get(index) liefert das Objekt an der Position index zurück.
    4. Die Methode indexOf(Objekt) liefert den Index des ersten Vorkommens ins der Liste.
    5. Die Methode remove(index) schliesst das Objekt an der Position index aus der Liste aus.
    6. DieMethode size() liefert die Anzahl Elemente in der Liste.
    7. Mit getFirst() liefert die Liste das erste Element und mit getLast() das letzte Element.
    8. Die Liste verfügt über eine Methode printLinkedList zur Ausgabe aller Elemente.


    Damit hat man schon einen Basissatz von Methoden, die sich zur umfangreichen LinkedList weiter ausbauen lassen oder verschachteln lassen. Beispielsweise lässt sich eine neue Methode removeLast() oder removeFirst() mit der Kombination aus 4. und 5. umsetzen. Dazu später mehr.

    Der Focus dieses Tuturials liegt in der funktionalen Umsetzung obiger Anforderungen und nicht auf die programmtechnische Umsetzung in Java. Kenntnisse von Java Generics werden vorausgesetzt. Konstruktive Verbesserungen werden gerne angenommen.

    Es sei kurz erwähnt, dass eine verkettete Liste eine Referenz first auf das erste Element sowie eine Referenz last auf das letzte Element haben sollte. Über diese zwei Instanzvariablen lässt sich schnell und einfach den Anfang resp. das Ende der Liste ermitteln. Damit lässt sich auch die Anforderung 7. realisieren, indem triviale Getters zu diesen zwei Instanzvariablen implementiert werden. Zudem ist eine Instanzvariable size ebenfalls sinnvoll, mit der sich schnell ermittlen lässt, ob die Liste leer ist resp. wieviele Element sie enthält.

    Da es sich hier um eine verkettete Liste handelt, müssen die Elemente auf das vorhergehende bzw. nachfolgende Element bezogen auf ihre eigene Position referenzieren. Zudem muss gemäss 1. ein Element ein beliebiger Datentyp speichern können. Hierzu bietet es sich an, eine generische Klasse mit dem Namen Node zu erzeugen. Die Klasse besitzt einen Konstruktor, welches das gemerische Item selbst, sowie das vorhergehende sowie das nachfolgende Element annehmen kann. Hier der Code:

    Code java:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    
    public class Node<T> {
        protected T item;
        protected Node<T> next;
        protected Node<T> prev;
     
        public Node(T item, Node<T> p, Node<T> n) {
            this.item = item;
            this.prev = p;
            this.next = n;
        }
     
        public T getItem() {
            return this.item;
        }
     
        @Override
        public boolean equals(Object o) {
            if (o instanceof Node && ((Node) o).next == this.next
                    && ((Node) o).prev == this.prev
                    && ((Node) o).getItem() == this.getItem()) {
                return true;
            } else {
                return false;
            }
        }
    }

    Mit obiger Klasse lassen sich bereits Knoten instanzieren. Um eine verkettete Liste solcher Knoten zu verwalten benötigen wird eine neue Klasse, die wir MyLinkedList nennen wollen. Diese Klasse ist wiederum generisch, da der Typ der Knoten über diese Klasse festgelegt wird. Die Definition der Klasse mit ihren Instanzvariablen sieht wie folgt aus:

    Code java:
    1
    2
    3
    4
    5
    
    public class MyLinkedList<T> {
        private Node<T> first;
        private Node<T> last;
        private Node<T> current;
        private int size;

    Die Instanzvariablen first und last sind vom Typ Node<T>. Zudem gibt es eine Instanzvariable current, die für interne Operationen gebraucht wird und die Instanzvariable size, welche bei add() oder remove() verändert wird. Mit diesen zwei Klassen sind die grundlegenden Datenstrukturen geschaffen, damit die Elemente verkettet und generisch verwaltet werden können. Nun soll die Klasse auch Methoden add() anbieten, die das Element jeweils am Ende der Liste einfügt. Eine Implementierung könnte wie folgt aussehen:

    Code java:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    
        public void add(T e) {
            if (size == 0) {
                current = new Node<T>(e, null, null);
                first = current;
                last = current;
                size = 1;
            } else {
                Node<T> node = new Node<T>(e, null, null);
                last = node;
                last.prev = current;
                current.next = node;
                current = last;
                size++;
            }
        }

    Falls die Liste noch leer ist, kann ein Knoten ohne Vorgänger und Nachfolger erzeugt werden und size wird auf 1 gesetzt. Sind hingegen bereits Knoten vorhanden, so wird last auf den neuen Knoten gesetzt. Da current noch auf den vorletzten Knoten zeigt, muss last.prev auf current und current.next auf den neuen Knoten referenzieren. Zudem wird size und eins erhöht. Der Code mag verwirrend erscheinen, wenn man sich jedoch die Referenzen bildlich vorstellt, ist ein add() keine Hexerei mehr. Nun ist die Klasse MyLinkedList in der Lage, Elemente eines beliebigen Typs aufzunehmen.

    Bevor wir innerhalb von main() einige Testfälle schreiben, wollen wir diese Klasse mit einer Methode printLinkedList() erweitern, welche die Elemente sequentiell ausgibt. Diese Methode besteht im Wesentlichen aus einer for-each-Schleife:

    Code java:
    1
    2
    3
    4
    5
    6
    
    public void printLinkedList() {
            for (Node<T> n = first; n != null; n = n.next) {
                System.out.print(n.getItem() + " ");
            }
            System.out.println();
        }

    Da mit add() auch die Instanzvariable size verändert wird, können wir für diese Instanzvariable eine entsprechende Getter-Methode schreiben. Dasselbe gilt für getFirst und getLast, wobei hier zuerst geprüft werden muss, ob die Instanzvariablen auch schon gesetzt worden sind, damit man keine NullPointerException auslöst:

    Code java:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    
        public T getFirst() {
            if (this.first != null) {
                return (T) this.first.getItem();
            } else {
                return null;
            }
        }
     
        public T getLast() {
            if (this.last != null) {
                return (T) this.last.getItem();
            } else {
                return null;
            }
        }
        
        public int size() {
            return this.size;
        }

    Nun zum Testfall: innerhalb von main() wird eine Instanz der Klasse MyLinkedList für Elemente des Typs Integer erzeugt um sodann mit einer for-Schleife 10 Elemente hinzuzufügen.

    Code java:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    
    public static void main(String[] args) {
            MyLinkedList<Integer> mll = new MyLinkedList<Integer>();
     
            System.out.println("Anzahl Elemente in MyLinkedList: " + mll.size());
            for (int i = 0; i < 10; i++) {
                mll.add(i);
            }
            System.out.println("Anzahl Elemente in MyLinkedList: " + mll.size());
            System.out.print("Die Elemente sind: ");
            mll.printLinkedList();
        }

    In meiner Umgebung wird folgender Output erzeugt

    Anzahl Elemente in MyLinkedList: 0
    Anzahl Elemente in MyLinkedList: 10
    Die Elemente sind: 0 1 2 3 4 5 6 7 8 9
    Dass unsere Liste tatsächlich generisch arbeitet, kann leicht überprüft werden, indem man eine neue Liste mit dem Elementyp String erzeugt. Selbstverständlich muss in der add() Methode ein Typ String übergeben werden, was mit String.valueOf(i) bewerkstelligen lässt. Sofern sie eigene Objekttypen hinzufügen, sollte die Methode toString() überschrieben werden, damit in printLinkedList eine sinnvolle Repräsentation des Objektes ausgegeben werden kann.

    Damit sind die Anforderungen 1., 2., 6. und 7. fertig implementiert. Die übrigen Methoden werde ich bei Interesse später nachliefern. Viel Spass mit dem Code.
    Jay bedankt sich.