ArrayList vs. LinkedList vs. Vector

Přistoupit do role softwarového inženýrství je mnohem snazší, než si lidé myslí. Ale v některých případech většina mých lidí s mnohaletými zkušenostmi s touto odborností selhala ve své kandidatuře. "Co je problém?" Otázka je vyčerpaná v mé hlavě.

Užil jsem si svůj čas jako role softwarového inženýrství ještě lépe miloval, co dělám s mým kódem za posledních 6 let. Během této doby jsem měl úžasné zkušenosti s pohovory s mnoha uchazeči o softwarové inženýrství. V každém rozhovoru neočekávám jen, že kandidáti budou dobře založeni na tématech, jako jsou dobré principy návrhu softwaru, škálovatelná architektura architektury a testování, ale také jejich znalosti v základech struktury a algoritmu dat v softwarovém inženýrství. Byl jsem tak smutný, když mnoho kandidátů nerozumělo základnímu.

Kromě toho, že se rychle učíte, kteří se v krátké době mohou učit nové rámce, nástroje nebo dokonce programovat jazyky, je důkladné porozumění struktuře dat jednou z klíčových znalostí, které byste měli mít, pokud chcete vykonávat kariéru softwarového inženýra.

Struktura dat je zvláštní způsob ukládání a organizace informací v počítači, aby je bylo možné získat a používat nejproduktivněji. Různé druhy datových struktur jsou určeny pro různé druhy aplikací a některé jsou vysoce specializované na konkrétní úkoly. - Wikipedia

Proč se datová struktura stává jedním z důležitých znalostí, které mají? Struktura dat a algoritmus poskytují řadu technik pro efektivní zpracování dat. Pokud kandidáti nevědí o struktuře dat a algoritmu, nemusí být schopni napsat efektivní kód pro zpracování dat. Znalost toho, jak struktura dat ukládá svá data, jak provádějí a kdy je používat s předem definovanou sadou technik, zlepší čas potřebný k vyřešení problému. Jednou z otázek, na které kandidáti často neodpovídají, je

Který lepší, ArrayList, LinkedList nebo Vector?

Seznam

Před odpovědí na otázku je dobré vědět, co je to Seznam. Seznam je jedním z abstraktních datových typů (ADT), který ukládá své prvky do sekvence a umožňuje nám přidávat, odebírat a přistupovat k jejich elementům pomocí indexu. Pole je jednou z datových struktur, které implementují seznam ADT. V Array můžeme přidávat, mazat a získávat element pomocí indexu. ArrayList, LinkedList a Vector jsou dalším příkladem datových struktur, které implementují seznam ADT. Zatímco Array má statickou velikost, jakmile je deklarována, ArrayList, LinkedList a Vector mají dynamickou velikost (lze změnit velikost). Pokud je pole deklarováno s délkou 7, bude mít délku 7 až do konce svého rozsahu. Zatímco ArrayList, LinkedList a Vector mohou ukládat data co nejvíce, kde limit je celková dostupná paměť.

Java Collection Framework. Zdroj: Wikipedia

V Java Collection Framework je ADT List implementován jako rozhraní nazvané List a ArrayList, LinkedList & Vector jsou konkrétní třídou, která implementuje rozhraní List. Protože tyto konkrétní třídy implementují stejné rozhraní, musí mít tyto třídy stejnou funkčnost, protože u všech ne abstraktních tříd, které implementují rozhraní, je vyžadována implementace všech abstraktních metod, které jsou deklarovány v rozhraní.

Jak byla data uložena

Zásadní rozdíl mezi výše uvedenými třemi datovými strukturami je způsob, jakým ukládají svá data, což způsobuje různý výkon pro různé operace. V Javě (a také používán v Kotlinu) ArrayList a Vector používá Array k uložení svých prvků, zatímco LinkedList ukládá své prvky do dvojitě propojeného seznamu.

V informatice je dvojitě propojený seznam propojenou datovou strukturou, která se skládá ze sady sekvenčně spojených záznamů nazývaných uzly. Každý uzel obsahuje dvě pole, nazývaná propojení, která jsou odkazy na předchozí a další uzel v posloupnosti uzlů. - Wikipedia
ArrayList (nahoře) vs LinkedList (dole). Zdroj https://dzone.com/storage/temp/895349-arraylist-linkedlistt.png

V propojeném seznamu může první uzel znát druhý uzel. Druhý uzel může znát první a třetí uzel. Třetí uzel může znát druhý a čtvrtý uzel. A tak může uzel znát předchozí a následující uzel. Zejména pro první uzel v propojeném seznamu nebude žádný předchozí uzel a také poslední uzel v propojeném seznamu nebude žádný další uzel.

Zde je fragment kódu, jak ArrayList ukládá své prvky do Array.

/ **
 * Vyrovnávací paměť pole, do které jsou prvky ArrayList
 * uloženo. Kapacita ArrayList je její délka
 * vyrovnávací paměť pole. Jakýkoli prázdný ArrayList s elementData ==
 * DEFAULTCAPACITY_EMPTY_ELEMENTDATA bude rozšířeno na
 * DEFAULT_CAPACITY při přidání prvního prvku.
 * /
