103_Elementare_Datenstrukturen.tex

\section{Elementare Datenstrukturen}
\label{elementare_datenstrukturen}

Was ist eine Datenstruktur? Diesen Begriff mathematisch präzise zu fassen ist sehr schwer. Wir überlassen das daher
anderen Vorlesungen und begnügen uns mit einer unpräziseren Definition: Datenstrukturen sind \emph{Daten} mit einer
\emph{Struktur}.

Daten meint dabei sowohl elementare Datentypen wie \texttt{int, float, char}, aber auch komplexere Gebilde wie ein Tupel
$(\text{int}, \text{float})$ oder abstraktere Gebilde wie die Repräsentation eines Gegenstandes oder $x \in \mathbb{R}$.
Die Menge der Daten bezeichnen wir mit $D$.

Struktur kann viel bedeuten. In diesem Kapitel befassen wir uns hauptsächlich mit Strukturen, die eine lineare Ordnung
ermöglichen, die uns also erlauben zu sagen, in welcher ``eindeutigen Reihenfolge'' sich die Daten befinden.
Datenstrukturen, in denen mehr als ein Nachfolger erlaubt ist, behandeln wir in späteren Kapiteln.


\paragraph{Datenstrukturen mit einer Reihenfolge}
Im Folgenden betrachen wir die vier bekanntesten Datenstrukturen, die uns zumindest eine Reihenfolge geben. Das
mathematische Äquivalent wäre also nicht eine Menge, sondern ein Tupel $(d_0, d_1, d_2, \dots)$ mit $d_i$ als
das Nutzdatum an der $i$-ten Stelle. Damit einher geht
die Einführung des Index $i \in \mathbb{N}_0$, wir fangen also (um Verwirrung beim Programmieren vorzubeugen) mit
$0$ an zu zählen. Dieser Index erlaubt uns, den Index $i$ (manchmal auch Schlüssel) und die Daten der Datenstruktur
$\mathcal{D}$ zu unterscheiden. Die Daten der Datenstruktur an der Stelle $i$ nennen wir $\mathcal{D}[i]$.

Wir werden zusätzlich Implementierungen dieser Datenstrukturen angeben. Diese sind in imperativer Perspektive für ein
Maschinenmodell mit Random-Access-Memory (RAM) $\mathcal{M}$ zu verstehen.
Um zu beschreiben, an welcher Stelle in $\mathcal{M}$ wir zugreifen wollen benutzen wir sogenannte pointer $p \in P =
\mathbb{N} \cup \{\text{void}\}$. Ein Zugriff ist dann wie folgt definiert:
\[
  \mathcal{M}[p] = 
  \begin{cases}
    \texttt{error}  &\text{ if } p = \texttt{void} \\
    d_p             &\text{ else},
  \end{cases}
\]
wobei $d_p$ der Speicherinhalt an der Stelle $p$ ist.

Die definierende Eigenschaft dieses Maschinenmodells ist, dass der Zugriff $\mathcal{M}[p]$ auf ein Speicherfeld stets gleich lange braucht,
egal wo es liegt. Desweiteren nehmen wir an, unendlich viele Speicherfelder zu haben und nicht nur das, auch jedes
einzelne Speicherfeld fasst unser Datum $d$, egal wie groß es sein mag.

\begin{figure}[!htp]
  \centering
  \tikzsetnextfilename{ram}
  \begin{tikzpicture}[box/.style = {draw, minimum size=9mm, inner sep=0pt, outer sep=0pt, anchor=center},]
    \matrix (array) [matrix of nodes, nodes={box}, column sep=-\pgflinewidth, inner sep=0pt]
    {
      $d_0 $ & $d_1$ & \qquad $\dots$ \qquad \vphantom{3} & $d_{p-1}$  & $d_p$ & $d_{p+1}$ & \qquad $\dotsm$ \qquad \vphantom{3} \\
    };
  \end{tikzpicture}
  \caption{Der (unendliche) random access Maschinenspeicher $\mathcal{M}$.}
\end{figure}

