\documentclass{bschlangaul-aufgabe}
\bLadePakete{java,grafik}

\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 2},
  Thematik = {DoubleLinkedList},
  Referenz = 66115-2021-F.T2-TA2-A2,
  RelativerPfad = Examen/66115/2021/03/Thema-2/Teilaufgabe-2/Aufgabe-2.tex,
  ZitatSchluessel = examen:66115:2021:03,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Doppelt-verkettete Liste},
  EinzelpruefungsNr = 66115,
  Jahr = 2021,
  Monat = 03,
  ThemaNr = 2,
  TeilaufgabeNr = 2,
  AufgabeNr = 2,
}

\let\j=\bJavaCode

\usetikzlibrary{calc,shapes.multipart,chains,arrows,positioning}

{Gegeben sei die folgende Java-Implementierung einer doppelt-verketteten
Liste.}
\index{Doppelt-verkettete Liste}
\footcite{examen:66115:2021:03}

\begin{bJavaAngabe}
class DoubleLinkedList {
  private Item head;

  public DoubleLinkedList() {
    head = null;
  }

  public Item append(Object val) {
    if (head == null) {
      head = new Item(val, null, null);
      head.prev = head;
      head.next = head;
    } else {
      Item item = new Item(val, head.prev, head);
      head.prev.next = item;
      head.prev = item;
    }
    return head.prev;
  }

  public Item search(Object val) {
    // ...
  }

  public void delete(Object val) {
    // ...
  }

  class Item {
    private Object val;
    private Item prev;
    private Item next;

    public Item(Object val, Item prev, Item next) {
      this.val = val;
      this.prev = prev;
      this.next = next;
    }
  }
}
\end{bJavaAngabe}

\begin{enumerate}

%%
% a)
%%

\item Skizzieren Sie den Zustand der Datenstruktur nach Aufruf der
folgenden Befehlssequenz. Um Variablen mit Zeigern auf Objekte
darzustellen, können Sie mit dem Variablennamen beschriftete Pfeile
verwenden.

\begin{bJavaAngabe}
DoubleLinkedList list = new DoubleLinkedList();
list.append("a");
list.append("b");
list.append("c");
\end{bJavaAngabe}

\begin{bAntwort}
\begin{tikzpicture}[
  list/.style={
    rectangle split,
    rectangle split parts=3,
    draw,
    rectangle split horizontal,
    minimum size=18pt,
    inner sep=5pt,
    text=black,
  },
  ->,
  start chain
]

  \node[list,on chain] (A) {\nodepart{second} a};
  \node[list,on chain] (B) {\nodepart{second} b};
  \node[list,on chain] (C) {\nodepart{second} c};

  \node (head) [left= of A] {head};

  \path[*->] let \p1 = (A.three), \p2 = (A.center) in (\x1,\y2) edge [bend left] ($(B.one)+(0,0.2)$);
  \path[*->] let \p1 = (B.three), \p2 = (B.center) in (\x1,\y2) edge [bend left] ($(C.one)+(0,0.2)$);

  \draw[*->] (head) -- ($(A.one)+(0.2,0.1)$);
  \path[*->] ($(B.one)+(0.1,0.1)$) edge [bend left] ($(A.three)+(0,-0.05)$);
  \path[*->] ($(C.one)+(0.1,0.1)$) edge [bend left] ($(B.three)+(0,-0.05)$);

  \path[*->] ($(C.three)+(0.1,0.1)$) edge [bend left] ($(A.one)+(0,-0.05)$);
  \path[*->] ($(A.one)+(0.1,0.2)$) edge [bend left] ($(C.three)+(0,0.2)$);

\end{tikzpicture}
\end{bAntwort}

%%
%
%%

\item Implementieren Sie in der Klasse \j{DoubleLinkedList} die Methode
\j{search}, die zu einem gegebenen Wert das Item der Liste mit dem
entsprechenden Wert, oder \j{null} falls der Wert nicht in der Liste
enthalten ist, zurückgibt.

\begin{bAntwort}
\bJavaExamen[firstline=23,lastline=35]{66115}{2021}{03}{DoubleLinkedList}
\end{bAntwort}

%%
%
%%

\item Implementieren Sie in der Klasse \j{DoubleLinkedList} die Methode
\j{delete}, die das erste Vorkommen eines Wertes aus der Liste entfernt.
Ist der Wert nicht in der Liste enthalten, terminiert die Methode
„stillschweigend“, \dh ohne Änderung der Liste und ohne Fehlermeldung.
Sie dürfen die Methode \j{search} aus Teilaufgabe b) verwenden, auch
wenn Sie sie nicht implementiert haben.

\begin{bAntwort}
\bJavaExamen[firstline=37,lastline=50]{66115}{2021}{03}{DoubleLinkedList}
\end{bAntwort}

%%
%
%%

\item Beschreiben Sie die notwendigen Änderungen an der Datenstruktur
und an den bisherigen Implementierungen, um eine Methode \j{size}, die
die Anzahl der enthaltenen Items zurück gibt, mit Laufzeit
$\mathcal{O}(1)$ zu realisieren.

\begin{bAntwort}
In der Klasse wird ein Zähler eingefügt, der bei jedem Aufruf der
Methode \j{append} um eins nach oben gezählt wird und bei jedem
erfolgreichen Löschen in der \j{delete}-Methode um eins nach unten
gezählt wird. Mit \j{return} kann der Zählerstand in $\mathcal{O}(1)$
ausgegeben werden. Dazu müsste ein Getter zum Ausgeben implementiert
werden. Die Datenstruktur bleibt unverändert.
\end{bAntwort}

\end{enumerate}
\end{document}