ArrayList vs LinkedList vs Vector

Obtenir un lloc de treball en enginyeria de programari és molt més fàcil del que la gent pensa. Però en alguns casos, la majoria de les meves persones amb molts anys d'experiència en aquesta experiència han fracassat la seva candidatura. "Què hi ha un problema?" La pregunta em queda al cap.

He estat gaudint del meu temps com a rol d'Enginyeria de Programari, a més m'encanta el que he estat fent amb el meu codi durant els darrers 6 anys. Durant aquest temps he tingut experiències sorprenents entrevistant a molts candidats en enginyeria de programari. En tots els processos d’entrevistes, no només espero que els candidats estiguin ben fonamentats en temes com els bons principis de disseny de programari, l’arquitectura de codis escalables i les proves, sinó també els seus coneixements bàsics en l’estructura de dades i l’algoritme en enginyeria de programari. Estava tan trist quan molts candidats no van entendre el bàsic.

A més de ser un aprenent ràpid que pot aprendre nous marcs, eines o fins i tot llenguatges de programació en un curt període de temps, tenir una bona comprensió de l’estructura de dades és un dels coneixements clau que hauria de tenir si voleu continuar una carrera d’enginyer de programari.

L’estructura de dades és una forma particular d’emmagatzemar i organitzar informació en un ordinador de manera que es pugui recuperar i utilitzar de manera més productiva. Per a diferents tipus d'aplicacions, s'utilitzen diferents tipus d'estructures de dades, i algunes estan molt especialitzades en tasques específiques. - Viquipèdia

Per què l'estructura de les dades es converteix en un dels coneixements importants per tenir? L’estructura i l’algoritme de dades proporcionen un conjunt de tècniques per manejar les dades de manera eficient. Si els candidats no coneixen l'estructura i l'algoritme de dades, és possible que no puguin escriure codi eficient per gestionar les dades. Saber com l’estructura de dades emmagatzema les seves dades, com funcionen i quan s’utilitzen amb un conjunt de tècniques predefinides millorarà el temps necessari per resoldre el problema. Una de les preguntes a les quals els candidats sovint no responen és

Quin millor, ArrayList, LinkedList o Vector?

Llista

Abans de respondre la pregunta, és bo saber què és la llista. La llista és un tipus de dades abstracte (ADT) que emmagatzema els seus elements en una seqüència i ens permet afegir, eliminar i accedir als seus elements mitjançant l'índex. Array és una de les estructures de dades que implementa la llista d’ADT. A Array, podem afegir, eliminar i obtenir l'element mitjançant l'índex. ArrayList, LinkedList i Vector són un altre exemple d’estructures de dades que implementen ADT List. Si bé Array té una mida estàtica un cop declarat, ArrayList, LinkedList i Vector tenen una mida dinàmica (canviable). Si es declara un Matriu amb la longitud 7, tindrà una longitud de 7 fins al final del seu abast. Mentre que ArrayList, LinkedList i Vector poden emmagatzemar dades el màxim possible, on el límit és total de memòria disponible.

Java Collection Framework. Font: Viquipèdia

Al Java Collection Framework, la llista ADT s’implementa com a una interfície anomenada List i ArrayList, LinkedList i Vector són la classe concreta que implementa la interfície de la llista. Com que aquestes classes concretes implementen la mateixa interfície, aquestes classes han de tenir la mateixa funcionalitat, ja que per a totes les classes no abstractes que implementen una interfície, cal implementar tots els mètodes abstractes que es declaren a la interfície.

Com s'emmagatzemen les dades

