Implementeringar av List-gränssnittet

"Om du tror att vi alla är klara med List-gränssnittet, så har du fel. Vi har precis börjat. Låt mig berätta om LinkedList- och ArrayList - samlingarna."

"Jag börjar med ArrayList-samlingen."

"Så här ser den här samlingens arvsdiagram ut:"

"Gränssnitt är gröna."

"Abstrakta klasser är lila."

"Vanliga klasser är röda."

"Heldragna linjer representerar arv, och streckade linjer representerar gränssnittsimplementeringar."

"Detta är den enklaste samlingen. Inuti en ArrayList lagras element i en enkel array."

"Den här samlingens främsta fördel gentemot en array är dess förmåga att expandera, dvs dess förmåga att öka dess längd efter behov."

"Om arrayen får slut på utrymme skapas en andra större array och alla element från den första arrayen kopieras till den. Sedan tar den andra arrayen platsen för den första och den första kasseras (det kommer att bli förstörts av sophämtaren)."

"Hur mycket större blir arrayen?"

"Den nya matrisens längd beräknas som (3*n)/2+1, där n är den gamla matrisens längd. Med andra ord, om den gamla matrisen var 100 element lång, så blir den nya 300/2+1 = 151."

"När du lägger till ett element i mitten av en ArrayList, kopieras alla element till höger om där det nya elementet kommer att infogas 1 position till höger, och sedan läggs det nya elementet till i den tomma cellen."

"När du tar bort ett element från mitten, kopieras alla element till höger om det elementet 1 position till vänster."

"Säger du att ArrayList blir längre när du lägger till element i den, och att den blir kortare när du tar bort element?"

"Nej, arrayen inuti en ArrayList gör sig aldrig kortare av sig själv, men du kan tvinga en ArrayList att krympa sin interna array till minsta möjliga storlek genom att anropa metoden trimToSize () . "

"Och, naturligtvis, jag ska berätta om LinkedList."

"Så här ser dess arvsdiagram ut:"

"Gränssnitt är gröna."

"Abstrakta klasser är lila."

"Vanliga klasser är röda."

"Heldragna linjer representerar arv, och streckade linjer representerar gränssnittsimplementeringar."

"Som du redan vet lagrar LinkedList element som en länkad lista."

"Jag hör det hela tiden, men kan du berätta för mig vad det är?"

"Visst. "Det är enkelt."

"En länkad lista består av element som a) lagrar data och b) lagrar referenser till nästa och föregående element."

"Så här skulle klassen för ett sådant element se ut om den lagrade Strings:"

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

"Och om vi använder en generisk typdeklaration, skulle det se ut ungefär så här:"

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

"Är vettigt."

"För att förstå det bättre, låt oss skriva kod där vi lägger till 10 element till en dubbellänkad lista:"

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
  }
 }
}

"Föreställ dig att vi har 10 element i listan. Så här infogar du ett element i mitten:"

"Länkarna som har ändrats är klarröda. De pekar nu på det nya elementet."

"Nya länkar markeras ljust lila . De är det nya elementets länkar till dess grannar."

"Och nu som kod:"

// 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;

"Tack, Ellie. Jag har definitivt lärt mig många nya saker om listor."