vent, hvorfor ikke bruge arrays i stedet?

i lavere niveau sprog, arrays er allocatd i blokke. Derfor er arrays statiske i størrelse og kan kun indeholde en bestemt datatype. Sammenkædede lister gemmer data i bunken, hvilket betyder, at dataene kan gemmes på en uorganiseret måde. Da hver node peger på den næste, er det stadig muligt at opretholde listestrukturen.

Kom godt i gang

den bedste måde at forstå, hvordan linkede lister fungerer, er at lave en! Lad os gøre det i Ruby. Her er processen.

1. Start med at oprette en Node klasse. Vi har attributter til at repræsentere dataene (lad os kalde dette @data) og henvisningen til den næste Node (lad os kalde dette @next).

2. Opret en LinkedList klasse. Denne klasse vil have to værdier, @head og @tail. Disse vil repræsentere begyndelsen og slutningen af listen. Initialiser begge til nil for nu. Vi har en tom liste!

3. nu for at indarbejde de to klasser sammen. Opret en metode på LinkedList klassen kaldet insert_front. Udfordringen er at tilføje et element til begyndelsen af listen. Dette kan gøres ved at oprette en ny Node og derefter gøre følgende:

4. Gem værdien af @head i en temp-variabel

5. Indstil @head til den nyoprettede Node. Bemærk, at i øjeblikket er dens next reference nil.

6. tænk over, hvad vi skal gøre, hvis vi tilføjer et nyt element til begyndelsen af en sammenkædet liste. Se diagrammet (TIP: Vi bliver nødt til at gøre noget med den nye node ‘ s next reference)

7. til sidst skal du håndtere det specielle tilfælde af @tail. @tail skal altid være den sidste Node i den linkede liste.

8. Opret en anden metode på LinkedList eller Node kaldet to_s for at udskrive listen til konsollen.

iterere over sammenkædede lister

brug mens sløjfer til at gentage over en sammenkædet liste. Mens sløjfer er bedre end for sløjfer her, fordi linkede lister ikke har en længdeegenskab. I stedet for at gentage for et bestemt antal gange, gentager vi simpelthen while vores current pointer er ikke nil.

Opret en lokal variabel kaldet current, der starter med at pege på listens rodknude. Inde i løkken kan du gøre to ting:

1. få adgang til værdien af den aktuelle node på current.data

2. peg den aktuelle variabel til næste punkt med current = current.next

BONUS: Opret en insert_end metode til at tilføje noder til slutningen af listen.

SUPER BONUS: Opret en mere alsidig insert metode til at tilføje en node hvor som helst i den linkede liste, hvilket giver et indeks for det nye element.