Mga pagpapatupad ng interface ng Listahan

"Kung sa tingin mo ay tapos na tayong lahat sa List interface, nagkakamali ka. Nagsisimula pa lang tayo. Hayaan mong sabihin ko sa iyo ang tungkol sa LinkedList at ArrayList na mga koleksyon."

"Magsisimula ako sa koleksyon ng ArrayList."

"Narito ang hitsura ng inheritance diagram ng koleksyon na ito:"

"Ang mga interface ay berde."

"Ang mga abstract na klase ay lila."

"Ang mga ordinaryong klase ay pula."

"Ang mga solidong linya ay kumakatawan sa mana, at ang mga putol-putol na linya ay kumakatawan sa mga pagpapatupad ng interface."

"Ito ang pinakasimpleng koleksyon. Sa loob ng ArrayList , ang mga elemento ay nakaimbak sa isang simpleng array."

"Ang pangunahing bentahe ng koleksyon na ito sa isang array ay ang kakayahang lumawak, ibig sabihin, ang kakayahang taasan ang haba nito kung kinakailangan."

"Kung ang array ay naubusan ng espasyo, pagkatapos ay isang pangalawang mas malaking array ay nilikha at ang lahat ng mga elemento mula sa unang array ay kinopya dito. Pagkatapos ang pangalawang array ay pumapalit sa una, at ang una ay itatapon (ito ay sinira ng basurero).

"Gaano kalaki ang nakukuha ng array?"

"Ang haba ng bagong array ay kinakalkula bilang (3*n)/2+1, kung saan ang n ay ang haba ng lumang array. Sa madaling salita, kung ang lumang array ay 100 elemento ang haba, ang bago ay magiging 300/2+1 = 151."

"Kapag nagdadagdag ng elemento sa gitna ng ArrayList, lahat ng elemento sa kanan kung saan ilalagay ang bagong elemento ay kinokopya ng 1 posisyon sa kanan, at pagkatapos ay idaragdag ang bagong elemento sa walang laman na cell."

"Kapag nag-aalis ng elemento mula sa gitna, lahat ng elemento sa kanan ng elementong iyon ay kinokopya ng 1 posisyon sa kaliwa."

"Sinasabi mo ba na ang ArrayList ay nagpapahaba ng sarili kapag nagdagdag ka ng mga elemento dito, at na ginagawang mas maikli ang sarili kapag nag-alis ka ng mga elemento?"

"Hindi, ang array sa loob ng ArrayList ay hindi kailanman ginagawang mas maikli ang sarili nito; gayunpaman, maaari mong pilitin ang isang ArrayList na paliitin ang panloob na array nito sa pinakamaliit na posibleng laki sa pamamagitan ng pagtawag sa trimToSize () na paraan . "

"At, siyempre, sasabihin ko sa iyo ang tungkol sa LinkList."

"Narito ang hitsura ng inheritance diagram nito:"

"Ang mga interface ay berde."

"Ang mga abstract na klase ay lila."

"Ang mga ordinaryong klase ay pula."

"Ang mga solidong linya ay kumakatawan sa mana, at ang mga putol-putol na linya ay kumakatawan sa mga pagpapatupad ng interface."

"Tulad ng alam mo na, iniimbak ng LinkList ang mga elemento bilang isang naka-link na listahan."

"Naririnig ko iyon sa lahat ng oras, ngunit maaari mo bang sabihin sa akin kung ano ito?"

"Oo naman. "Simple lang."

"Ang isang naka-link na listahan ay binubuo ng mga elemento na a) nag-iimbak ng data at b) nag-iimbak ng mga sanggunian sa susunod at nakaraang mga elemento."

"Ito ang magiging hitsura ng klase para sa naturang elemento kung nag-imbak ito ng Strings:"

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

"At kung gagamit tayo ng generic na uri ng deklarasyon, magiging ganito ang hitsura nito:"

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

"May katuturan."

"Upang mas maunawaan ito, magsulat tayo ng code kung saan nagdaragdag tayo ng 10 elemento sa isang listahang doble-link:"

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

"Isipin na mayroon kaming 10 elemento sa listahan. Narito kung paano magpasok ng elemento sa gitna:"

"Ang mga link na nagbago ay naka-highlight na maliwanag na pula . Ang mga ito ngayon ay tumuturo sa bagong elemento."

"Ang mga bagong link ay naka-highlight na maliwanag na lila . Ang mga ito ay mga link ng bagong elemento sa mga kapitbahay nito."

"At ngayon bilang 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;

"Salamat, Ellie. Tiyak na marami akong natutunan tungkol sa mga listahan."