Die Datenstruktur List

13 Jan 2018 • Datenstrukturen • Beiträge

Anstatt beispielsweise einer Queue, bei der wir ein head und ein tail Element haben, über die wir auf den Anfang und das Ende der Queue zugreifen können, haben wir nun die List mit 3 möglichen “Eingriffspunkten”.

Wie bei der Queue haben wir auch ein Element am Anfang (first) und am Ende (last). Zusätlich zu diesen beiden gibt es noch das current Element, dass über die List bewegt werden kann. Wir haben damit die Möglichkeit bekommen, dass wir auf alle Elemente in einer Datenstruktur zugreifen können, ohne eines der anderen Element entfernen zu müssen!

Beispiel List

Methoden

Im folgenden werden die wichtigsten Methode aus der Klasse List erläutert.

hasAccess()

Die Methode liefert einen boolean Wert zurück, der angibt, ob das aktuelle Element auf ein Element zugreift.

public boolean hasAccess() {
    return current != null;
}

toFirst() und toLast()

toFirst() setzt das aktuelle Element auf das erste Element. Im Gegensatz dazu setzt toLast() das aktuelle Element auf das letzte Element.

public void toFirst() {
    if (!isEmpty()) current = first;
}

public void toLast() {
    if (!isEmpty()) current = last;
}

setContent() und getContent()

In dem Fall, dass es ein aktuelles Element gibt, kann mit den Methoden setContent() und getContent() der Inhalt des aktuellen Elementes bearbeitet/abgerufen werden.

public ContentType getContent() {
    if (hasAccess()) return current.getContent();
    else return null;
}

public void setContent(ContentType pContent) {
    if (hasAccess() && pContent != null) current.content = pContent;
}

append()

Mit der append() Methode lassen sich Elemente hinten an die Liste anhängen. Dabei ist zu unterscheiden, ob die Liste leer ist, oder schon Elemente behinhaltet. Ist sie leer, so muss sowohl first als auch last auf das neue Element zeigen. In allen anderen Fällen wird mit der setNext() Methode aus der internen Klasse Node bestimmt, dass der Nachfolger des letzten Elementes das neu einzufügende Element ist. Anschließend muss dann noch last auf das letzte Element gesetzt werden.

public void append(ContentType pContent) {
    if (pContent != null) {
        Node temp = new Node(pContent);

        if (isEmpty()) {
            first = temp;
            last = temp;
        } else {
            last.setNext(temp);
            last = temp;
        }
    }
}

insert()

Die Methode insert() fügt ein neues Element vor dem aktuellen Element ein. Dabei muss beachtet werden, dass es ein aktuelles Element geben muss, damit die Methode funnktioniert. In dem Fall, dass die List leer ist und es damit kein aktuelles Element geben kann, wird das neue Element zwar eingefügt, current zeigt aber weiterhin auf kein Element.

Bei dieser Methode wird deutlich, dass man immer überprüfen muss, dass man alle möglichen Sonderfälle berücksichtigt hat. Folgenden Fälle könne häufig auftreten:

  1. Die Liste ist leer.
  2. Das neue Element wird am Anfang eingefügt.
  3. Das neue Element wird am Ende eingefügt.
  4. Das neue Element wird an einer anderen Stelle eingefügt.

Bei der beschriebenen Methode sind vor allem die Fälle 1, 2 und natürlich 4 wichtig. Insbesondere der Fall 2 ist von Beudeutung, da das neue Element immer vor dem aktuellen Element eingefügt wird, und wir vor dem ersten Element in der List kein Element haben.

Um das vorherige Element erst einmal zu finden, verwenden wir eine getPrevious() Methode

    
private Node getPrevious(Node pNode) {
    if (hasAccess() && !isEmpty() && current  != first) {
        Node pointer = first;

        while (pointer != null && pointer.getNext() != pNode) {
            pointer = pointer.getNext();
        }

        return pointer;
    } else return null;
}

Die oben abgebildete Methode liefert immer das Element, dass vor dem current Element steht zurück, es sei denn es gibt kann Element davor. Das kann beispielsweise dann passieren, wenn current auf das erste Element zeigt. In diesem Fall würde null zurückgegeben werden.

Mit der Methode getPrevious() kann nun bestimmt werden zwischen welchen beiden Elementen das neue Element in der insert() Methode eingefügt werden soll: Zwischen getPrevious() und current.

public void insert(ContentType pContent) {
    if (pContent == null) return;

    if (isEmpty()) append(pContent);
    else if (hasAccess()) {
        Node previousNode = getPrevious(current);
        Node newNode = new Node(pContent);

        if (previousNode != null) {
            newNode.setNext(current);
            previousNode.setNext(newNode);

        } else if (current == first) { //newNode muss am Anfang eingefügt werden
            newNode.setNext(first);
            first = newNode;
        }
    }
}

