AuK/Konkrete Datenstrukturen/Linked List

Wiki-Quelltext dieser Seite.

<language>Python</language>
==Linked List==

Im Gegensatz zu Arrays sind Listen ''dynamische'' Datenstrukturen. Die Länge einer Liste steht nach Instanziierung nicht für immer fest. Durch Hinzufügen weiterer Elemente kann die Länge einer Liste bedarfsgerecht angepasst werden. 

Eine '''Linked List''' (verkettete Liste) ist eine Implementation für den ADT "Lineare Liste". 
Linked Lists müssen die folgenden Operationen implementieren:

'' Einfügen eines Elements $x$ in die Liste $L$ - an der Position $p$,
'' Entfernen eines Elements $x$ aus der Liste $L$,
'' Suchen eines Elements $x$ in der Liste $L$ und
'' Zugriff auf das Element $x$ in der Liste $L$

Zur Implementation linearer Listen kommen ''sequentielle Speicherung'' (Array) und die ''verkettete Speicherung'' infrage. 
Für letztere Speicherform betrachten wir zwei Implementationen, nämlich '''Singly Linked List''' (einfach verkettete Liste) und '''Doubly Linked List''' (doppelt verkettete Liste), und illustrieren an diesem Beispiel nochmals den Trade-off zwischen Speicher und Zeit.

===Singly Linked List===

Bei einer '''Singly Linked List''' werden die Elemente (eines bestimmten Grundtyps) der Liste als Nodes (Knoten) abgebildet. Ein Node besteht dabei aus zwei Werten: dem eigentlichen Wert des Elements und einem Pointer, der auf das nächste Element der Liste zeigt. Der Pointer des letzten Elements der Liste hat den Wert '''null'''. Um auf die Liste zuzugreifen, wird die (gespeicherte!) Adresse des ersten Nodes angegeben. Da die Verweise auf das jeweils nächste Element gegeben sind, kann man durch Iteration der Pointer, die entsprechenden Elemente der Liste erreichen. Man kann sich das wie ein "Durchhangeln" vorstellen.

Die Liste [5, 10, 20, 1] wird folgendermaßen dargestellt:

[[Datei:Singly-linked-list_5-10-20-1.png|center]]

<run id="5f370cc593ae7">
import math

class Node:
    def __init__(self):
        self.value = None
        self.next = None

    def add(self, value, index):
        if index > 1 and self.next is not None:
            return self.next.add(value, index - 1)
        elif index == 1:
            new_node = Node()
            new_node.value = value
            new_node.next = self.next
            self.next = new_node
            return True
        return False


class SinglyLinkedList:
    def __init__(self):
        self.head = Node()
        self.length = 0

    def add(self, value, index=None):
        if index is None:
            index = self.length
        if index == 0:
            new_node = Node()
            new_node.value = value
            new_node.next = self.head
            self.head = new_node
            self.length += 1
        elif 0 < index <= self.length:
            if self.head.add(value, index):
                self.length += 1

    def print_lst(self):
        node = self.head
        for i in range(self.length - 1):
            print('{0}, '.format(node.value), end='')
            node = node.next
        print(node.value)

        
lst = SinglyLinkedList()
lst.add(5)
lst.add(10)
lst.add(20)
lst.add(1)
lst.add(-1, 2)

lst.print_lst()
</run>

====Access (Zugriff) und Search (Suche)====

Da man zunächst nur auf den Anfang der Liste zugreifen kann, muss man über die Pointer auf die jeweils nächsten Elemente durch die gesamte Liste iterieren, um das letzte Element der Liste zu erreichen. Der Aufwand zur Suche bzw. zum Zugriff auf ein Element beträgt also $\mathcal{O}(n)$. Dies gilt auch für den Fall, dass das gesuchte Element nicht in der Liste vorkommt.

====Insert (Einfügen)====

Nach dem $m$-ten Element einer Liste soll ein neues Element eingefügt werden. Die Einfügeposition ist durch einen Zeiger auf das $m$-te Element vorgegeben (wird also nicht gesucht). Als erstes wird an einer beliebigen Stelle im Speicher ein neues Node angelegt. Danach muss der Pointer des $m$-ten Elements, der auf das nächste, also $m+1$-te, Element zeigt, in das neu erstellte Node geschrieben werden. Schließlich soll das bisherige $m+1$-te Element Nachfolger des einzufügenden Elements sein. Im letzten Schritt muss der Pointer des $m$-ten Elements so umgeschrieben werden, dass er auf das neu erstellte Node zeigt.

<img width="450" src="https://www.geeksforgeeks.org/wp-content/uploads/gq/2013/03/Linkedlist''insert''middle.png"/>

Für den Sonderfall, dass an erster Stelle, also am Index 0, das Element eingefügt werden soll, muss der Pointer des neuen Nodes auf das bisher erste Element zeigen. Zusätzlich wird der Pointer auf den Head der Linked List entsprechend bearbeitet.

<img width="450" src="https://www.geeksforgeeks.org/wp-content/uploads/gq/2013/03/Linkedlist''insert''at''start.png"/>

In beiden Fällen wird eine konstante Anzahl an Operationen durchgeführt, somit beträgt der Aufwand zum Einfügen $\mathcal{O}(1)$.

====Delete (Entfernen)====

Um das $m$-te Element der Liste zu löschen, muss lediglich der Pointer des $m-1$-ten Nodes so modifiziert werden, dass er auf das $m+1$-te Element zeigt. Auch hier wird lediglich eine konstante Anzahl an Operationen benötigt, was zu einem Aufwand von $\mathcal{O}(1)$ führt.

<img width="450" src="https://www.geeksforgeeks.org/wp-content/uploads/gq/2014/05/Linkedlist''deletion.png"/>

