Ruby liste legate

pentru acest exercițiu, vom implementa o versiune simplă a unei liste legate individual. Dar mai întâi, să aflăm ce este o listă legată și de ce ar trebui să vă pese.

o listă legată o structură de date, utilizată pentru inserții și ștergeri rapide și eficiente din punct de vedere al memoriei. Spre deosebire de matrice, care sunt obiecte unice, listele legate conțin mai multe obiecte ‘nod’ care sunt legate între ele prin referințe.

listele legate pot fi conectate individual sau dublu. Ne vom concentra pe liste separate pentru moment.

listă singur legată

dacă listele legate sunt mai multe obiecte legate între ele, în mod ideal avem nevoie de câteva obiecte diferite.

  1. un obiect LinkedList, care deține toate obiectele din listă

  2. un obiect nod, care conține datele pentru elementul, precum și o referință la următorul nod din listă.

stai, de ce nu folosiți tablouri în schimb?

în limbile de nivel inferior, matricele sunt allocatd în blocuri. Prin urmare, matricele au dimensiuni statice și pot conține doar un anumit tip de date. Listele legate stochează date în heap, ceea ce înseamnă că datele pot fi stocate într-o manieră neorganizată. Deoarece fiecare nod indică următorul, este încă posibil să se mențină structura listei.

Noțiuni de bază

cel mai bun mod de a înțelege cum funcționează listele legate este să faci una! Să facem acest lucru în Ruby. Iată procesul.

  1. începeți prin crearea unei clase Node. Vom avea atribute pentru a reprezenta datele (să numim acest @data) și referința la următorul nod (să numim acest @next).

  2. creați o clasă LinkedList. Această clasă va avea două valori, @head și @tail. Acestea vor reprezenta începutul și sfârșitul listei. Inițializați ambele la nil pentru moment. Avem o listă goală!

  3. acum pentru încorporarea celor două clase împreună. Creați o metodă pe clasa LinkedList numită insert_front. Provocarea este de a adăuga un element la începutul listei. Acest lucru se poate face prin crearea unui nou Node, apoi făcând următoarele:

  4. stocați valoarea @head într-o variabilă temp

  5. setați @headla nou creat Node. Rețineți că, în prezent, referința sa next este nil.

  6. gândiți-vă la ce ar trebui să facem dacă adăugăm un element nou la începutul unei liste legate. Consultați diagrama( sugestie :va trebui să facem ceva cu referința next a noului nod)

  7. în cele din urmă, se ocupe de cazul special al @tail. @tail ar trebui să fie întotdeauna ultimul Node din lista legată.

  8. creați o altă metodă pe LinkedList sau Node numită to_s pentru a imprima lista în consolă.

iterarea peste liste legate

utilizați while loops pentru a itera peste o listă legată. În timp ce buclele sunt mai bune decât pentru bucle aici, deoarece listele legate nu au o proprietate de lungime. În loc să repetăm for de un anumit număr de ori, pur și simplu repetăm while indicatorul nostru currentnu este nil.

creați o variabilă locală numită current care începe să indice spre nodul rădăcină al listei. În interiorul buclei puteți face două lucruri:

  1. accesați valoarea nodului curent la current.data

  2. indicați variabila curentă la următorul element cu current = current.next

BONUS: creați o metodă insert_end pentru a adăuga noduri la sfârșitul listei.

Super BONUS: creați o metodă mai versatilă insert pentru a adăuga un nod oriunde în lista legată, oferind un index pentru noul element.

Lasă un răspuns

Adresa ta de email nu va fi publicată.