Ruby Linked Lists

til denne øvelse implementerer vi en simpel version af en enkeltkædet liste. Men først, lad os lære, hvad en linket liste er, og hvorfor du skal pleje.

en sammenkædet liste en datastruktur, der bruges til hurtige og hukommelseseffektive indsættelser og sletninger. I modsætning til arrays, som er enkeltobjekter, indeholder sammenkædede lister flere ‘node’ objekter, der er knyttet sammen via referencer.

linkede lister kan enten være enkeltvis eller dobbelt forbundet. Vi vil fokusere på enkeltvis sammenkædede lister for nu.

enkeltkædet liste

hvis sammenkædede lister er flere objekter, der er knyttet sammen, har vi ideelt set brug for et par forskellige objekter.

  1. et LinkedList-objekt, der indeholder alle objekterne på listen

  2. en Node objekt, som indeholder data for elementet, samt en henvisning til den næste Node på listen.

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.

Skriv et svar

Din e-mailadresse vil ikke blive publiceret.