Structurile de date fundamentale explicate simplu
Pentru a avea o idee generală despre ce vorbim în acest articol trebuie mai întâi să definim ce sunt acelea structuri de date. Structurile de date sunt în primul rând un concept fundamental in programare. Fără a știi structurile de date de bază cu care te confrunți în orice limbaj de programare, nu te poți numi un adevărat programator. Așa că să începem cu o definire a structurilor de date.
Conform ibm.com, structurile de date sunt:
“O structură de date este o formă folosită pentru a scrie datele într-un format standardizat astfel încât ele să poată fi folosite de către un program sau un sistem. Structurile de date sunt componente fundamentale ale programării deoarece ele dau o formă datelor abstracte. Astfel, ele îi ajută pe utilizatori și sisteme să organizeze eficient, să manipuleze si stocheze datele.”
Structurile de date
Au o importanță aparte când vine vorba de a scrie cod efectiv. Fiecare structură de date are o regulă generală după care aceasta funcționează. Vom dezvolta puțin mai târziu această idee. Din cauza acestor reguli după care ele se formează, unele structuri funcționează perfect pentru anumite programe, iar pentru alte programe, aceleași structuri de date pot complica foarte mult logica programului și pot face execuția acelui program sa fie foarte înceată. Tocmai din această cauză, noi ca și programatori trebuie să știm foarte bine cu ce tip de date avem de a face, și cum ar trebui sa structurăm aceste date astfel încât sa avem o execuție si o performanță cât mai bune.
Acum haide sa aprofundăm puțin ideea de structuri de date și să intrăm în tipurile și regulile de funcționare al fiecărui tip de date existent. Trebuie să amintim și faptul ca acestea sunt niște concepte teoretice, iar în practică noi trebuie sa folosim structurile de date oferite de fiecare limbaj de programare pentru a crea aceste structuri de date conceptuale.
Aceste structuri de date sunt numite și structuri de date secvențiale deoarece sunt parcurse exact cum este parcursă o secvență, de la stângă la dreapta. Aceste structuri se pot imagina ca fiind ca o dreaptă, de acolo venind și numele de structuri de date liniare.
Vectori (Arrays)
Vectorul este cea mai simplă structură de bază care există, de asemenea și cea mai folosită dintre toate. În practică, de cele mai multe ori, ca să folosim celelalte structuri de date pe care le vom aminti vom folosi vectori deoarece sunt prezenți in mai toate limbajele de programare de pe piață și este o structură de date foarte ușor de utilizat si manipulat.
Vectorii ca și regulă stochează date de tipuri similare în locații adiacente de memorie. Mai exact, un array stocat in memorie va arată ca și un frigider pe care începi să îl umpli de sus in jos. Umpli prima etajera de la stângă la dreapta, apoi cea de a doua, și așa mai departe. Această structură de date permite un access si o localizare ușoară a datelor de același tip.
Cozi (Queues)
Pentru a putea explica mult mai ușor acest tip de date, îți poți imagina coada de la caseria unui magazin. După exact același principiu merge și acest tip de date. Principiul “FIFO” – First In First Out este principiul care guvernează acest tip de date. Exact ca la un magazin, în acest tip de date tu poți să introduci date prin doar o parte a cozii, și să extragi date din capătul opus. Primul item de date introdus va fi ultimul extras. De obicei, acest tip de date este folosit pentru cozi de prioritate când vine vorba de accesa o resursă limitată, astfel, in funcție de prioritatea pe care o are un user, acesta primește sau nu access la acea resursă.
Stive (Stacks)
Stiva este o alta structură de date liniară, care seamănă cu cozile, singura diferență fiind aceea ca principiul care guvernează acest tip de date este “LIFO” – Last In First Out. În această structură de date, itemi de date se introduc și elimină din același capăt. Ultimul adăugat va fi singurul pe care îl poți accesa și citi sau elimina din structura de date. Acest tip de date are multe atribuințe, fiind folosit în verificarea statică a unui fișier de cod sau a urmări și stoca istoricului căutărilor pe internet.
Liste înlănțuite (Linked lists)
Listele înlănțuite sunt o altă formă de stocare a datelor care structural seamănă cu vectorii, dar acest tip de date este stocat in memorie într-un mod complet diferit față de vectori. În timp ce pentru a stoca in memorie un vector tu ai nevoie in memorie o lista de celule de memorie libere adiacente exact cât de lung este vectorul, pentru a stoca o listă înlănțuită tu nu ai nevoie de asta. O listă înlănțuită este formată din itemi de date care fiecare are două valori. Prima valoare este valoarea stocată care este efectiv folosită în operațiile din program, iar a doua valoare este o adresă in memorie către următorul element din listă. Astfel, o listă înlănțuită est mult mai ușor de stocat in memorie deoarece tu nu mai ai acea constrângere în stocare pe care o ai cu vectorii.
Aceste structuri de date sunt mai abstracte decât structurile liniare de date, iar datele din aceste tipuri de date nu mai pot fi accesate secvențial. În aceste tipuri de date, datele sunt stocate in oricare alt fel dar nu liniar într-un aranjament secvențial. Din cauza acestor reguli de stocare, datele din aceste tipuri de date nu pot fi accesate toate într-o singura parcurgere astfel încât de cele mai multe ori ai nevoie de mai multe parcurgeri a structuri pentru a îți colecta toate datele necesare.
Arbori (Trees)
Această structură de date creează o ierarhie din itemi de date, similar cu un copac răsturnat. Asemenea unui copac, tu ai o rădăcină (root) care este nodul părinte al întregului arbore, iar sub acest nod ai o ramificație, cu noduri copii (subnodes). Daca am merge pe aceeași abstractizare, aceste noduri copii ar fi locul de pe trunchiul copacului de unde pornesc ramurile copacului. Există mai multe tipuri de arbori, iar fiecare din aceștia are reguli diferite și proprietăți diferite. Un arbore de acest tip care merită amintit de arborele binar care este folosit pentru a căuta valori într-o colecție de date.
Grafuri (Graphs)
Grafurile merg pe aceeași structură ca si arborii, iar grafurile sunt formate din noduri și muchii, exact ca un arbore. Există trei tipuri mari de grafuri, iar acestea sunt următoarele. Grafuri neorientate ceea ce înseamnă că muchiile nu au o direcție anume, parcurgerea datelor putând să se facă în orice ordine. Grafuri orientate, parcurgerea datelor putând să se facă doar în direcția precizată de muchia care conectează două noduri. Grafuri ponderate, unde fiecare muchie are un cost pentru parcurgerea acelei muchii, astfel, în parcurgerea grafului se ia in considerare și costurile muchiilor care conectează nodurile, căutându-se astfel parcurgerea cu cel mai mic cost posibil.
În concluzie, structurile de date sunt un lucru foarte important în programare. Ca și un programator este important să stăpânești aceste concepte, și este important să știi diferențele dintre aceste tipuri de date și cum fiecare dintre ele poate să afecteze sau să îmbunătățească performanțele programului tău. Îți recomand sa citești de mai multe ori acest articol, și dacă ai întrebări, ni le poți adresa in secțiunea de comentarii de mai jos.