ArrayList vs LinkedList vs Vector

Darbs programmatūras inženiera lomā ir daudz vienkāršāks, nekā cilvēki domā. Bet dažos gadījumos vairumam manu ļaužu ar daudzu gadu pieredzi šajā pieredzē neizdevās izvirzīt savu kandidatūru. “Kāda problēma?” Man galvā uzpūta jautājums.

Es izbaudu savu laiku, būdams programmatūras inženiera lomā, vēl labāk mīlu to, ko es daru ar savu kodu pēdējos 6 gadus. Šajā laikā man ir bijusi pārsteidzoša pieredze, intervējot daudzus programmatūras inženierijas kandidātus. Katrā intervijas procesā es ne tikai ceru, ka kandidāti būs pietiekami pamatoti tādās tēmās kā labi programmatūras projektēšanas principi, mērogojama koda arhitektūra un testēšana, bet arī viņu zināšanas datu struktūras pamatos un programmatūras inženierijas algoritmā. Man bija tik skumji, kad daudzi kandidāti nesaprata pamata.

Papildus tam, ka tas ir ātrs audzēknis, kurš īsā laikā var iemācīties jaunas struktūras, rīkus vai pat programmēšanas valodas, skaidra izpratne par datu struktūru ir arī viena no galvenajām zināšanām, kas jums vajadzētu būt, ja vēlaties turpināt programmatūras inženiera karjeru.

Datu struktūra ir īpašs informācijas glabāšanas un sakārtošanas veids datorā, lai to varētu iegūt un produktīvāk izmantot. Dažāda veida datu struktūras ir paredzētas dažāda veida lietojumiem, un daži ir ļoti specializēti noteiktiem uzdevumiem. - Vikipēdija

Kāpēc datu struktūra kļūst par vienu no svarīgākajām zināšanām? Datu struktūra un algoritms nodrošina metožu kopumu efektīvai datu apstrādei. Ja kandidāti nezina par datu struktūru un algoritmu, iespējams, viņi nevarēs uzrakstīt efektīvu kodu datu apstrādei. Zinot, kā datu struktūrā tiek glabāti viņu dati, kā tie darbojas un kad tos izmantot ar iepriekš noteiktu paņēmienu kopu, tiks uzlabots laiks, kas nepieciešams problēmas risināšanai. Viens no jautājumiem, uz kuru kandidāti bieži nespēj atbildēt, ir

Kurš labāks, ArrayList, LinkedList vai Vector?

Saraksts

Pirms atbildes uz jautājumu ir labi zināt, kas ir saraksts. Saraksts ir viens no abstraktiem datu tipiem (ADT), kas savus elementus glabā secīgā secībā un ļauj mums pievienot, noņemt un piekļūt tā elementiem, izmantojot indeksu. Masīvs ir viena no datu struktūrām, kas ievieš ADT sarakstu. Masīvā mēs varam pievienot, dzēst un iegūt elementu, izmantojot indeksu. ArrayList, LinkedList un Vector ir vēl viens datu struktūru piemērs, kas ievieš ADT sarakstu. Kamēr Array ir statisks izmērs, tiklīdz tas ir deklarēts, ArrayList, LinkedList un Vector ir dinamisks izmērs (maināms). Ja masīvs tiek deklarēts ar garumu 7, tad tam būs 7 garums līdz tā darbības jomas beigām. Kaut arī ArrayList, LinkedList un Vector var cik vien iespējams uzglabāt datus, ja pieejamais atmiņa ir ierobežota.

Java kolekcijas ietvars. Avots: Wikipedia

Java kolekcijas ietvarā ADT saraksts tiek ieviests kā saskarne, ko sauc par sarakstu, un ArrayList, LinkedList un Vector ir konkrētā klase, kas ievieš saraksta saskarni. Tā kā šīs konkrētās klases īsteno to pašu saskarni, šīm klasēm jābūt ar vienādu funkcionalitāti, jo visām neabstraktām klasēm, kuras ievieš saskarni, ir jāievieš visas abstraktās metodes, kas deklarētas saskarnē.