concat()

Die Methode concat() fügt zwei Listen zusammen. Dabei wird der Methode eine Liste übergeben, die dann an die aktuelle Liste (this) angehängt wird. Dabei muss wieder zwischen zwei Fällen unterschieden werden. Zum einen kann die aktuelle Liste leer sein, dann werden first und last der aktuellen Liste mit dem first und last der übergebenen Liste überschrieben. Andernfalls zeigt das last Element der aktuellen Liste auf das erste Element der übergebenen Liste last wird mit dem last der übergebenen List überschrieben.

Da die übergebene Liste, die angehängt werden soll, leer sein soll, werden noch alle Möglichkeiten auf Liste zuzugreifen auf null gesetzt.

public void concat(List<ContentType> pList) {
    if (pList != null && pList != null && !pList.isEmpty()) {
        if (this.isEmpty()){
            first = pList.first;
            this.last = pList.last;
        }else{
            last.setNext(pList.first);
            last = pList.last;
        } 

        pList.first = null;
        pList.last = null;
        pList.current = null;

    }
}

remove()

remove() löscht das aktuelle Element und setzt current auf das nächste Element. Dabei wird auch hier der Vorgang in Fälle zerlegt, da es je nach Fall vorkommen kann, dass vor dem aktuellen Element in der Liste kein weiteres Element gibt, beziehungsweise nach dem aktuellen Element kein Element mehr vorhanden ist. Nachdem dann auch das aktuelle Element verschoben wurde, wird nocheinmal überprüft, ob die Liste leer ist, da in diese Fall last noch auf ein Element zeigen würde, first aber auf null.

public void remove() {
    if (hasAccess() && !isEmpty()) {
        if (current == first) {
            first = first.getNext();
        }
        else if (current == last) {
            Node previousNode = getPrevious(current);

            last = previousNode;
            previousNode.setNext(null);
        }
        else {
            Node previousNode = getPrevious(current);
            previousNode.setNext(current.getNext());
        }

        Node newNext = current.getNext();
        current = newNext;

        if (isEmpty()) last = null;
    }
}

List Sort

Das Sortieren mit Listen gestaltet sich als besonders einfach, da die Implementierung der verschiedenen Verfahren sich als relativ unkompliziert darstellt.

Quicksort

public List<Integer> quicksort(List<Integer> pList) {
    
    
    pList.toFirst();
    int pivot = pList.getContent();
    pList.next();

    List<Integer> greaterThan = new List<Integer>();
    List<Integer> lessEqualThan = new List<Integer>();

    while (pList.hasAccess()) {
        if (pList.getContent() > pivot) greaterThan.append(pList.getContent());
        else lessEqualThan.append(pList.getContent());

        pList.remove();
    }

    if (!greaterThan.isEmpty()) greaterThan = quicksort(greaterThan);
    if (!lessEqualThan.isEmpty()) lessEqualThan = quicksort(lessEqualThan);

    lessEqualThan.concat(pList);
    lessEqualThan.concat(greaterThan);


    return lessEqualThan;

}

In der Implementierung des Verfahrens wird das erste Element in der Liste als Pivot Element genommen. Anhand diesem Elementes wird dann jedes Element in eine der zwei gegebenen Listen einsortiert. Für diese Listen wird dann jeweils die Methode rekursiv aufgerufen. Anschließend werden die Listen mit der concat() Methode wieder zusammengefügt.

Mergesort

public List<Integer> mergesort(List<Integer> pList) {
    int size = getListSize(pList);

    if (size < 2) return pList;

    List<Integer> pList2 = new List<Integer>();
    pList.toFirst();

    for (int i = 0; i < (size / 2); i++) {
        pList2.append(pList.getContent());
        pList.remove();
    }

    pList = mergesort(pList);
    pList2 = mergesort(pList2);


    return merge(pList, pList2);
}

private int getListSize(List<Integer> pList) {
    int size = 0;
    pList.toFirst();

    while (pList.hasAccess()) {
        size++;
        pList.next();
    }

    return size;
}

private List<Integer> merge(List<Integer> pList1, List<Integer> pList2) {
    List<Integer> pList = new List<Integer>();

    pList1.toFirst();
    pList2.toFirst();

    while (pList1.hasAccess() && pList2.hasAccess()) {

        if (pList1.getContent() <= pList2.getContent()) {
            pList.append(pList1.getContent());
            pList1.remove();
        } else {
            pList.append(pList2.getContent());
            pList2.remove();
        }
    }

    if (pList1.isEmpty()) pList.concat(pList2);
    else if (pList2.isEmpty()) pList.concat(pList1);

    return pList;
}

