Implementierungen der List-Schnittstelle

„Wenn Sie denken, dass wir alle mit der List-Schnittstelle fertig sind, dann irren Sie sich. Wir fangen gerade erst an. Lassen Sie mich Ihnen etwas über die LinkedList- und ArrayList -Sammlungen erzählen.“

„Ich beginne mit der ArrayList-Sammlung.“

„So sieht das Vererbungsdiagramm dieser Sammlung aus:“

„Schnittstellen sind grün.“

„Abstrakte Klassen sind lila.“

„Normale Klassen sind rot.“

„Durchgezogene Linien stehen für Vererbung und gestrichelte Linien für Schnittstellenimplementierungen.“

„Dies ist die einfachste Sammlung. Innerhalb einer ArrayList werden Elemente in einem einfachen Array gespeichert.“

„Der Hauptvorteil dieser Sammlung gegenüber einem Array ist ihre Erweiterbarkeit, also ihre Fähigkeit, ihre Länge nach Bedarf zu vergrößern.“

„Wenn das Array nicht mehr genügend Platz hat, wird ein zweites größeres Array erstellt und alle Elemente aus dem ersten Array werden dorthin kopiert. Dann nimmt das zweite Array den Platz des ersten ein und das erste wird verworfen (das wird es auch sein). vom Garbage Collector zerstört).

„Wie viel größer wird das Array?“

„Die Länge des neuen Arrays wird als (3*n)/2+1 berechnet, wobei n die Länge des alten Arrays ist. Mit anderen Worten: Wenn das alte Array 100 Elemente lang war, dann ist das neue 300/2+1.“ = 151.“

„Wenn Sie ein Element in der Mitte einer ArrayList hinzufügen, werden alle Elemente rechts von der Stelle, an der das neue Element eingefügt wird, um eine Position nach rechts kopiert, und dann wird das neue Element der leeren Zelle hinzugefügt.“

„Wenn Sie ein Element aus der Mitte entfernen, werden alle Elemente rechts von diesem Element um eine Position nach links kopiert.“

„Wollen Sie damit sagen, dass die ArrayList länger wird, wenn Sie Elemente hinzufügen, und dass sie kürzer wird, wenn Sie Elemente entfernen?“

„Nein, das Array innerhalb einer ArrayList verkürzt sich niemals von selbst; Sie können jedoch eine ArrayList zwingen, ihr internes Array auf die kleinstmögliche Größe zu verkleinern, indem Sie die Methode trimToSize() aufrufen . “

„Und natürlich erzähle ich Ihnen von LinkedList.“

„So sieht das Vererbungsdiagramm aus:“

„Schnittstellen sind grün.“

„Abstrakte Klassen sind lila.“

„Normale Klassen sind rot.“

„Durchgezogene Linien stehen für Vererbung und gestrichelte Linien für Schnittstellenimplementierungen.“

„Wie Sie bereits wissen, speichert LinkedList Elemente als verknüpfte Liste.“

„Das höre ich ständig, aber könnten Sie mir sagen, was es ist?“

„Sicher. „Es ist einfach.“

„Eine verknüpfte Liste besteht aus Elementen , die a) Daten speichern und b) Verweise auf das nächste und vorherige Element speichern.“

„So würde die Klasse für ein solches Element aussehen, wenn es Strings speichern würde:“

class LinkedListElement
{
String data;
LinkedListElement next;
LinkedListElement previous;
}

„Und wenn wir eine generische Typdeklaration verwenden würden, dann würde das etwa so aussehen:“

class LinkedListElement<T>
{
 T data;
 LinkedListElement<T> next;
 LinkedListElement<T> previous;
}

"Macht Sinn."

„Um es besser zu verstehen, schreiben wir Code, in dem wir 10 Elemente zu einer doppelt verknüpften Liste hinzufügen:“

public static void main(String[] args)
{
 LinkedListElement<Integer> tail; // The tail (very last element) of the list

 for(int i = 0; i < 10; i++)
 {
  LinkedListElement<Integer> element = new LinkedListElement<Integer>();
  element.data = i;

  if (tail == null) // If the tail doesn't exist, then make our element the last element
  {
   tail = element;
  }
  else // if there is a tail, add the element
  {
   tail.next = element; // Set the next field on the tail element
   element.previous = tail; // Add a reference to the tail to the new element
   tail = element; // Make the new element the tail
  }
 }
}

„Stellen Sie sich vor, wir haben 10 Elemente in der Liste. So fügen Sie ein Element in die Mitte ein:“

„Die geänderten Links werden leuchtend rot hervorgehoben . Sie verweisen nun auf das neue Element.“

„Neue Links werden hellviolett hervorgehoben . Sie sind die Links des neuen Elements zu seinen Nachbarn.“

„Und jetzt als Code:“

// This field stores the element that is the head of the list
LinkedListElement<Integer> head = …

// Get the 4th element (counting from zero)
LinkedListElement<Integer> element4 = head.next.next.next.next;
// Get the 5th element
LinkedListElement<Integer> element5 = element4.next;

// Create the new element that we will insert
LinkedListElement<Integer> newElement = new LinkedListElement<Integer>();
newElement.data = -18;

// Replace the references in the element on the left
newElement.previous = element4;
element4.next = newElement;

// Replace the references in the element on the right
newElement.next = element5;
element5.previous = newElement;

„Danke, Ellie. Ich habe definitiv viel Neues über Listen gelernt.“