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;
}