Implementacje interfejsu List

„Jeśli myślisz, że skończyliśmy z interfejsem List, to się mylisz. Dopiero zaczynamy. Pozwól, że opowiem ci o kolekcjach LinkedList i ArrayList ”.

„Zacznę od kolekcji ArrayList”.

„Oto jak wygląda diagram dziedziczenia tej kolekcji:”

„Interfejsy są zielone”.

„Klasy abstrakcyjne są fioletowe”.

„Zwykłe klasy są czerwone”.

„Linie ciągłe reprezentują dziedziczenie, a linie przerywane reprezentują implementacje interfejsu”.

„To jest najprostsza kolekcja. Wewnątrz tablicy ArrayList elementy są przechowywane w prostej tablicy”.

„Główną przewagą tej kolekcji nad macierzą jest jej zdolność do rozszerzania się, tj. zwiększania jej długości w razie potrzeby”.

„Jeśli w tablicy zabraknie miejsca, tworzona jest druga większa tablica i wszystkie elementy z pierwszej tablicy są do niej kopiowane. Następnie druga tablica zajmuje miejsce pierwszej, a pierwsza jest odrzucana (zostanie zniszczone przez śmieciarza).”

„O ile większa staje się tablica?”

„Długość nowej tablicy jest obliczana jako (3*n)/2+1, gdzie n jest długością starej tablicy. Innymi słowy, jeśli stara tablica miała 100 elementów, nowa tablica będzie miała długość 300/2+1 = 151."

„Podczas dodawania elementu na środku tablicy ArrayList wszystkie elementy na prawo od miejsca, w którym zostanie wstawiony nowy element, są kopiowane o 1 pozycję w prawo, a następnie nowy element jest dodawany do pustej komórki”.

„Podczas usuwania elementu ze środka wszystkie elementy na prawo od tego elementu są kopiowane o 1 pozycję w lewo”.

„Czy chcesz powiedzieć, że ArrayList wydłuża się, gdy dodajesz do niej elementy, i że skraca się, gdy usuwasz elementy?”

„Nie, tablica wewnątrz tablicy ArrayList nigdy sama się nie skraca; można jednak zmusić tablicę ArrayList do zmniejszenia jej wewnętrznej tablicy do najmniejszego możliwego rozmiaru, wywołując metodę trimToSize() ” .

„I oczywiście opowiem ci o LinkedList”.

„Oto, jak wygląda jego diagram dziedziczenia:”

„Interfejsy są zielone”.

„Klasy abstrakcyjne są fioletowe”.

„Zwykłe klasy są czerwone”.

„Linie ciągłe reprezentują dziedziczenie, a linie przerywane reprezentują implementacje interfejsu”.

„Jak już wiesz, LinkedList przechowuje elementy jako połączoną listę”.

„Słyszę to cały czas, ale czy możesz mi powiedzieć, co to jest?”

"Jasne. "To proste."

„Lista połączona składa się z elementów , które a) przechowują dane oraz b) przechowują odniesienia do następnych i poprzednich elementów”.

„Tak wyglądałaby klasa takiego elementu, gdyby przechowywała ciągi znaków:”

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

„A jeśli użyjemy deklaracji typu ogólnego, wyglądałoby to mniej więcej tak:”

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

"Ma sens."

„Aby to lepiej zrozumieć, napiszmy kod, w którym dodajemy 10 elementów do podwójnie połączonej listy:”

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

„Wyobraź sobie, że mamy 10 elementów na liście. Oto jak wstawić element na środek:”

„Łącza, które uległy zmianie, są podświetlone na jaskrawoczerwono . Teraz wskazują nowy element”.

„Nowe łącza są podświetlone na jasnofioletowo . Są to łącza nowego elementu do jego sąsiadów”.

„A teraz jako 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;

„Dziękuję, Ellie. Zdecydowanie dowiedziałam się wielu nowych rzeczy o listach”.