Implementeringer af List-grænsefladen

"Hvis du tror, ​​at vi alle er færdige med List-grænsefladen, så tager du fejl. Vi er lige begyndt. Lad mig fortælle dig om LinkedList- og ArrayList - samlingerne."

"Jeg starter med ArrayList-samlingen."

"Sådan ser denne samlings arvediagram ud:"

"Grænseflader er grønne."

"Abstrakte klasser er lilla."

"Almindelige klasser er røde."

"Optrukne linjer repræsenterer arv, og stiplede linjer repræsenterer grænsefladeimplementeringer."

"Dette er den enkleste samling. Inde i en ArrayList er elementer gemt i et simpelt array."

"Denne samlings primære fordel i forhold til et array er dens evne til at udvide, dvs. dens evne til at øge dens længde efter behov."

"Hvis arrayet løber tør for plads, oprettes et andet større array, og alle elementerne fra det første array kopieres til det. Derefter overtager det andet array stedet for det første, og det første kasseres (det bliver ødelagt af skraldemanden)."

"Hvor meget større bliver arrayet?"

"Det nye arrays længde beregnes som (3*n)/2+1, hvor n er det gamle arrays længde. Med andre ord, hvis det gamle array var 100 elementer langt, så vil det nye være 300/2+1 = 151."

"Når du tilføjer et element til midten af ​​en ArrayList, kopieres alle elementer til højre for, hvor det nye element vil blive indsat 1 position til højre, og derefter tilføjes det nye element til den tomme celle."

"Når du fjerner et element fra midten, kopieres alle elementer til højre for det element 1 position til venstre."

"Siger du, at ArrayList bliver længere, når du tilføjer elementer til den, og at den gør sig selv kortere, når du fjerner elementer?"

"Nej, arrayet inde i en ArrayList gør sig aldrig kortere af sig selv, men du kan tvinge en ArrayList til at formindske dens interne array til den mindst mulige størrelse ved at kalde trimToSize () metoden . "

"Og selvfølgelig vil jeg fortælle dig om LinkedList."

"Sådan ser dets arvediagram ud:"

"Grænseflader er grønne."

"Abstrakte klasser er lilla."

"Almindelige klasser er røde."

"Optrukne linjer repræsenterer arv, og stiplede linjer repræsenterer grænsefladeimplementeringer."

"Som du allerede ved, gemmer LinkedList elementer som en linket liste."

"Jeg hører det hele tiden, men kan du fortælle mig, hvad det er?"

"Selvfølgelig. "Det er enkelt."

"En sammenkædet liste består af elementer , der a) gemmer data og b) gemmer referencer til de næste og forrige elementer."

"Sådan ville klassen for et sådant element se ud, hvis den lagrede Strings:"

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

"Og hvis vi bruger en generisk typedeklaration, så ville den se sådan ud:"

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

"Giver mening."

"For at forstå det bedre, lad os skrive kode, hvor vi tilføjer 10 elementer til en dobbelt-linket 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
  }
 }
}

"Forestil dig, at vi har 10 elementer på listen. Sådan indsætter du et element i midten:"

"De links, der er ændret, er fremhævet lyse rødt . De peger nu på det nye element."

"Nye links er fremhævet lyse lilla . De er det nye elements links til dets naboer."

"Og nu 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;

"Tak, Ellie. Jeg har bestemt lært en masse nye ting om lister."