\paragraph{Notation}
In der Hoffnung, die folgende Mischung aus mathematischer Notation, Pseudocode und Erklärungen verständlicher zu
gestalten, benutzen wir folgende notationelle Konventionen: Indexe $i$, sowie Pointer auf Speicheradressen $p$ und (für
uns abstrakte) Nutzlast $d$ wird in mathematischem $italic$ geschrieben. Datenstrukturen wie beispielsweise das Array
$\mathcal{A}$ oder die Liste $\mathcal{L}$ werden in \textbackslash mathcal\{\} gesetzt, auch der RAM $\mathcal{M}$ gehört
notationell zu den Speicherstrukturen. Systemfunktionen wie $\texttt{reference\_of}$  oder sehr triviale zu implementierende Funktionen wie
$\texttt{len}$ für die Länge von Speicherstrukturen werden in \texttt{truetype} gesetzt, um ihre Maschinennähe darzustellen.
Ebenso bekommen all unsere in Psudeocode notierten Algorithmen diese Notation.

\subsection{Arrays $\mathcal{A}$}
Das Array $\mathcal{A}$ ist eine Datenstruktur von fixer Größe $n \in \mathbb{N}$. Aus logischer Perspektive stehen benachbarte
Elemente direkt nebeneinander. Das Array $\mathcal{A}$ von Größe $n$ ist also nichts weiter als
$\mathcal{M}[s,\dots,s+n-1]$, wobei $s \in \mathbb{N}$ ein gewisser Versatz ist.
Durch die Natur des RAM ist Lese- oder Schreibzugriff auf das $i$-te Feld in konstanter
Zeit $\mathcal{O}(1)$ möglich. Das ist das Alleinstellungsmerkmal des Arrays!

Es gibt aber keine kanonische Möglichkeit, die Größe des Arrays zu verändern, also Elemente hinzuzufügen oder zu
entfernen. Das sogenannte \emph{dynamische Array} bietet Möglichkeiten dazu, ist aber keine elementare Datenstruktur.
Wir geben daher später keine Laufzeiten für das Einfügen oder Entfernen von Elementen an.

\begin{figure}[!htp]
  \centering
  \tikzsetnextfilename{array}
  \begin{tikzpicture}[box/.style = {draw, minimum size=9mm, inner sep=0pt, outer sep=0pt, anchor=center},]
    \matrix (array) [matrix of nodes, nodes={box}, column sep=-\pgflinewidth, inner sep=0pt]
    {
              &                                  &            & $\mathcal{A}[0]$  & $\mathcal{A}[1]$  & \quad $\dotsm$  \quad \vphantom{3} & \enspace  $\mathcal{A}[n-1]$ \enspace & \\
      $d_0 $  & \quad $\dots$ \quad \vphantom{3} & $d_{s-1}$  & $d_s$             & $d_{s+1}$         & \quad $\dotsm$  \quad \vphantom{3} & \quad $d_{s+n-1}$ \quad        & \quad $\dots$ \quad \vphantom{3} \\
    };
  \end{tikzpicture}
  \caption{Ein Array $\mathcal{A}$ von Länge $n$ mit offset $s$ in $\mathcal{M}$.}
\end{figure}

Arrays sind die einfachsten Datenstrukturen auf Maschinen mit Random-Access-Memory. Allerdings steht der Vorteil der immer gleichen
Zugriffszeit wird dem Nachteil der Inflexibilität gegenüber: Zur Laufzeit können Elemente weder hinten, noch irgendwie
in der Mitte eingefügt werden. Es ist lediglich ein neubeschreiben der Felder möglich. Desweiteren sind Arrays
\emph{endlich} lang. 

\subsection{Listen $\mathcal{L}$}
Nicht immer können wir vorhersagen, wie viele Datensätze wir im Laufe des Programmablaufs entgegennehmen. Daher benötigen wir
Datenstrukturen, in welche wir Daten einfügen, aber auch wieder löschen können. Ein elementarer Prototyp ist die einfach
verkettete Liste:

\begin{figure}[!htb]
  \centering
  \includegraphics[width=0.5\textwidth]{bilder/Singly-linked-list.png}
  \caption{Graphische Darstellung einer einfach verketteten Liste: $12, 99$ und $37$ sind hier die Nutzdaten, der
  Schlusspointer $\texttt{void}$ wird mit dem gekreuzten Quadrat dargestellt.}
  \label{fig:linked_list}
\end{figure}

