add list method slides

4 files changed, 529 insertions, 0 deletions

diff --git a/Info/12/Listen/Funktionen/.gitignore b/Info/12/Listen/Funktionen/.gitignore
new file mode 100644
index 00000000..dd6b8c3d
--- /dev/null
+++ b/Info/12/Listen/Funktionen/.gitignore
@@ -0,0 +1,2 @@
+slides-wiederholung.pdf
+slides-wiederholung.pptx
diff --git a/Info/12/Listen/Funktionen/img/playlist_song_to_remove.png b/Info/12/Listen/Funktionen/img/playlist_song_to_remove.png
new file mode 100644
index 00000000..8734d89b
--- /dev/null
+++ b/Info/12/Listen/Funktionen/img/playlist_song_to_remove.png
diff --git a/Info/12/Listen/Funktionen/slides-wiederholung.md b/Info/12/Listen/Funktionen/slides-wiederholung.md
new file mode 100644
index 00000000..35b312dd
--- /dev/null
+++ b/Info/12/Listen/Funktionen/slides-wiederholung.md
@@ -0,0 +1,202 @@
+---
+author: Florian Fischer
+theme: metropolis
+aspectratio: 169
+---
+
+## \faIcon{comments} Wiederholung: Speicherplatz \hfill 1/5
+
+Nimm Stellung zu folgender Aussage: \vspace{1cm}
+
+> Eine Warteschlange ist die *speicherplatzsparenste* Art mehrere Objekte zu speichern. 
+
+\pause
+
+\begin{tikzpicture}[overlay, remember picture]
+  \node[rotate=5,scale=2] at (4, 0.3) {\large \boldred{Falsch}};
+\end{tikzpicture}
+
+\pause
+
+```java
+// Braucht Speicher für n Objekte und die Länge
+Objekt[] array;
+// Braucht Speicher für n Objekte und n Nachfolger-Referenzen
+Liste    liste;
+```
+
+## \faIcon{comments} Wiederholung: Länge \hfill 2/5
+
+Nimm Stellung zu folgender Aussage: \vspace{1cm}
+
+> Die Länge einer Liste, kann einfach an der Anzahl der gespeicherten Objekte abgelesen werden.
+
+\pause
+
+\begin{tikzpicture}[overlay, remember picture]
+  \node[rotate=5,scale=2] at (4, 0.3) {\large \boldred{Falsch}};
+\end{tikzpicture}
+
+\centering
+\begin{tikzpicture}
+ \begin{object}[text width=3cm]{liste}{0,0}
+  \attribute{anfang}
+  \attribute{ende}
+ \end{object}
+
+ \begin{object}[text width=3.5cm]{node1}{-5,-2.5}
+  \attribute{next}
+ \end{object}
+
+ \node[fill=black, circle, minimum size=0.005cm, scale=0.5] (n1) at (-5.8, -3.3) {};
+ \draw[line width=2pt, -latex, draw=blue!80] (n1) edge [bend right=15] (-2, -2.75);
+
+ \begin{object}[text width=3.5cm]{node2}{0,-2.5}
+  \attribute{next}
+ \end{object}
+
+ \node[fill=black, circle, minimum size=0.005cm, scale=0.5] (n1) at (-0.8, -3.3) {};
+ \draw[line width=2pt, -latex, draw=blue!80] (n1) edge [bend right=15] (3, -2.75);
+
+ \begin{object}[text width=3.5cm]{node3}{5,-2.5}
+  \attribute{next}
+ \end{object}
+
+ % Anfang
+ \node[fill=black, circle, minimum size=0.005cm, scale=0.5] (anfang) at (-1.6, -0.81) {};
+ \draw[line width=2pt, -latex, draw=blue!80] (anfang) edge [bend right=25] (-5.1, -2.45);
+
+ % Ende
+ \node[fill=black, circle, minimum size=0.005cm, scale=0.5] (ende) at (-0.35, -1.4) {};
+ \draw[line width=2pt, -latex, draw=blue!80] (ende) edge [bend left=20] (5.1, -2.45);
+\end{tikzpicture}
+
+## \faIcon{comments} Wiederholung: Arten von Listen \hfill 3/5
+
+Nimm Stellung zu folgender Aussage: \vspace{0.75cm}
+
+> Eine Liste kann sowohl als Warteschlange und als Stapel verwendet werden.
+
+\pause
+
+\begin{tikzpicture}[overlay, remember picture]
+  \node[rotate=5,scale=2] at (0.75\textwidth, 1.7) {\large \textbf{\textcolor{green!80!black}{Korrekt}}};
+\end{tikzpicture}
+
+\centering
+\begin{tikzpicture}
+ \begin{object}[text width=3cm]{liste}{0,0}
+  \attribute{anfang}
+  \attribute{ende}
+ \end{object}
+
+ \begin{object}[text width=3.5cm]{node1}{-5,-2.5}
+  \attribute{next}
+ \end{object}
+
+ \node[fill=black, circle, minimum size=0.005cm, scale=0.5] (n1) at (-5.8, -3.3) {};
+ \draw[line width=2pt, -latex, draw=blue!80] (n1) edge [bend right=15] (-2, -2.75);
+
+ \begin{object}[text width=3.5cm]{node2}{0,-2.5}
+  \attribute{next}
+ \end{object}
+
+ \node[fill=black, circle, minimum size=0.005cm, scale=0.5] (n1) at (-0.8, -3.3) {};
+ \draw[line width=2pt, -latex, draw=blue!80] (n1) edge [bend right=15] (3, -2.75);
+
+ \begin{object}[text width=3.5cm]{node3}{5,-2.5}
+  \attribute{next}
+ \end{object}
+
+ % Anfang
+ \node[fill=black, circle, minimum size=0.005cm, scale=0.5] (anfang) at (-1.6, -0.81) {};
+ \draw[line width=2pt, -latex, draw=blue!80] (anfang) edge [bend right=25] (-5.1, -2.45);
+
+ % Ende
+ \node[fill=black, circle, minimum size=0.005cm, scale=0.5] (ende) at (-1.6, -1.4) {};
+ \draw[line width=2pt, -latex, draw=blue!80] (ende) edge [bend right=25] (-5.1, -2.45);
+\end{tikzpicture}
+
+## \faIcon{comments} Wiederholung: Listen-Traversierung \hfill 4/5
+
+Nimm Stellung zu folgender Aussage: \vspace{0.75cm}
+
+> Eine einfach-verkettete Liste kann nur rekursiv durchlaufen werden.
+
+\centering
+\begin{tikzpicture}
+ \begin{object}[text width=3.5cm]{liste1}{-5,-2.5}
+  \attribute{first}
+ \end{object}
+
+ \node[fill=black, circle, minimum size=0.005cm, scale=0.5] (n1) at (-5.8, -3.3) {};
+ \draw[line width=2pt, -latex, draw=blue!80] (n1) edge [bend right=15] (-2, -2.75);
+
+ \begin{object}[text width=3.5cm]{node2}{0,-2.5}
+  \attribute{next}
+ \end{object}
+
+ \node[fill=black, circle, minimum size=0.005cm, scale=0.5] (n1) at (-0.8, -3.3) {};
+ \draw[line width=2pt, -latex, draw=blue!80] (n1) edge [bend right=15] (3, -2.75);
+
+ \begin{object}[text width=3.5cm]{node3}{5,-2.5}
+  \attribute{next}
+ \end{object}
+\end{tikzpicture}
+
+\pause
+
+\begin{tikzpicture}[overlay, remember picture]
+  \node[rotate=5,scale=2] at (4, 0.3) {\large \boldred{Falsch}};
+\end{tikzpicture}
+
+\pause
+
+```java
+for (Node n = first; n != null; n = n.next) {
+  println(n);
+}
+```
+
+## \faIcon{comments} Wiederholung: alles hat eine Ende ... \hfill 5/5
+
+Nimm Stellung zu folgender Aussage: \vspace{1cm}
+
+> Eine Liste braucht eine Referenz auf das erste und das letzte Objekt.
+
+\pause
+
+\begin{tikzpicture}[overlay, remember picture]
+  \node[rotate=5,scale=2] at (4, 0.3) {\large \boldred{Falsch}};
+\end{tikzpicture}
+
+\pause
+
+\centering
+\begin{tikzpicture}
+ \begin{object}[text width=3cm]{liste}{0,0}
+  \attribute{anfang}
+ \end{object}
+
+ \begin{object}[text width=3.5cm]{node1}{-5,-2.5}
+  \attribute{next}
+ \end{object}
+
+ \node[fill=black, circle, minimum size=0.005cm, scale=0.5] (n1) at (-5.8, -3.3) {};
+ \draw[line width=2pt, -latex, draw=blue!80] (n1) edge [bend right=15] (-2, -2.75);
+
+ \begin{object}[text width=3.5cm]{node2}{0,-2.5}
+  \attribute{next}
+ \end{object}
+
+ \node[fill=black, circle, minimum size=0.005cm, scale=0.5] (n1) at (-0.8, -3.3) {};
+ \draw[line width=2pt, -latex, draw=blue!80] (n1) edge [bend right=15] (3, -2.75);
+
+ \begin{object}[text width=3.5cm]{node3}{5,-2.5}
+  \attribute{next}
+ \end{object}
+
+ % Anfang
+ \node[fill=black, circle, minimum size=0.005cm, scale=0.5] (anfang) at (-1.6, -0.81) {};
+ \draw[line width=2pt, -latex, draw=blue!80] (anfang) edge [bend right=25] (-5.1, -2.45);
+\end{tikzpicture}
diff --git a/Info/12/Listen/Funktionen/slides.md b/Info/12/Listen/Funktionen/slides.md
new file mode 100644
index 00000000..4334ad44
--- /dev/null
+++ b/Info/12/Listen/Funktionen/slides.md
@@ -0,0 +1,325 @@
+---
+author: Florian Fischer
+theme: metropolis
+aspectratio: 169
+header-includes:
+  \usepackage{pgf-umlsd}
+---
+
+```{.include}
+slides-wiederholung.md
+```
+
+## \faIcon{chalkboard-teacher} Wiederholung: Die Liste
+
+\begin{merke}
+Die \boldred{Liste} ist eine Datenstruktur, die eine \boldred{1:n}-Beziehung ermöglicht, indem jedes Element seinen Nachfolger selbst verwaltet.
+Der Wert von n ist \boldred{unbeschränkt}.
+Eine Beziehung zwischen Objekten der gleichen Klasse nennt man \boldred{rekursiv}.
+\end{merke}
+
+\centering
+\begin{tikzpicture}
+ \begin{object}[text width=3cm]{liste}{0,0}
+  \attribute{anfang}
+  \attribute{ende}
+ \end{object}
+
+ \begin{object}[text width=3.5cm]{lied1}{-5,-2.5}
+  \attribute{name = "foo"}
+  \attribute{next}
+ \end{object}
+
+ \node[fill=black, circle, minimum size=0.005cm, scale=0.5] (n1) at (-5.8, -3.9) {};
+ \draw[line width=2pt, -latex, draw=blue!80] (n1) edge [bend right=15] (-2, -2.75);
+
+ \begin{object}[text width=3.5cm]{lied2}{0,-2.5}
+  \attribute{name = "bar"}
+  \attribute{next}
+ \end{object}
+
+ \node[fill=black, circle, minimum size=0.005cm, scale=0.5] (n1) at (-0.8, -3.9) {};
+ \draw[line width=2pt, -latex, draw=blue!80] (n1) edge [bend right=15] (3, -2.75);
+
+ \begin{object}[text width=3.5cm]{lied3}{5,-2.5}
+  \attribute{name = "baz"}
+  \attribute{next}
+ \end{object}
+
+ % Anfang
+ \node[fill=black, circle, minimum size=0.005cm, scale=0.5] (anfang) at (-1.6, -0.81) {};
+ \draw[line width=2pt, -latex, draw=blue!80] (anfang) edge [bend right=25] (-5.1, -2.45);
+
+ % Ende
+ \node[fill=black, circle, minimum size=0.005cm, scale=0.5] (ende) at (-0.35, -1.4) {};
+ \draw[line width=2pt, -latex, draw=blue!80] (ende) edge [bend left=20] (5.1, -2.45);
+\end{tikzpicture}
+
+## \faIcon{chalkboard-teacher} Wiederholung: Länge {.standout}
+
+\Large
+Woher wissen wir wie lang die Liste ist?
+
+## \faIcon{chalkboard-teacher} Wiederholung: Die Rekursive-Methode `getLength`
+
+![](img/Copyrighted/cornelson_inf6_intro_length.jpg){.center}
+
+## \faIcon{chalkboard-teacher} Wiederholung: Die Rekursive-Methode `getLength`
+
+Jedes **Lied** bestimmt die Anzahl der Lieder hinter sich, indem es seinen Nachfolger nach der Länge frägt und eins addiert.
+
+\begin{pseudocode}
+Methode Song.GibLänge(): \\
+\phantom{.}~~falls kein Nachfolger \\
+\phantom{.}~~~~antworte 1 \\
+\phantom{.}~~sonst \\
+\phantom{.}~~~~nachMir <- Nachfolger.GibLänge() \\
+\phantom{.}~~~~antworte nachMir + 1  \\
+\end{pseudocode}
+
+## Sequenzdiagramm: Die Rekursive-Methode `getLength()`
+
+\begin{sequencediagram}
+    \newthread{A}{playlist}{}
+    \newinst[1.5]{B}{s1}{}
+    \newinst[1.5]{C}{s2}{}
+    \newinst[1.5]{D}{s3}{}
+    \begin{call}{A}{getLength()}{B}{3}
+    \begin{call}{B}{getLength()}{C}{2}
+    \begin{call}{C}{getLength()}{D}{1}
+    \end{call}
+    \end{call}
+    \end{call}
+\end{sequencediagram}
+
+## \faIcon{chalkboard-teacher} Wiederholung: Die Rekursive-Methode `getLength`
+
+::: {.columns align=center}
+:::: {.column width=50%}
+\begin{pseudocode}
+Methode Song.GibLänge(): \\
+\phantom{.}~~falls kein Nachfolger \\
+\phantom{.}~~~~antworte 1 \\
+\phantom{.}~~sonst \\
+\phantom{.}~~~~nachMir <- Nachfolger.GibLänge() \\
+\phantom{.}~~~~antworte nachMir + 1  \\
+\end{pseudocode}
+::::
+
+:::: {.column width=50%}
+```java
+int getLength() {
+  if (next == null)
+    return 1;
+  else
+    return next.getLength() + 1;
+}
+```
+::::
+:::
+
+# Funktionen
+
+## Suche {.standout}
+
+\Large
+
+Wie können wir ein Lied in der Liste finden?
+
+## Die Rekursive-Methode `find(title)` {.t}
+
+### \faIcon{lightbulb} **Idee**
+
+\pause
+
+>1. Bin ich das gesuchte Lied?
+>2. Der Nachfolger wird gefragt, falls vorhanden.
+>3. Wenn kein Nachfolger mehr existiert, wurde das Lied nicht gefunden.
+
+```{=latex}
+\only<5>{
+```
+
+### \faIcon{pencil-alt} 1. Arbeitsauftrag \hfill 10min
+
+Zeichne das Sequenzdiagramm, eines `find("bar")` Methodenaufrufs.
+
+### \faIcon{desktop} 2. Arbeitsauftrag
+
+Implementiere die **rekursive** Methode `Song find(String title)`.
+
+```{=latex}
+}
+```
+
+## Sequenzdiagramm: Die Rekursive-Methode `find(title)`
+
+### Lied ist in der Playlist
+
+\begin{sequencediagram}
+    \newthread{A}{playlist}{}
+    \newinst[1.5]{B}{s1}{}
+    \newinst[1.5]{C}{s2}{}
+    \newinst[1.5]{D}{s3}{}
+    \begin{call}{A}{find("2")}{B}{s2}
+    \begin{call}{B}{find("2")}{C}{s2}
+    \end{call}
+    \end{call}
+\end{sequencediagram}
+
+## Sequenzdiagramm: Die Rekursive-Methode `find(title)`
+
+### Lied ist \boldred{nicht} in der Playlist
+
+\begin{sequencediagram}
+    \newthread{A}{playlist}{}
+    \newinst[1.5]{B}{s1}{}
+    \newinst[1.5]{C}{s2}{}
+    \begin{call}{A}{find("3")}{B}{null}
+    \begin{call}{B}{find("3")}{C}{null}
+    \end{call}
+    \end{call}
+\end{sequencediagram}
+
+## Die Rekursive-Methode `find(title)`
+
+```java
+class Song {
+  Song find(String tofind) {
+    if (title == tofind) // 1. Ich bin das gesuchte Lied
+      return this; // Antworte mit DIESEM Objekt
+
+    if (next != null) // 2. Ich habe einen Nachfolger
+      return next.find(tofind); // Die Antwort des Nachfolgers weitersagen
+
+    return null; // 3. Kein Nachfolger -> Lied ist nicht enthalten
+  }
+}
+```
+
+## {.standout}
+
+![](img/playlist_song_to_remove.png){.center height=50%}
+
+\Large
+
+Wie können wir ein Lied wieder löschen?
+
+## Die Rekursive-Methode `remove(title)` {.t}
+
+### \faIcon{lightbulb} **Idee**
+
+\pause
+
+>1. Vorgänger prüft, ob der Nachfolger das gesuchte Lied ist.
+>2. Falls ja, wird der Nachfolger durch dessen Nachfolger ersetzt und das Objekt zurückgegeben.
+
+```{=latex}
+\only<5>{
+```
+
+### \faIcon{pencil-alt} 1. Arbeitsauftrag  \hfill 10min
+
+Zeichne das Sequenzdiagramm, eines `remove("bar")` Methodenaufrufs.
+
+### \faIcon{desktop} 2. Arbeitsauftrag
+
+Implementiere die **rekursive** Methode `Song remove(String title)`.
+
+:::::{.info}
+Welche 3. Fälle müssen unterschieden werden?
+:::::
+
+```{=latex}
+}
+```
+
+## Sequenzdiagramm: Die Rekursive-Methode `remove(title)`
+
+### In der Liste wird entfernt
+
+\begin{sequencediagram}
+    \newthread{A}{playlist}{}
+    \newinst[1.5]{B}{s1}{}
+    \newinst[1.5]{C}{s2}{}
+    \newinst[1.5]{D}{s3}{}
+    \begin{call}{A}{remove("2")}{B}{s1}
+    \begin{call}{B}{setNext(next.next)}{B}{}
+    \end{call}
+    \end{call}
+\end{sequencediagram}
+
+## Sequenzdiagramm: Die Rekursive-Methode `remove(title)`
+
+### Der Letzte wird entfernt
+
+\begin{sequencediagram}
+    \newthread{A}{playlist}{}
+    \newinst[1.5]{B}{s1}{}
+    \newinst[1.5]{C}{s2}{}
+    \newinst[1.5]{D}{s3}{}
+    \begin{call}{A}{remove("3")}{B}{s2}
+    \begin{call}{B}{remove("3")}{C}{s2}
+    \end{call}
+    \end{call}
+    \begin{call}{A}{setLast(s2)}{A}{}
+    \end{call}
+\end{sequencediagram}
+
+## Implementierung: Die Rekursive-Methode `remove(title)`
+
+::: {.columns}
+:::: {.column width=50%}
+```java
+class Playlist {
+  void remove(String toremove) {
+    if (first == null) // Leere Liste
+      return;
+    // Der Erste ist gesucht
+    if (first.title == toremove)
+      first = first.next;
+
+    Song before = first.remove(toremove);
+    // Der Letzte war gesucht
+    if (last.title == tofind)
+      last = before;
+  }
+}
+```
+::::
+
+:::: {.column width=50%}
+```java
+class Song {
+  Song remove(String toremove) {
+    if (next == null) // Letzter
+      return null;
+
+    if (next.title == toremove) {
+      next = next.next;
+      return this;
+    }
+
+    return next.remove(toremove);
+  }
+}
+```
+::::
+:::
+
+## \faIcon{desktop} Arbeitsauftrag: Imperative Liste
+
+Implementiere die rekursiven Methoden:
+
+* `getLength`
+* `find`
+* `remove`
+
+mit Hilfe einer `for`{.java}-Schleife.
+
+```java
+for (Song cur = first; cur != null; cur = cur.next) {
+  ...
+}
+```
+