Kā dati tiek glabāti

Triju iepriekšminēto datu struktūru galvenā atšķirība ir veids, kā tie glabā savus datus, kas dažādām darbībām rada atšķirīgu veiktspēju. Java valodā (un to izmanto arī Kotlinā) ArrayList un Vector izmanto masīvu, lai saglabātu savus elementus, savukārt LinkedList savus elementus saglabā divkārši saistītā sarakstā.

Datorzinātnē divkārt saistīts saraksts ir saistīta datu struktūra, kas sastāv no secīgi saistītu ierakstu kopuma, ko sauc par mezgliem. Katrā mezglā ir divi lauki, saukti par saitēm, kas ir atsauces uz iepriekšējo un uz nākamo mezglu mezglu secībā. - Vikipēdija
ArrayList (augšpusē) vs LinkedList (apakšā). Avots https://dzone.com/storage/temp/895349-arraylist-linkedlistt.png

LinkedList pirmais mezgls var zināt otro mezglu. Otrais mezgls var zināt pirmo un trešo mezglu. Trešais mezgls var zināt otro un ceturto mezglu. Un tā tālāk, mezgls var zināt iepriekšējo un nākamo mezglu. Īpaši pirmajam mezglā LinkedList nebūs iepriekšējā mezgla, un arī pēdējam mezglā LinkedList nebūs nākamā mezgla.

Šeit ir koda fragments, kā ArrayList glabā savus elementus masīvā.

/ **
 * Masīva buferis, kurā atrodas ArrayList elementi
 * glabājas. ArrayList ietilpība ir tā garums
 * masīva buferis. Jebkurš tukšs ArrayList ar elementData ==
 * DEFAULTCAPACITY_EMPTY_ELEMENTDATA tiks izvērsts līdz
 * DEFAULT_CAPACITY, kad tiek pievienots pirmais elements.
 * /
pārejošs objekts [] elementData; // nav privāts, lai vienkāršotu ligzdotu saturu
                                // pieeja klasei

Un šeit ir redzams, kā Vector savus elementus glabā arī masīvā.

/ **
 * Masīva buferis, kurā atrodas vektora komponenti
 * glabājas. Vektoru ietilpība ir šī masīva garums
 * buferis, un tas ir vismaz pietiekami liels, lai saturētu visus vektorus
 * elementi.
 *
 * 

Jebkuri masīva elementi, kas seko pēdējam vektora elementam  * nav spēkā.  *  * @sērija  * / aizsargāts objekts [] elementData;

Iepriekš redzamajā koda fragmentā mēs redzam, ka gan ArrayList, gan Vector saglabā tā elementus mainīgajā ar nosaukumu elementDatawith Object [] kā tā tipu. Kāpēc objekts []? Objekts ir visu Java klašu superklase. Definējot elementData kā Object [], tad elementData varētu uzglabāt dažāda veida elementus, tā varētu būt virkne, vesels skaitlis, dubultā, peldošā vai pielāgotā klase, piemēram, Pair, TextView un tā tālāk.

Kāpēc ArrayList un Vector izmanto Array, lai saglabātu savus datus? Kā minēts iepriekš, lai gan ArrayList un Vector savu datu glabāšanai izmanto masīvus, ArrayList un Vector ir spēja būt dinamiskiem izmēriem (maināmiem). Kad ArrayList un Vector izmantotais masīvs ir pilns, tie var “augt”, lai palielinātu tā ietilpību. ArrayList un Vector palielina tā ietilpību, izveidojot jaunu masīvu, kura lielums ir lielāks par iepriekšējo, pēc tam, izmantojot komandu Arrays.copyOf, visus elementus no vecā masīva kopē ar jauno masīvu. Šeit ir programmas fragments vietnē ArrayList, lai palielinātu tās ietilpību (avots: ArrayList.java).