Aus einer (etwas abstrakteren) Sicht gibt es dann Nodes $D \times P$ und Listen an sich sind eigentlich nur
headnodes, also ein Node, der keine Daten enthält, sondern nur auf das erste Element der Liste zeigt.
Wir wollen dabei folgende Operationen haben:
\begin{itemize}
  \item $\texttt{is\_empty}: \mathcal{L} \rightarrow \text{Bool}$,
  \item $\texttt{head}: \mathcal{L} \rightarrow \text{Node}$,
  \item $\texttt{next}: \text{Node} \rightarrow \text{Node}$,
  \item $\texttt{data}: \text{Node} \rightarrow D$,
  \item $\texttt{pointer}: \text{Node} \rightarrow P$,
  \item $\texttt{insert\_after}: \text{Node} \times D \rightarrow \{\}$,
  \item $\texttt{delete\_after}: \text{Node} \rightarrow \{\}$,
\end{itemize}
Ein Node $(d,\texttt{void})$ ist dabei das letzte Element einer Liste, ein Node $(\texttt{void}, p)$ ist der headnode.
Eine neue, leere Liste ist also lediglich dieses Kopfelement $(\texttt{void} ,\texttt{void})$.

Der Bequemlichkeit halber führen wir auch für Listen eine Indexnotation ein: $\mathcal{L}[0]$ referiert auf das
erste Element der Liste, $\mathcal{L}[2]$ auf das dritte, etc. Dabei ist die Abkürzung definiert als
\begin{align*}
  \mathcal{L}[i] &= \texttt{next}^i(\texttt{head}(\mathcal{L})) \\
  &:= \underbrace{\texttt{next}(\texttt{next}(\texttt{next}\dots}_{\text{$i$ mal}}\  (\texttt{head}(\mathcal{L})) \ 
  \underbrace{\dots )))}_{\text{$i$ mal}}
\end{align*}
Offensichtlich ist hier, anders als beim Array, die Zugriffszeit linear abhängig von~$i$.

\subsubsection{Implementierung von Listen auf RAM}
Nodes sind Tupel $(d,p)$, headnode ist $(\texttt{void}, p)$. Die meisten Operationen sind trivial:
\begin{itemize}
  \item $\texttt{is\_empty}(\mathcal{L}) = \text{True}$ genau dann, wenn
    $\texttt{pointer}(\texttt{head}(\mathcal{L})) = \texttt{void}$.
  \item $\texttt{head}(\mathcal{L}) = (\texttt{void},p)$,
  \item $\texttt{next}((d,p)) = \mathcal{M}[p]$,
  \item $\texttt{data}((d,p)) = d$,
  \item $\texttt{pointer}((d,p)) = p$,
\end{itemize}

