bild
Skolan för
elektroteknik
och datavetenskap

Länkade listor

En lista, ett antal element ordnade i en linjär struktur, är den kanske enklaste och mest grundläggande datastrukturen. Java erbjuder flera implementationer av listor:

  • den vanliga vektorn (t.ex. int[]) som har direkt stöd i hårdvara och är enkel men något begränsad,
  • ArrayList som är implementerad med hjälp av en vektor men har ytterligare funktionalitet,
  • och LinkedList som har i stort sett samma funktionalitet som ArrayList men annorlunda prestanda.

I det här uppgiften får du lära dig hur länkade listor fungerar genom att göra en implementation i Java och analysera tidskomplexiteten för de grundläggande operationerna.

En länkad lista är en sekvens av listelement förbundna av pekare. En länkad lista med tre heltal [2, 2, 1] ser ut så här.

     ----------        ----------        ----------
    |     |    |      |     |    |      |     |    |
--->|  2  |  -------->|  2  |  -------->|  1  |null|
    |     |    |      |     |    |      |     |    |
     ----------        ----------        ----------

Listelementen kan implementeras som objekt med två instansvariabler, en variabel som innehåller nodens värde och en variabel som pekar på nästa element i listan:

class ListElement {
    int data;
    ListElement next;
}

Copyright © Sidansvarig: Stefan Nilsson <snilsson@nada.kth.se>
Uppdaterad 2009-08-03