streamalism.org

1. Oversikt

I denne superrask opplæringen viser vi hvordan du fjerner det første elementet fra en Liste.

Vi utfører denne operasjonen for to vanlige implementeringer av Liste grensesnitt - ArrayList og LinkedList.

2. Opprette en Liste

For det første, la oss fylle ut vårt Listes:

@Før offentlige ugyldig init () {list.add ("cat"); list.add ("hund"); list.add ("gris"); list.add ("ku"); list.add ("geit"); linkedList.add ("katt"); linkedList.add ("hund"); linkedList.add ("gris"); linkedList.add ("ku"); linkedList.add ("geit"); }

3. ArrayList

For det andre, la oss fjerne det første elementet fra ArrayList, og sørg for at listen vår ikke inneholder den lenger:

@Test offentlig ugyldighet gittList_whenRemoveFirst_thenRemoved () {list.remove (0); assertThat (liste, harSize (4)); assertThat (liste, ikke (inneholder ("katt"))); }

Som vist ovenfor bruker vi fjerne (indeks) metode for å fjerne det første elementet - dette vil også fungere for enhver implementering av Liste grensesnitt.

4. LinkedList

LinkedList også redskaper fjerne (indeks) metode (på sin egen måte), men den har også removeFirst () metode.

La oss sørge for at det fungerer som forventet:

@Test offentlig ugyldig givenLinkedList_whenRemoveFirst_thenRemoved () {linkedList.removeFirst (); assertThat (linkedList, hasSize (4)); assertThat (linkedList, ikke (inneholder ("cat"))); }

5. Tidskompleksitet

Selv om metodene ser like ut, er effektiviteten forskjellig. ArrayList‘S fjerne() metoden krever O (n) tid, mens LinkedList‘S removeFirst () metoden krever O (1) tid.

Dette er fordi ArrayList bruker en matrise under panseret, og fjerne() operasjonen krever kopiering av resten av matrisen til begynnelsen. Jo større matrisen er, jo flere elementer må forskyves.

I motsetning til det, LinkedList bruker pekere som betyr at hvert element peker til neste og forrige.

Derfor betyr det å fjerne det første elementet bare å endre pekeren til det første elementet. Denne operasjonen krever alltid samme tid, ikke avhengig av størrelsen på en liste.

6. Konklusjon

I denne artikkelen har vi dekket hvordan du fjerner det første elementet fra en Liste, og har sammenlignet effektiviteten av denne operasjonen for ArrayList og LinkedList implementeringer.

Som vanlig er den komplette kildekoden tilgjengelig på GitHub.