Implementaties van de Lijst-interface

"Als je denkt dat we allemaal klaar zijn met de List-interface, dan heb je het mis. We zijn nog maar net begonnen. Laat me je vertellen over de LinkedList- en ArrayList -collecties."

"Ik zal beginnen met de ArrayList-collectie."

"Zo ziet het overervingsdiagram van deze collectie eruit:"

"Interfaces zijn groen."

"Abstracte lessen zijn paars."

"Gewone lessen zijn rood."

"Ononderbroken lijnen vertegenwoordigen overerving en stippellijnen vertegenwoordigen interface-implementaties."

"Dit is de eenvoudigste verzameling. Binnen een ArrayList worden elementen opgeslagen in een eenvoudige array."

"Het belangrijkste voordeel van deze verzameling ten opzichte van een array is het vermogen om uit te breiden, dat wil zeggen het vermogen om de lengte naar behoefte te vergroten."

"Als de array geen ruimte meer heeft, wordt een tweede grotere array gemaakt en worden alle elementen van de eerste array ernaar gekopieerd. Vervolgens neemt de tweede array de plaats in van de eerste en wordt de eerste weggegooid (deze wordt vernietigd door de vuilnisman)."

"Hoeveel groter wordt de array?"

"De lengte van de nieuwe array wordt berekend als (3*n)/2+1, waarbij n de lengte van de oude array is. Met andere woorden, als de oude array 100 elementen lang was, dan is de nieuwe 300/2+1 = 151."

"Bij het toevoegen van een element aan het midden van een ArrayList, worden alle elementen rechts van waar het nieuwe element wordt ingevoegd 1 positie naar rechts gekopieerd en vervolgens wordt het nieuwe element toegevoegd aan de lege cel."

"Bij het verwijderen van een element uit het midden, worden alle elementen rechts van dat element 1 positie naar links gekopieerd."

"Bedoel je dat de ArrayList zichzelf langer maakt als je er elementen aan toevoegt, en dat hij zichzelf korter maakt als je elementen verwijdert?"

"Nee, de array in een ArrayList maakt zichzelf nooit korter; u kunt een ArrayList echter dwingen zijn interne array tot de kleinst mogelijke grootte te verkleinen door de methode trimToSize () aan te roepen."

"En natuurlijk zal ik je vertellen over LinkedList."

"Dit is hoe het overervingsdiagram eruit ziet:"

"Interfaces zijn groen."

"Abstracte lessen zijn paars."

"Gewone lessen zijn rood."

"Ononderbroken lijnen vertegenwoordigen overerving en stippellijnen vertegenwoordigen interface-implementaties."

"Zoals u al weet, slaat LinkedList elementen op als een gekoppelde lijst."

"Dat hoor ik de hele tijd, maar kun je me vertellen wat het is?"

"Natuurlijk. "Het is simpel."

"Een gekoppelde lijst bestaat uit elementen die a) gegevens opslaan en b) verwijzingen naar de volgende en vorige elementen opslaan."

"Dit is hoe de klasse voor zo'n element eruit zou zien als het Strings zou opslaan:"

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

"En als we een generieke typedeclaratie gebruiken, dan zou het er ongeveer zo uitzien:"

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

"Klinkt logisch."

"Om het beter te begrijpen, laten we code schrijven waarin we 10 elementen toevoegen aan een dubbel gekoppelde lijst:"

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

"Stel je voor dat we 10 elementen in de lijst hebben. Zo kun je een element in het midden invoegen:"

"De links die gewijzigd zijn, zijn knalrood gemarkeerd . Ze verwijzen nu naar het nieuwe element."

"Nieuwe links zijn helder paars gemarkeerd . Het zijn de links van het nieuwe element naar zijn buren."

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

'Dank je, Ellie. Ik heb zeker veel nieuwe dingen over lijsten geleerd.'