A Lista felület megvalósításai

"Ha úgy gondolja, hogy mindannyian elkészültünk a List felülettel, akkor téved. Még csak most kezdjük. Hadd meséljek a LinkedList és az ArrayList gyűjteményekről."

– Kezdem az ArrayList gyűjteményével.

"Íme, hogyan néz ki a gyűjtemény öröklődési diagramja:"

"Az interfészek zöldek."

– Az absztrakt osztályok lilák.

– A rendes osztályok pirosak.

"A folytonos vonalak az öröklődést, a szaggatott vonalak pedig az interfész megvalósításait jelentik."

"Ez a legegyszerűbb gyűjtemény. Az ArrayList- en belül az elemek egy egyszerű tömbben vannak tárolva."

"Ennek a gyűjteménynek az elsődleges előnye a tömbökkel szemben, hogy bővíthető, azaz szükség szerint növelheti a hosszát."

"Ha a tömbből kifogy a hely, akkor létrejön egy második nagyobb tömb, és az első tömb összes eleme átmásolódik oda. Ezután a második tömb átveszi az első helyét, és az elsőt eldobják (ez lesz a szemétgyűjtő tönkretette).

– Mennyivel lesz nagyobb a tömb?

"Az új tömb hosszát a következőképpen számítjuk ki: (3*n)/2+1, ahol n a régi tömb hossza. Más szóval, ha a régi tömb 100 elem hosszú volt, akkor az új 300/2+1 lesz. = 151."

"Ha egy ArrayList közepéhez adunk egy elemet, az új elem beszúrásának helyétől jobbra lévő összes elemet 1 pozícióval jobbra másoljuk, majd az új elemet hozzáadjuk az üres cellához."

"Amikor eltávolít egy elemet a közepéről, az elemtől jobbra lévő összes elemet a rendszer 1 pozícióval balra másolja."

"Azt akarja mondani, hogy az ArrayList meghosszabbítja magát, ha elemeket ad hozzá, és rövidebbé teszi magát, ha elemeket távolít el?"

"Nem, az ArrayList belsejében lévő tömb soha nem rövidíti önmagát; azonban rákényszerítheti az ArrayList belső tömbjét a lehető legkisebb méretre a trimToSize () metódus meghívásával."

– És természetesen mesélek a LinkedListről is.

"Íme, hogy néz ki az öröklődési diagramja:"

"Az interfészek zöldek."

– Az absztrakt osztályok lilák.

– A rendes osztályok pirosak.

"A folytonos vonalak az öröklődést, a szaggatott vonalak pedig az interfész megvalósításait jelentik."

"Amint azt már tudja, a LinkedList az elemeket linkelt listaként tárolja."

– Állandóan ezt hallom, de meg tudná mondani, mi az?

– Persze. – Egyszerű.

"A linkelt lista olyan elemekből áll , amelyek a) adatokat tárolnak és b) hivatkozásokat tárolnak a következő és az előző elemekre."

"Így nézne ki egy ilyen elem osztálya , ha stringeket tárolna:"

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

"És ha általános típusdeklarációt használunk, akkor az valahogy így nézne ki:"

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

"Van értelme."

"A jobb megértéshez írjunk kódot, amelyben 10 elemet adunk hozzá egy duplán linkelt listához:

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

"Képzeld el, hogy 10 elemünk van a listában. Így illeszthetsz be egy elemet a közepébe:"

"A megváltozott hivatkozások élénkpirossal vannak kiemelve . Most az új elemre mutatnak."

"Az új linkek élénklilával vannak kiemelve . Ezek az új elem linkjei a szomszédokhoz."

"És most kódként:"

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

– Köszönöm, Ellie. Határozottan sok új dolgot tanultam a listákkal kapcsolatban.