List

• Listen


  gegeben: eine Reihe von Objekten einer bestimmten Klasse oder Basisdatentyp, die wir nicht verändern können -> Object

  
• einfache Liste Bestandteile


  - Element head, Element tail

  - beide in Konstruktion auf null gesetzt

  -isEmpty

  - getHead

  - getTail

  - prepend (vorne einfügen)

  -append (hinten einfügen)

  - removeHead

  
• neues Objekt hinter aktuellen einfügen

  
• Objekt hinter aktuellem löschen

  
• Linked-Lists


  Eine einfach verkettete Liste besteht aus einer Sequenz von Knoten.

  
  

  Jeder Knoten auch Node genannt besitzt ein Element (den Inhalt) und einen Link zum nächsten Knoten.

  
• Singly-Linked-List

  Eine einfach verkette Liste (Singly-Linked-List)besteht aus einer Sammlung von Knoten.

  
  

  Die Reiehenfolge ist bestimmt durhc Nachfolge / nächster Knoten.

  
  

  Der Kopf der Liste wird dabei speziell gespeichert. Der Kopf wird als Einstieg benötigt.

  
• Singly-Linked-List: Einfügen eines Knotens (Kopf, head)

  1. Verketten des neuen Knoten mit dem alten Kopf.

  2. "head" updaten: Zeigt nun auf den neuen Knoten.

  
  

  Der neue Knoten wird vor den alten Kopf (head) gestellt. Dieser wird nun mit dem alten Kopf (head) verbunden. Nach der Verbindung muss nun noch der Kopf aktualisiert werden.

  
• Singly-Linked-List: Einfügen eines Knotens (tail)


  1. Den neuen Knoten auf nullzeigen lassen (am Ende)

  2. Verketten des früheren Endknoten mit dem neuen Knoten.

  3. tail" updaten: Zeigt nun auf den neuen Knoten.

  
  

  Es wird ein neuer Knoten hinter dem Tail gebaut. Dieser wird jedoch noch nicht verknüpft. Der alte Tail zeigt immer noch auf einen Null Knoten. Nun wird der neue Knoten (Tail) verknüpft und der Tail aktualisiert.

  
• Singly-Linked-List: Entfernen eines Knotens (Kopf, head)

  1. Überprüfung auf leere Liste.

  2. "head" updaten: Zeigt nun auf den 2. Knoten.

  3. Verbindung des alten "head"-Knotens mit der Liste löschen.

  
  

  Bevor der aktuelle Head entfernt werden kann muss der Head auf den zweit vordersten Knoten aktualisiert werden. Nach der aktualisierung kann der alte Head entfernt werden.

  
• Lineare Liste


  Einfügen und löschen unabhängig der Reihenfolge

  -> kann beliebig viele Objekte verwalten
• append


  einfügen nach last

  (Liste)
• insert


  einfügen nach current

  (Liste)
• remove


  current entfernen
• setCurrent(name)

  Auswahl eines neuen Elements

  -> name => neuer current
• hasCurrent

  Ausgabe des aktuellen Elements
• Vorteile


  dynamische Datenstruktur

  einfaches Einfügen und Löschen