přechodný objekt [] elementData; // non-private pro zjednodušení vnořených
                                // přístup ke třídě

A tady je to, jak Vector ukládá své prvky také do pole.

/ **
 * Vyrovnávací paměť pole, do které jsou složky vektoru
 * uloženo. Kapacita vektoru je délka tohoto pole
 * vyrovnávací paměť a je alespoň dostatečně velká, aby obsahovala všechny vektory
 * elementy.
 *
 * 

Jakékoli prvky pole následující za posledním prvkem ve Vektoru  * jsou nulové.  *  * @serial  * / chráněný objekt [] elementData;

Ve výše uvedeném úryvku kódu vidíme, že jak ArrayList, tak Vector ukládá své prvky jako proměnnou s názvem elementDatawith Object []. Proč Object []? Objekt je super třída všech tříd v Javě. Definováním elementData jako Object [] by pak elementData mohl ukládat různé typy elementů, mohlo to být String, Integer, Double, Float nebo custom class jako Pair, TextView atd.

Proč ArrayList a Vector využívající Array k ukládání svých dat? Jak již bylo zmíněno dříve, ačkoli ArrayList a Vector používají pole k ukládání svých dat, ArrayList a Vector má schopnost mít dynamické velikosti (velikost lze změnit). Když je pole použité v ArrayList a Vector plné, mohou tyto „růst“ a zvětšit tak svou kapacitu. ArrayList a Vector zvyšují svou kapacitu vytvořením nového pole s velikostí větší než předchozí velikost a pak zkopírováním všech prvků ze starého pole do nového pole pomocí příkazu Arrays.copyOf. Tady je úryvek kódu programu na ArrayListu pro zvětšení jeho kapacity (zdroj: ArrayList.java).

/ **
  * Zvyšuje kapacitu, aby bylo zajištěno, že pojme alespoň
  * počet prvků zadaných argumentem minimální kapacity.
  *
  * @param minCapacity požadovanou minimální kapacitu
  * /
  soukromý růst prázdnin (int minCapacity) {
      // kód při přetečení
      int oldCapacity = elementData.length;
      int newCapacity = oldCapacity + (oldCapacity >> 1);
      if (newCapacity - minCapacity <0)
          newCapacity = minCapacity;
      if (newCapacity - MAX_ARRAY_SIZE> 0)
          newCapacity = obrovská kapacita (minCapacity);
      // minCapacity je obvykle blízko velikosti, takže jde o výhru:
      elementData = Arrays.copyOf (elementData, newCapacity);
  }

A tady je způsob, jak Vector rozšiřuje svou kapacitu (zdroj: Vector.java)

soukromý růst prázdnin (int minCapacity) {
    // kód při přetečení
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((kapacitaPřírůstek> 0)?
                                     capacityIncrement: oldCapacity);
    if (newCapacity - minCapacity <0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE> 0)
        newCapacity = obrovská kapacita (minCapacity);
    elementData = Arrays.copyOf (elementData, newCapacity);
}

Implementace vektoru je téměř totožná s ArrayList a jediným rozdílem jsou všechny operace ve vektoru, které jsou synchronizovány, takže každá metoda, která se dotýká obsahu vektoru, je bezpečná pro vlákno.

Takže který lepší, ArrayList, LinkedList nebo Vector? Odpověď na tuto otázku umožňuje porovnat výkon běžných operací v ArrayList a LinkedList. Protože implementace ArrayList a Vector je téměř identická, jejich výkon by také byl téměř stejný.

Porovnání výkonu mezi ArrayListem a LinkedListem

Z výše uvedené tabulky vidíme, že pro všechny operace neexistují stříbrné kulky. ArrayList je lepší než LinkedList při náhodném přístupu (get). ArrayList je lepší než LinkedList, protože ArrayList ukládá své prvky do pole, zatímco LinkedList ukládá své prvky do propojeného uzlu. Například pro získání pátého prvku mohou ArrayList a Vector přímo získat jeho element pomocí indexu, protože ArrayList a Vector jsou v podstatě pole, zatímco LinkedList musí být iterovaný, aby zjistil pátý prvek, protože v LinkedList můžeme znát pouze první a pouze poslední prvek.

Pro insertFirst a deleteFirst je LinkedList lepší než ArrayList. ArrayList vyžaduje velké úsilí přidat prvek na začátku (první index) nebo odstranit první prvek, protože ArrayList musí posunout následující prvky po přidání nebo odstranění. Zatímco LinkedList stačí vyměnit / nastavit jeho ukazatele. Pokud jde o jiné funkce, ArrayList i LinkedList mají relativně stejný výkon.

Takže který lepší, ArrayList, LinkedList nebo Vector? Závisí na vašich potřebách. Pokud používáte náhodný přístup (získejte) častěji, je ArrayList a Vector dobrou volbou. Pokud potřebujete kolekci bezpečnou pro vlákno, vyberte Vektor. Pokud ale často přidáváte nebo odstraňujete první pozici (index), je lepším výběrem LinkedList.

Existuje další ADT, které se běžně používá při vývoji aplikací, jako je Set, Map a PriorityQueue. Chcete-li vědět, jak ukládají svá data, jak fungují a kdy je mají používat, mějte na mém médiu pořádek.