/ **
  * Palielina spēju nodrošināt, ka tā var noturēt vismaz
  * elementu skaits, kas norādīts ar minimālās ietilpības argumentu.
  *
  * @param minCapacity vēlamā minimālā ietilpība
  * /
  privāts tukšums pieaug (int minCapacity) {
      // pārpildīts kods
      int oldCapacity = elementData.length;
      int newCapacity = oldCapacity + (oldCapacity >> 1);
      if (newCapacity - minCapacity <0)
          newCapacity = minkapacitāte;
      if (newkapacitāte - MAX_ARRAY_SIZE> 0)
          newCapacity = milzīga kapacitāte (minCapacity);
      // minCapacity parasti ir tuvu lielumam, tāpēc tas ir ieguvums:
      elementData = Masīvi.copyOf (elementData, newCapacity);
  }

Un šeit ir redzams, kā Vector palielina savu jaudu (avots: Vector.java)

privāts tukšums pieaug (int minCapacity) {
    // pārpildīts kods
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((kapacitāteIncrement> 0)?
                                     jaudaIncrements: vecākapacitāte);
    if (newCapacity - minCapacity <0)
        newCapacity = minkapacitāte;
    if (newkapacitāte - MAX_ARRAY_SIZE> 0)
        newCapacity = milzīga kapacitāte (minCapacity);
    elementData = Masīvi.copyOf (elementData, newCapacity);
}

Vektoru ieviešana ir gandrīz identiska ArrayList, un vienīgā atšķirība ir tā, ka visas vektorā veiktās darbības tiek sinhronizētas, kas padara visas metodes, kas skar vektora saturu, diegu drošu.

Tātad, kurš no tiem ir labāks, ArrayList, LinkedList vai Vector? Lai atbildētu uz šo jautājumu, varēsit salīdzināt kopējo darbību veiktspēju ArrayList un LinkedList. Tā kā ArrayList un Vector ieviešana ir gandrīz identiska, arī to veiktspēja būtu gandrīz vienāda.

Veiktspējas salīdzinājums starp ArrayList un LinkedList

No iepriekš redzamās tabulas mēs redzam, ka visām darbībām nav sudraba lodes. ArrayList ir pārāks par LinkedList ar brīvpiekļuvi (get). ArrayList ir labāks par LinkedList, jo ArrayList savus elementus saglabā masīvā, savukārt LinkedList savus elementus glabā saistītajā mezglā. Piemēram, lai iegūtu 5. elementu, ArrayList un Vector var tieši iegūt tā elementu, izmantojot indeksu, jo ArrayList un Vector būtībā ir masīvs, savukārt LinkedList jābūt iteratīvam, lai uzzinātu piekto elementu, jo LinkedList mēs varam zināt tikai pirmo un tikai pēdējais elements.

Lai ievietotu pirmo un izdzēstu pirmo, LinkedList ir pārāks par ArrayList. ArrayList prasa lielas pūles, lai pievienotu elementu sākumā (pirmais indekss) vai izdzēstu pirmo elementu, jo ArrayList pēc pievienošanas vai dzēšanas ir jāpārvieto šādi elementi. Lai gan LinkedList ir jāaizstāj / jāiestata tikai norādes. Runājot par citām funkcijām, gan ArrayList, gan LinkedList darbība ir salīdzinoši vienāda.

Tātad, kurš no tiem ir labāks, ArrayList, LinkedList vai Vector? Atkarīgs no jūsu vajadzībām. Ja biežāk izmantojat brīvpiekļuvi (iegūstat), tad laba izvēle ir ArrayList un Vector. Izvēlieties Vektors, ja jums nepieciešama kolekcija, kas ir droša pavedieniem. Bet, ja jūs bieži veicat papildinājumus vai svītrojumus pirmajā pozīcijā (indeksā), labāka izvēle ir LinkedList.

Ir vēl viens ADT, ko parasti izmanto, izstrādājot lietojumprogrammas, piemēram, Set, Map un PriorityQueue. Lai uzzinātu, kā viņi glabā savus datus, kā viņi strādā un kad tos izmantot, sekojiet manam videi.