Anders als in einem Array können wir nun an jeder Stelle der Liste etwas einfügen, siehe Abbildung
\ref{fig:linked_list_insert}. Beachtenswert ist hierbei, dass bei Kenntnis der Adresse des vorherigen Listenelements nur
$\mathcal{O}(1)$ Aufwand vonnöten ist. \\
\begin{algorithm}[H]
  \SetNlSty{texttt}{[}{]}
  \caption{\texttt{insert\textunderscore after}$((d,p), d')$}
  \KwIn{A node $(d,p)$ to the list element after which to insert the new list element storing $d'$}
  \KwOut{Side effects in the memory $\mathcal{M}$}
  new\_element $= (d', \texttt{pointer}(\texttt{next}((d,p))))$ \;
  $\texttt{next}(\mathcal{M}[p]) \leftarrow \texttt{reference\_of}(new\_element)$\;
\end{algorithm}
Hier gibt $\texttt{reference\_of}$ die Speicherposition des frisch erstellten Nodes zurück.

\begin{figure}[!htb]
  \centering
  \includegraphics[width=0.7\textwidth]{bilder/LinkedLists-addingnode.png}
  \caption{Einfügen eines Listenelements an arbitrarer Stelle}
  \label{fig:linked_list_insert}
\end{figure}

Auch für das Löschen ist nur das Umbiegen eines einzelnen Zeigers nötig, siehe Abbildung \ref{fig:linked_list_delete}:\\

\begin{algorithm}[H]
  \SetNlSty{texttt}{[}{]}
  \caption{\texttt{delete\textunderscore after((d,p))}}
  \KwIn{A node $(d,p)$ to the list element whose successor shall be removed from the list}
  \KwOut{Side effects in the memory $\mathcal{M}$}
  $((d,p)) \leftarrow (d, \texttt{pointer}(\texttt{next}((d,p))))$ \;
\end{algorithm}

\begin{figure}[!htb]
  \centering
  \includegraphics[width=0.6\textwidth]{bilder/LinkedLists-deletingnode.png}
  \caption{Löschen eines Listenelements an arbitrarer Stelle}
  \label{fig:linked_list_delete}
\end{figure}

\subsubsection{Varianten von Listen}
Es gibt Listen in fast allen Geschmacksrichtungen. Häufig verwendet werden beispielsweise die sogenannten doppelt
verketteten Listen (Abbildung
\ref{fig:doubly_linked_list}). Deren Nodes $(d,p_{\text{prev}}, p_{\text{next}})$ haben zwei Pointer, sodass in beide
Richtungen traversiert werden kann.

\begin{figure}[!htb]
  \centering
  \includegraphics[width=0.8\textwidth]{bilder/doubly_linked_list.png}
  \caption{Graphische Darstellung einer doppelt verketteten Liste}
  \label{fig:doubly_linked_list}
\end{figure}

Frei kombinierbar gibt es aber auch zirkulär verketteten Listen (Abbildung \ref{fig:circular_linked_list}),
bei denen anstelle der Referenz auf $\texttt{void}$ wieder auf den Anfang referenziert wird.

\begin{figure}[!htb]
  \centering
  \includegraphics[width=0.5\textwidth]{bilder/circular_linked_list.png}
  \caption{Graphische Darstellung einer zirkulär verketteten Liste}
  \label{fig:circular_linked_list}
\end{figure}

\subsubsection{Anwendung}
Verkettete Listen sind nur noch in den seltensten Fällen wirklich notwendig, meistens gibt es bessere Datenstrukturen.
Allerdings kann eine doppelt verkettete Liste als die natürlichste Datenstruktur einer Turing-Maschine betrachtet
werden.


\subsection{Stacks $\mathcal{S}$}
Ein Stack $\mathcal{S}$ ist wie ein Stapel Teller: Hinzufügen oder Entnehmen von weiteren Tellern ist nur an der Spitze möglich.

Viele Anwendungen brauchen genau das, aber auch nicht mehr. Beispielsweise das Umdrehen der Reihenfolge einer Sequenz,
das  Umformen von Prefix- in Postfixnotation, oder allgemeiner: Syntax parsen. Ebenso braucht man zur Verwaltung rekursiver
Funktionsaufrufe (siehe Kapitel \ref{section:recursion}) einen Stack. Solche Algorithmen arbeiten mit der sogenannten LIFO-Strategie,
was für last in, first out steht.

Aber auch aus rein abstrakter Sicht ist ein Stack interessant. Während wir gleich einen Stack mithilfe einer verketteten
Liste implementieren (aus Bequemlichkeit, nicht aus Notwendigkeit), können umgekehrt auch Listen mit zwei Stacks implementiert
werden. Es ist also, in diesem Sinne, eine ebenso fundamentale Datenstruktur.

Ein Stack hat zwei Operationen: $\texttt{push}$, was dem dazulegen eines weiteren Tellers entspricht, sowie
$\texttt{pop}$, welches den obersten Teller entfernt. Die LIFO-Bedingung wird dann mit dem Axiom
\[
  x = \texttt{pop}(\texttt{push}(x))
\]
beschrieben.

\subsubsection{Stackoperationen}
Wir implementieren den Stack $\mathcal{S}$ mittels einer oben definierten verkettete Liste. Ein leerer Stack ist daher auch einfach
eine leere Liste $\mathcal{L}$.

Der Test auf Inhalt ist somit ident zum entsprechenden $\texttt{is\_empty}$ für Listen.
Möchten wir nun ein Element mit Nutzlast $d$ hinzufügen, so ist dies auch auf Listenoperationen zurückführbar:
\[
  \texttt{push}(\mathcal{S}, d) := \texttt{insert\_after}(\texttt{head}(\mathcal{L}), d)
\]
Wir haben die gleiche Nebenwirkung im Speicher. Das Entfernen einen Elements besteht aus zwei elementaren Schritten, dem
Auslesen, und dem Löschen:  \\
\begin{algorithm}[H]
  \SetNlSty{texttt}{[}{]}
  \caption{$\texttt{pop}(\mathcal{S})$}
  \KwIn{A Stack $\mathcal{S}$}
  \KwOut{The top element of the stack $\mathcal{S}$}
  \KwOut{Side effects in the memory $\mathcal{M}$: Removal of the returned top element}
  $\text{ret} \leftarrow \texttt{data}(\mathcal{M}[\texttt{next}(\texttt{head}(\mathcal{S}))])$ \;
  $\texttt{delete\_after}(\texttt{head}(\mathcal{S}))$ \;
  \KwRet ret \;
\end{algorithm}

Charmant für uns ist, dass alle Operationen auf Stacks jeweils $\mathcal{O}(1)$ Zeit brauchen, meist also
vernachlässigbar sind.

\subsection{Queues $\mathcal{Q}$}
Anders als der Stapel, der die LIFO-Strategie verfolgt, beschreibt die Queue eine (faire) Warteschlange: Wer als Erstes
da war, kommt als Erstes dran. Man nennt es auch die FIFO-Strategie (first-in, first-out). 
Ansonsten hat auch sie zwei Funktion, $\texttt{put}$, das Hintanstellen, sowie $\texttt{get}$, das Drankommen.

\subsubsection{Queueoperationen}
Wir implementieren eine Queue $\mathcal{Q}$ wieder über eine verkettete Liste $\mathcal{L}$, aber diesmal sollten wir
noch eine Referenz auf das letzte Element mitführen (sonst müssten wir immer mit $\mathcal{O}(n)$ Aufwand zum Ende der
verketteten Liste laufen. Das ist prinzipiell möglich, aber langsam.). Die Queue $\mathcal{Q}$ besteht also also aus $\mathcal{Q} = (\mathcal{L}, p_{\text{last}})$.
Wir fügen Elemente am Ende der Liste hinzu und lesen sie vom Anfang der Kette ab.
Der Test auf Leere ist wieder analog wie bei Listen.

\begin{algorithm}[H]
  \SetNlSty{texttt}{[}{]}
  \caption{$\texttt{put}(\mathcal{Q}, d)$}
  \KwIn{A queue $\mathcal{Q}$, data $d$}
  \KwOut{Side effects in the memory $\mathcal{M}$: Insertion of an Element at the end of the list $\mathcal{L}$ as well
  as change of the value $p_{\text{last}}$ of $\mathcal{Q}$}
  $\texttt{insert\_after}(p_{\text{last}}, d)$ \;
  $p_{\text{last}} \leftarrow \texttt{next}(\mathcal{M}[p_{\text{last}}])$ \;
\end{algorithm}

Die Funktion \texttt{get} entspricht genau dem Stackpendant \texttt{pop}:\\
\begin{algorithm}[H]
  \SetNlSty{texttt}{[}{]}
  \caption{$\texttt{get}(\mathcal{Q})$}
  \KwIn{A queue $\mathcal{Q}$}
  \KwOut{The oldest element of the queue $\mathcal{Q}$}
  \KwOut{Side effects in the memory $\mathcal{M}$: Removal of the returned top element}
  $\text{ret} \leftarrow \texttt{data}(\mathcal{M}[\texttt{next}(\texttt{head}(\mathcal{L}))])$ \;
  $\texttt{delete\_after}(\texttt{head}(\mathcal{L}))$ \;
  \KwRet ret \;
\end{algorithm}

Wiederum benötigen alle Operationen lediglich $\mathcal{O}(1)$ Zeit.

\subsection{Übersichtstabelle zu den asymptotischen Aufwänden}

\begin{figure}[!htb]
  \centerfloat
  \begin{tabular}{l||c|c|c|c|c|c}
    Datenstruktur $\mathcal{D}$   & $\mathcal{D}[1]$ & $\mathcal{D}[i]$ & $\mathcal{D}[n]$ & Einfügen          & Löschen           & Suchen            \\
    \hline
    Array                         & $\mathcal{O}(1)$ & $\mathcal{O}(1)$ & $\mathcal{O}(1)$ &                   &                   & $\mathcal{O}(n)$  \\
    Liste                         & $\mathcal{O}(1)$ & $\mathcal{O}(i)$ & $\mathcal{O}(n)$ & $\mathcal{O}(1)$  & $\mathcal{O}(1)$  & $\mathcal{O}(n)$  \\
    Stack                         & $\mathcal{O}(1)$ &                  &                  & $\mathcal{O}(1)$  & $\mathcal{O}(1)$  &   \\
    Queue                         &                  &                  & $\mathcal{O}(1)$ & $\mathcal{O}(1)$  & $\mathcal{O}(1)$  &   \\
  \end{tabular}
\end{figure}
Beim Einfügen oder Löschen in Listen wird vorausgesetzt, dass die Adresse $p$ bekannt ist. Ist das Element nur durch
seine Position oder seinen Inhalt bekannt, muss zuerst mit entsprechendem Aufwand zum Element traversiert werden.