Für den Fall, dass das Element am Index 0 entfernt werden soll, muss der Pointer, der auf den Head der Linked List zeigt, auf das Node mit Index 1 zeigen.

===Doubly Linked List===

Eine Doubly Linked List ist wie eine Singly Linked List implementiert, mit dem Unterschied, dass es bei einer Doubly Linked List zusätzlich zum Pointer auf das nächste Element, einen Pointer, der auf das vorherige Element zeigt, gibt.

<img width="500" src="https://www.geeksforgeeks.org/wp-content/uploads/gq/2014/03/DLL1.png"/>

Der ''prev''-Pointer des ersten Elements zeigt, wie der ''next''-Pointer des letzten Elements, auf '''null'''. 

Die asymptotischen Zeitaufwände der Access-, Insert- und Delete-Operationen verhalten sich genauso, wie bei der Singly Linked List. 

Befindet sich der aktuelle Pointer auf dem Element mit dem Index $i$, so kann man durch den ''prev''-Pointer mit konstantem Aufwand $\mathcal{O}(1)$ auf das Element mit dem Index $i-1$ zugreifen. Bei einer Singly Linked List müsste man wieder am Anfang der Liste beginnen und hätte einen Aufwand von $\mathcal{O}(n)$. Zu erwähnen ist, dass der Speicherbedarf zwar auch $\mathcal{O}(n)$ ist, jedoch das 1.5-fache an Speicher im Vergleich zur Singly Linked List benötigt wird, da durch die zwei Pointer pro Element drei anstatt zwei Speicherplätze beansprucht werden. Hier gilt also das Prinzip "trade space for time".

<run id="5f370cc593b9a">
import math

class DoublyNode:
    def __init__(self):
        self.value = None
        self.next = None
        self.prev = None  # prev Pointer is required in Doubly Linked List

    def add(self, value, index):  # using prev node as parameter to be able to set prev pointer
        if index > 1 and self.next is not None:
            return self.next.add(value, index - 1)
        elif index == 1:
            new_node = DoublyNode()
            new_node.value = value
            new_node.next = self.next
            new_node.prev = self
            self.next.prev = new_node
            self.next = new_node
            return True
        return False

    def add_from_tail(self, value, index):
        if index > 1 and self.prev is not None:
            return self.prev.add_from_tail(value, index - 1)
        elif index == 1:
            new_node = DoublyNode()
            new_node.value = value
            new_node.next = self
            new_node.prev = self.prev
            self.prev.next = new_node
            self.prev = new_node
            return True
        return False

    def remove(self, index):
        if index > 0 and self.next is not None:
            return self.next.remove(index - 1)
        elif index == 0:
            self.prev.next = self.next
            self.next.prev = self.prev
            return True
        return False

    def remove_from_tail(self, index):
        if index > 0 and self.prev is not None:
            return self.prev.remove_from_tail(index - 1)
        elif index == 0:
            self.next.prev = self.prev
            self.prev.next = self.next
            return True
        return False


class DoublyLinkedList:
    def __init__(self):
        node = DoublyNode()
        self.head = node
        self.tail = node  # tail pointer exist to access from end of list
        self.length = 0

    def add(self, value, index=None):
        if index is None:
            index = self.length
        if index == 0 and self.length == 0:
            self.head.value = value
            self.length += 1
        elif index == 0:
            new_node = DoublyNode()
            new_node.value = value
            new_node.next = self.head
            new_node.prev = None
            self.head.prev = new_node
            self.head = new_node
            self.length += 1
        elif 0 < index < self.length:
            if self.head.add(value, index):
                self.length += 1
        elif index == self.length:
            self.add_from_tail(value, 0)

    def add_from_tail(self, value, index):
        if index == 0 and self.length == 0:
            self.tail.value = value
            self.length += 1
        elif index == 0:
            new_node = DoublyNode()
            new_node.value = value
            new_node.next = None
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
            self.length += 1
        elif 0 < index < self.length:
            if self.tail.add_from_tail(value, index):
                self.length += 1
        elif index == self.length:
            self.add(value, 0)

    def remove(self, index):
        if index >= self.length:
            return None
        if index == 0 and self.length == 1:
            self.head.value = None
            self.length -= 1
        elif index == 0:
            self.head.next.prev = None
            self.head = self.head.next
            self.length -= 1
        elif 0 < index < self.length - 1:
            if self.head.remove(index):
                self.length -= 1
        elif index == self.length - 1:
            self.remove_from_tail(0)

    def remove_from_tail(self, index):
        if index >= self.length:
            return None
        if index == 0 and self.length == 1:
            self.tail.value = None
            self.length -= 1
        elif index == 0:
            self.tail.prev.next = None
            self.tail = self.tail.prev
            self.length -= 1
        elif 0 < index < self.length - 1:
            if self.tail.remove_from_tail(index):
                self.length -= 1
        elif index == self.length - 1:
            self.remove(0)

    def print_lst(self):
        node = self.head
        for i in range(self.length - 1):
            print('{0}, '.format(node.value), end='')
            node = node.next
        print(node.value)


lst = DoublyLinkedList()
lst.add(5)
lst.add(10)
lst.add(20)
lst.add(1)
lst.add(-1, 2)
lst.add_from_tail(-2, 4)
lst.remove(2)

lst.print_lst()
</run>

===Fazit===

Eine Linked List (sowohl singly als auch doubly) eignet sich, wenn häufig Elemente eingefügt und entfernt werden, da der Zeitaufwand dafür lediglich $\mathcal{O}(1)$ beträgt. Eine Doubly Linked List ist besonders dann geeignet, wenn man häufig das Vorgängerelement benötigt. Dies ist z. B. bei Browserverläufen oder Undo/Redo-Aktionen der Fall. Hier kommt eine Doubly Linked List zum Einsatz.