Implementări ale interfeței List

"Dacă crezi că am terminat cu toți interfața Listă, atunci te înșeli. Abia am început. Permiteți-mi să vă spun despre colecțiile LinkedList și ArrayList ."

„Voi începe cu colecția ArrayList”.

„Iată cum arată diagrama de moștenire a acestei colecții:”

„Interfețele sunt verzi”.

„Clasele de abstracte sunt violete”.

„Clasele obișnuite sunt roșii”.

„Liniile continue reprezintă moștenirea, iar liniile întrerupte reprezintă implementările de interfață.”

„Aceasta este cea mai simplă colecție. În cadrul unui ArrayList , elementele sunt stocate într-o matrice simplă.”

„Avantajul principal al acestei colecții față de o matrice este capacitatea sa de a se extinde, adică capacitatea de a-și crește lungimea după cum este necesar”.

„Dacă matricea rămâne fără spațiu, atunci o a doua matrice mai mare este creată și toate elementele din prima matrice sunt copiate în ea. Apoi a doua matrice ia locul primei, iar prima este eliminată (va fi distrus de gunoiul)."

„Cât de mult devine matricea?”

„Lungimea noii matrice este calculată ca (3*n)/2+1, unde n este lungimea vechii matrice. Cu alte cuvinte, dacă vechea matrice avea 100 de elemente, atunci cea nouă va fi 300/2+1 = 151."

„Când adăugați un element la mijlocul unui ArrayList, toate elementele din dreapta locului unde va fi inserat noul element sunt copiate 1 poziție la dreapta, iar apoi noul element este adăugat în celula goală.”

„Când eliminați un element din mijloc, toate elementele din dreapta acelui element sunt copiate cu o poziție la stânga.”

„Vrei să spui că ArrayList se devine mai lung atunci când îi adaugi elemente și că se scurtează atunci când elimini elemente?”

„Nu, matricea din interiorul unui ArrayList nu se scurtează niciodată de la sine; totuși, puteți forța un ArrayList să-și micșoreze matricea internă la cea mai mică dimensiune posibilă apelând metoda trimToSize () ” .

„Și, bineînțeles, vă voi spune despre LinkedList”.

„Iată cum arată diagrama ei de moștenire:”

„Interfețele sunt verzi”.

„Clasele de abstracte sunt violete”.

„Clasele obișnuite sunt roșii”.

„Liniile continue reprezintă moștenirea, iar liniile întrerupte reprezintă implementările de interfață.”

„După cum știți deja, LinkedList stochează elemente ca o listă legată.”

„Aud asta tot timpul, dar ai putea să-mi spui ce este?”

"Sigur. "Este simplu."

„O listă legată constă din elemente care a) stochează date și b) stochează referințe la elementele următoare și anterioare.”

„Așa ar arăta clasa pentru un astfel de element dacă ar stoca șiruri de caractere:”

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

„Și dacă folosim o declarație de tip generic, atunci ar arăta cam așa:”

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

"Are sens."

„Pentru a înțelege mai bine, să scriem cod în care adăugăm 10 elemente la o listă dublu legată:”

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

„Imaginați-vă că avem 10 elemente în listă. Iată cum să inserați un element în mijloc:”

„Legăturile care s-au schimbat sunt evidențiate în roșu aprins . Ele indică acum noul element.”

„Noile legături sunt evidențiate în mov strălucitor . Sunt legăturile noului element cu vecinii săi.”

„Și acum ca cod:”

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

— Mulțumesc, Ellie. Cu siguranță am învățat o mulțime de lucruri noi despre liste.