streamalism.org

1. Oversigt

I denne superhurtige vejledning viser vi, hvordan du fjerner det første element fra en Liste.

Vi udfører denne operation for to almindelige implementeringer af Liste grænseflade - ArrayList og LinkedList.

2. Oprettelse af en Liste

Lad os først udfylde vores Listes:

@Før offentlig ugyldig init () {list.add ("kat"); list.add ("hund"); list.add ("gris"); list.add ("ko"); list.add ("ged"); linkedList.add ("kat"); linkedList.add ("hund"); linkedList.add ("gris"); linkedList.add ("ko"); linkedList.add ("ged"); }

3. ArrayList

For det andet, lad os fjerne det første element fra ArrayList, og sørg for, at vores liste ikke indeholder den længere:

@Test offentlig ugyldighed givenList_whenRemoveFirst_thenRemoved () {list.remove (0); assertThat (liste, hasSize (4)); assertThat (liste, ikke (indeholder ("kat"))); }

Som vist ovenfor bruger vi fjern (indeks) metode til at fjerne det første element - dette vil også fungere for enhver implementering af programmet Liste interface.

4. LinkedList

LinkedList også redskaber fjern (indeks) metode (på sin egen måde), men den har også removeFirst () metode.

Lad os sørge for, at det fungerer som forventet:

@Test offentlig ugyldighed givenLinkedList_whenRemoveFirst_thenRemoved () {linkedList.removeFirst (); assertThat (linkedList, hasSize (4)); assertThat (linkedList, ikke (indeholder ("kat"))); }

5. Tidskompleksitet

Selv om metoderne ligner hinanden, er effektiviteten forskellig. ArrayList'S fjerne() metode kræver O (n) tid, hvorimod LinkedList'S removeFirst () metode kræver O (1) tid.

Dette er fordi ArrayList bruger en matrix under emhætten, og fjerne() operation kræver kopiering af resten af ​​arrayet til begyndelsen. Jo større matrixen er, jo flere elementer skal skiftes.

I modsætning til det, LinkedList bruger markører, hvilket betyder, at hvert element peger på det næste og det forrige.

Derfor fjerner det første element bare at ændre markøren til det første element. Denne handling kræver altid samme tid, ikke afhængigt af størrelsen på en liste.

6. Konklusion

I denne artikel har vi dækket, hvordan man fjerner det første element fra en Liste, og har sammenlignet effektiviteten af ​​denne operation for ArrayList og LinkedList implementeringer.

Som sædvanlig er den komplette kildekode tilgængelig på GitHub.