La diferència fonamental de les tres estructures de dades anteriors és la forma d’emmagatzemar les seves dades, la qual cosa provoca un rendiment diferent per a diferents operacions. A Java (i també s'utilitza a Kotlin), ArrayList i Vector utilitzen un Array per emmagatzemar els seus elements, mentre que LinkedList emmagatzema els seus elements en una llista doblement enllaçada.

En informàtica, una llista doblement enllaçada és una estructura de dades enllaçada que consisteix en un conjunt de registres enllaçats seqüencialment anomenats nodes. Cada node conté dos camps, anomenats enllaços, que són referències a l'anterior i al següent node de la seqüència de nodes. - Viquipèdia
Llista Array (superior) i LinkedList (inferior). Font https://dzone.com/storage/temp/895349-arraylist-linkedlistt.png

A LinkedList, el primer node pot conèixer el segon node. El segon node pot conèixer el primer i el tercer node. El tercer node pot conèixer el segon i quart node. I així successivament, un Node pot conèixer el Node anterior i el Node següent. Especialment per al primer node a LinkedList, no hi haurà cap node anterior i, a més, l'últim node de LinkedList no hi haurà un node següent.

Aquí teniu el fragment de codi de com ArrayList emmagatzema els seus elements a Array.

/ **
 * El buffer de matriu en el qual es troben els elements de la matriu ArrayList
 * emmagatzemat. La capacitat d’ArrayList és la longitud d’aquest
 * buffer de matriu. Qualsevol ArrayList buit amb elementData ==
 * DEFAULTCAPACITY_EMPTY_ELEMENTDATA s'ampliarà a
 * DEFAULT_CAPACITY quan s'afegeix el primer element.
 * /
Object transient [] elementData; // no privat per simplificar imbricat
                                // accés a classe

I aquí és com Vector emmagatzema els seus elements també a Array.

/ **
 * El buffer de matriu en què es troben els components del vector
 * emmagatzemat. La capacitat del vector és la longitud d'aquesta matriu
 * buffer i és almenys prou gran com per contenir tots els vectoris
 * elements.
 *
 * 

Qualsevol element de matriu després del darrer element del vector  * són nuls.  *  * @serial  * / protected Object [] elementData;

Al fragment de codi anterior, podem veure que tant ArrayList com Vector emmagatzemen els seus elements en una variable anomenada elementDatawith Object [] com el seu tipus. Per què objectar []? Object és una super-classe de totes les classes de Java. En definir elementData com a Objecte [], llavors elementData podria emmagatzemar diversos tipus d’elements, pot ser una cadena, un nombre enter, doble, Float o una classe personalitzada com Pair, TextView, etc.

Per què ArrayList i Vector utilitzen una matriu per emmagatzemar les seves dades? Com s'ha esmentat anteriorment, tot i que ArrayList i Vector utilitzen matrius per emmagatzemar les seves dades, ArrayList i Vector tenen la capacitat de tenir mides dinàmiques (canviables). Quan la matriu usada a ArrayList i Vector està plena, aquestes poden “créixer” per augmentar la seva capacitat. ArrayList i Vector augmenten la seva capacitat creant un Array nou amb una mida més gran que la mida anterior, i després copia tots els elements de l'antic Array al nou Array mitjançant l'ordre Arrays.copyOf. Aquí hi ha un fragment de codi del programa a ArrayList per ampliar la seva capacitat (font: ArrayList.java).

/ **
  * Augmenta la capacitat per assegurar-se que pot mantenir almenys la
  * nombre d’elements especificats per l’argument de capacitat mínima.
  *
  * @param minCapacity la capacitat mínima desitjada
  * /
  privat void grow (capacitat mínima int) {
      // codi conscient del desbordament
      int oldCapacity = elementData.length;
      int newCapacity = oldCapacity + (oldCapacity >> 1);
      if (newCapacity - minCapacity <0)
          newCapacity = minCapacity;
      if (newCapacitat - MAX_ARRAY_SIZE> 0)
          newCapacity = enormeCapacitat (minCapacity);
      // minCapacity sol ser a prop de la mida, per tant, es pot guanyar:
      elementData = Arrays.copyOf (elementData, newCapacity);
  }

I aquí és com Vector amplia la seva capacitat (font: Vector.java)

privat void grow (capacitat mínima int) {
    // codi conscient del desbordament
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacitatIncrement> 0)?
                                     capacitatIncrement: OldCapacity);
    if (newCapacity - minCapacity <0)
        newCapacity = minCapacity;
    if (newCapacitat - MAX_ARRAY_SIZE> 0)
        newCapacity = enormeCapacitat (minCapacity);
    elementData = Arrays.copyOf (elementData, newCapacity);
}

La implementació del vector és gairebé idèntica a la de ArrayList i l’única diferència és que totes les operacions de Vector es sincronitzen que fa que qualsevol mètode que toqui el contingut del vector sigui segur.

Llavors, quin és millor, ArrayList, LinkedList o Vector? Per respondre a aquesta pregunta, comparem el rendiment de les operacions comunes a ArrayList i LinkedList. Com que la implementació ArrayList i Vector és gairebé idèntica, el seu rendiment també seria gairebé el mateix.

Comparació de rendiment entre ArrayList i LinkedList

A la taula anterior, podem veure que no hi ha bala de plata per a totes les operacions. ArrayList és superior a LinkedList en accés aleatori (obtenir). ArrayList és millor que LinkedList perquè ArrayList emmagatzema els seus elements en un Array mentre que LinkedList emmagatzema els seus elements dins del Node enllaçat. Per exemple, per obtenir el cinquè element, ArrayList i Vector poden obtenir directament el seu element mitjançant l'ús de l'índex, ja que ArrayList i Vector són essencialment una matriu, mentre que LinkedList ha de ser iterat per esbrinar el cinquè element, perquè a LinkedList, només podem conèixer el primer i només el darrer element.

Per inserir primer i eliminar primer, LinkedList és superior a ArrayList. ArrayList requereix un gran esforç per afegir un element al principi (primer índex) o suprimir el primer element, perquè ArrayList ha de canviar els elements següents després de la suma o supressió. Tot i que LinkedList només cal substituir / establir els seus indicadors. Pel que fa a altres funcions, tant ArrayList com LinkedList tenen relativament el mateix rendiment.

Llavors, quin és millor, ArrayList, LinkedList o Vector? Depèn de les vostres necessitats. Si feu servir accés (obtenir) aleatori més sovint, ArrayList i Vector són una bona opció. Trieu Vector si necessiteu una col·lecció segura de fils. Però si feu freqüentment addicions o supressions a la primera posició (índex), LinkedList és una opció millor.

Hi ha un altre ADT que s’utilitza habitualment durant el desenvolupament d’aplicacions com Set, Map i PriorityQueue. Per saber com emmagatzemen les seves dades, com funcionen i quan s’utilitzen, mantingueu-vos al corrent del meu mitjà.