Für Mergesort wird noch eine Methode getListSize() benötigt, da man immer die Liste in der Mitte teilt um sie dann wieder sortiert zusammenzufügen. Mit current ist es zudem immer einfach den Pointer beim mergen darzustellen.

SortedList

Eine Erweiterung des List ist die SortedList. Sie fügt jeden Wert automatisch sortiert in die List ein. Dafür wird folgenden Struktur verwendet:

Architektur des SortedList

Diagramm SortedListQuelle: Moodle

Zur Realisierung wird ein Interface verwendet. Dieses definiert Methoden, die dann von der Klasse implementiert werden, die das Interface implementiert. In obigen Bid wäre es die Klasse Item, die das Interface Sortable implementiert.

Der ContentType der SortedList muss von dem Interface Sortable erben, da wir damit auf die Methode compareTo() zugreifen können, wenn wir als Datentyp den ContentType angeben.

Interface Sortable

public interface Sortable<ContentType> {
  public int compareTo(ContentType pContent);

  public String getID();
}

Klasse Item

public class Item implements Sortable<Item> {
  private String iD;

  public Item(String pID) {
    this.iD = pID;
  }

  public String getID() {
    return iD;
  }

  @Override
  public int compareTo(Item pItem) {
    return iD.compareTo(pItem.getID());
  }

  @Override
  public String toString() {
    return iD;
  }
}

Wie in den oben abgebildeten Quelltexten zu erkennen, werden die Methoden, die im Interface deklariert wurden, in der Klasse Item implementiert. Hauptsächlich ist dabei die Methode compareTo() von belangen, da diese benutzt wird, um zwei Strings zu vergleichen. Deshalb wird nicht mehr ein Integer verglichen und dann einsortiert, sondern ein String. Dieses Vorgehen ermöglicht uns, dass wird jedes Mögliche Objekt vergleichen können, solange wir ihm eine Id geben können (z.b. Autokennzeichen, Ip-Adresse, etc.)

Außerdem erbt die Klasse SortedList von der Klasse List um auf die Methoden zugreifen zu könne. Dabei werden die Methoden, die Verändert werden müssen, um ein Element sortiert einzufügen, in der Klasse SortedList überschrieben.

Implementierung

Insbesondere die insert() Methode muss überschrieben werden. Da sie praktischerweise auch von den anderen Methoden in der SortedList Klasse aufgerufen wird, ist sie eine der wichtigsten Methoden.

public class SortedList<ContentType extends Sortable<ContentType>> extends List<ContentType> {
    //Von klein nach groß sortiert
    public void setContent(ContentType pContent) {
        this.remove();
        this.insert(pContent);
    }

    public void insert(ContentType pContent) {
        if (pContent != null) {

            if (this.isEmpty()) {
                super.append(pContent);
            }else {

                //Wenn es ein aktuelles Objekt gibt, wird die ID von current gespeichert
                String currentItemID = "";
                if (hasAccess()) currentItemID = this.getContent().getID();

                //Iteriert solange über die Queue, wie current > pContent ist
                this.toFirst();
                while (this.hasAccess() && this.getContent().compareTo(pContent) < 0) {
                    this.next();
                }

                //hasAccess = false, weil pContent das kleinste ELement ist
                if (hasAccess()) super.insert(pContent);
                else super.append(pContent);

                //Current zurücksetzen
                if (currentItemID != "") {
                    getByID(currentItemID);
                } else {
                    this.toLast();
                    this.next();
                }
            }
        }
    }

    public void append(ContentType pContent) {
        this.insert(pContent);
    }

    public void concat(List<ContentType> pList) {
        if (pList != null && !pList.isEmpty()) {

            pList.toFirst();

            while (!pList.hasAccess()) {
                append(pList.getContent());
                pList.remove();
            }
        }
    }

    /**
     * Setzt current auf das Element vor current. Sollte es keine current Node geben oder current auf
     * dem ersten Element sitzen, so bleibt current unverändert.
     */
    public void previous() {
        if (hasAccess() && !this.isEmpty()) {

            ContentType currentItem = this.getContent();
            int steps = 0;
            toFirst();

            while (hasAccess() && getContent() != currentItem) {
                steps++;
                next();
            }

            toFirst();

            for (int i = 0; i < steps-1; i++) next();
        }
    }

    public void getByID(String pId) {
        if (pId != null){
            toFirst();
            while (hasAccess() && this.getContent().getID() != pId){
                next();
            }
        }
    }

    public void removeByID(String pId) {
        if (pId == null) {
            boolean currentAcces = hasAccess();
            ContentType currentItem = null;

            if (currentAcces) {
                currentItem = this.getContent();
            }

            getByID(pId);
            remove();

            if (currentAcces) {
                getByID(currentItem.getID());
            }
        }
    }
}

Related Posts