Odstráňte prvý prvok zo zoznamu
1. Prehľad
V tomto veľmi rýchlom výučbe si ukážeme, ako odstrániť prvý prvok z a Zoznam.
Túto operáciu vykonáme pre dve bežné implementácie Zoznam rozhranie - ArrayList a LinkedList.
2. Vytvorenie a Zoznam
Po prvé, naplnime naše Zoznams:
@ Pred verejnosťou void init () {list.add ("mačka"); list.add ("pes"); list.add ("prasa"); list.add ("krava"); list.add ("koza"); linkedList.add ("mačka"); linkedList.add ("pes"); linkedList.add ("prasa"); linkedList.add ("krava"); linkedList.add ("koza"); }3. ArrayList
Po druhé, odstráňte prvý prvok z ArrayList, a uistite sa, že náš zoznam ho už neobsahuje:
@Test public void givenList_whenRemoveFirst_thenRemoved () {list.remove (0); assertThat (zoznam, hasSize (4)); assertThat (zoznam, nie (obsahuje („mačka“))); }Ako je uvedené vyššie, používame odstrániť (index) metóda na odstránenie prvého prvku - to bude fungovať aj pri akejkoľvek implementácii Zoznam rozhranie.
4. LinkedList
LinkedList tiež realizuje odstrániť (index) metóda (svojím spôsobom), ale má aj removeFirst () metóda.
Uistite sa, že funguje podľa očakávania:
@Test public void givenLinkedList_whenRemoveFirst_thenRemoved () {linkedList.removeFirst (); assertThat (linkedList, hasSize (4)); assertThat (linkedList, not (contains ("cat"))); }5. Časová zložitosť
Aj keď metódy vyzerajú podobne, ich účinnosť sa líši. ArrayList‘S odstrániť () metóda vyžaduje O (n) čas, zatiaľ čo LinkedList‘S removeFirst () metóda vyžaduje O (1) čas.
To je preto, že ArrayList používa pole pod kapotou a odstrániť () operácia vyžaduje skopírovanie zvyšku poľa na začiatok. Čím väčšie je pole, tým viac prvkov je potrebné posunúť.
Na rozdiel od toho LinkedList používa ukazovatele, čo znamená, že každý prvok ukazuje na nasledujúci a predchádzajúci.
Odstránenie prvého prvku teda znamená iba zmenu ukazovateľa na prvý prvok. Táto operácia vyžaduje vždy rovnaký čas, nie v závislosti od veľkosti zoznamu.
6. Záver
V tomto článku sme sa venovali spôsobu odstránenia prvého prvku z a Zoznam, a porovnali efektívnosť tejto operácie pre ArrayList a LinkedList implementácie.
Celý zdrojový kód je ako obvykle k dispozícii na serveri GitHub.
