Implementeringer av List-grensesnittet

"Hvis du tror at vi alle er ferdige med List-grensesnittet, tar du feil. Vi har akkurat kommet i gang. La meg fortelle deg om LinkedList- og ArrayList - samlingene."

"Jeg begynner med ArrayList-samlingen."

"Slik ser denne samlingens arvediagram ut:"

"Grensesnitt er grønne."

"Abstrakte klasser er lilla."

"Vanlige klasser er røde."

"Heltrukkede linjer representerer arv, og stiplede linjer representerer grensesnittimplementeringer."

"Dette er den enkleste samlingen. Inne i en ArrayList er elementer lagret i en enkel matrise."

"Denne samlingens primære fordel fremfor en array er dens evne til å utvide seg, dvs. dens evne til å øke lengden etter behov."

"Hvis matrisen går tom for plass, opprettes en andre større matrise og alle elementene fra den første matrisen kopieres til den. Deretter tar den andre matrisen plassen til den første, og den første blir forkastet (det vil bli ødelagt av søppelsamleren)."

"Hvor mye større blir matrisen?"

"Den nye matrisens lengde beregnes som (3*n)/2+1, der n er den gamle matrisens lengde. Med andre ord, hvis den gamle matrisen var 100 elementer lang, vil den nye være 300/2+1 = 151."

"Når du legger til et element i midten av en ArrayList, blir alle elementene til høyre for der det nye elementet skal settes inn kopiert 1 posisjon til høyre, og deretter legges det nye elementet til den tomme cellen."

"Når du fjerner et element fra midten, kopieres alle elementene til høyre for det elementet 1 posisjon til venstre."

"Sier du at ArrayList blir lengre når du legger til elementer i den, og at den blir kortere når du fjerner elementer?"

"Nei, matrisen inne i en ArrayList gjør seg aldri kortere av seg selv, men du kan tvinge en ArrayList til å krympe den interne matrisen til den minste mulige størrelsen ved å kalle trimToSize ()-metoden . "

"Og selvfølgelig skal jeg fortelle deg om LinkedList."

"Her er hvordan arvediagrammet ser ut:"

"Grensesnitt er grønne."

"Abstrakte klasser er lilla."

"Vanlige klasser er røde."

"Heltrukkede linjer representerer arv, og stiplede linjer representerer grensesnittimplementeringer."

"Som du allerede vet, lagrer LinkedList elementer som en koblet liste."

"Jeg hører det hele tiden, men kan du fortelle meg hva det er?"

"Jada. "Det er enkelt."

"En koblet liste består av elementer som a) lagrer data og b) lagrer referanser til neste og forrige elementer."

"Slik ville klassen for et slikt element sett ut hvis den lagret Strings:"

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

"Og hvis vi bruker en generisk type erklæring, vil det se omtrent slik ut:"

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

"Gir mening."

"For å forstå det bedre, la oss skrive kode der vi legger til 10 elementer til en dobbeltlenket liste:"

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

"Tenk deg at vi har 10 elementer i listen. Slik setter du inn et element i midten:"

"Lenkene som har endret seg er uthevet knallrødt . De peker nå til det nye elementet."

"Nye lenker er fremhevet i lys lilla . De er det nye elementets lenker til naboene."

"Og nå som kode:"

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

"Takk, Ellie. Jeg har definitivt lært mye nytt om lister."