6 structuri de date pe care fiecare programator ar trebui să le cunoască

Calea pentru a deveni un programator competent și de succes este dificilă, dar cu siguranță realizabilă. Structurile de date sunt o componentă de bază pe care fiecare student la programare trebuie să o stăpânească și sunt șanse să fi învățat sau să fi lucrat deja cu unele structuri de date de bază, cum ar fi matrice sau liste.

Intervievatorii tind să prefere să pună întrebări legate de structurile de date, așa că, dacă vă pregătiți pentru un interviu de angajare, va trebui să vă îmbunătățiți cunoștințele privind structurile de date. Citiți mai departe, în timp ce enumeram cele mai importante structuri de date pentru programatori și interviurile de angajare.

Listele legate sunt una dintre cele mai elementare structuri de date și adesea punctul de plecare pentru studenții la majoritatea cursurilor de structuri de date. Listele legate sunt structuri de date liniare care permit accesul secvenţial la date.

Elementele din lista legată sunt stocate în noduri individuale care sunt conectate (legate) folosind pointeri. Vă puteți gândi la o listă legată ca la un lanț de noduri conectate între ele prin indicatori diferiți.

Legate de: O introducere în utilizarea listelor legate în Java

Înainte de a intra în specificul diferitelor tipuri de liste legate, este crucial să înțelegem structura și implementarea nodului individual. Fiecare nod dintr-o listă legată are cel puțin un pointer (nodurile liste dublu legate au doi pointeri) care îl conectează la următorul nod din listă și cu elementul de date în sine.

Fiecare listă legată are un nod cap și coadă. Nodurile de listă cu legături unice au un singur indicator care indică următorul nod din lanț. În plus față de următorul pointer, nodurile de listă dublu legate au un alt pointer care indică către nodul anterior din lanț.

Întrebările de interviu legate de listele conectate gravitează de obicei în jurul inserării, căutării sau ștergerii unui anumit element. Inserarea într-o listă legată durează O(1) timp, dar ștergerea și căutarea pot dura O(n) timp în cel mai rău caz. Deci listele legate nu sunt ideale.

2. Arborele binar

Arborii binari sunt cel mai popular subset al structurii de date a familiei de arbori; elementele dintr-un arbore binar sunt aranjate într-o ierarhie. Alte tipuri de arbori includ arbori AVL, roșu-negru, B etc. Nodurile arborelui binar conțin elementul de date și doi pointeri către fiecare nod copil.

Fiecare nod părinte dintr-un arbore binar poate avea maximum două noduri copil, iar fiecare nod copil, la rândul său, poate fi părinte pentru două noduri.

Legate de: Un ghid pentru începători pentru arbori binari

Un arbore de căutare binar (BST) stochează datele într-o ordine sortată, în care elementele cu o cheie-valoare mai mică decât cea părinte nodul sunt stocate în stânga, iar elementele cu o cheie-valoare mai mare decât nodul părinte sunt stocate în dreapta.

Arborii binari sunt frecvent întrebați în interviuri, așa că, dacă vă pregătiți pentru un interviu, ar trebui să știți cum să aplatizați un arbore binar, să căutați un anumit element și multe altele.

3. Tabel Hash

Tabelele hash sau hărțile hash sunt o structură de date extrem de eficientă care stochează datele într-un format de matrice. Fiecărui element de date i se atribuie o valoare de index unică într-un tabel hash, care permite căutarea și ștergerea eficientă.

Procesul de atribuire sau mapare a cheilor într-o hartă hash se numește hashing. Cu cât funcția hash este mai eficientă, cu atât eficiența tabelului hash în sine este mai bună.

Fiecare tabel hash stochează elemente de date într-o pereche valoare-index.

Unde valoare sunt datele care trebuie stocate, iar indexul este întregul unic utilizat pentru maparea elementului în tabel. Funcțiile hash pot fi foarte complexe sau foarte simple, în funcție de eficiența necesară a tabelului hash și de modul în care veți rezolva coliziunile.

Ciocnirile apar adesea atunci când o funcție hash produce aceeași mapare pentru elemente diferite; Coliziunile hărților hash pot fi rezolvate în diferite moduri, folosind adresarea deschisă sau înlănțuirea.

Tabelele hash sau hărțile hash au o varietate de aplicații diferite, inclusiv criptografia. Acestea sunt structura de date de prima alegere atunci când este necesară inserarea sau căutarea în timp constant O(1).

4. Stive

Stivele sunt una dintre structurile de date mai simple și sunt destul de ușor de stăpânit. O structură de date stivă este, în esență, orice stivă din viața reală (gândiți-vă la un teanc de cutii sau farfurii) și funcționează într-o manieră LIFO (Last In First Out).

Proprietatea LIFO a stivelor înseamnă că elementul pe care l-ați inserat ultimul va fi accesat primul. Nu puteți accesa elementele de sub elementul de sus dintr-o stivă fără a apărea elementele de deasupra acestuia.

Stivele au două operații principale — push și pop. Push este folosit pentru a introduce un element în stivă, iar pop elimină elementul cel mai de sus din stivă.

De asemenea, au o mulțime de aplicații utile, așa că este foarte obișnuit ca intervievatorii să pună întrebări legate de stive. A ști cum să inversezi o stivă și să evaluezi expresii este destul de esențial.

5. Cozile

Cozile sunt similare cu stivele, dar funcționează într-o manieră FIFO (First In First Out), ceea ce înseamnă că puteți accesa elementele pe care le-ați introdus mai devreme. Structura de date a cozii poate fi vizualizată ca orice coadă din viața reală, în care oamenii sunt poziționați în funcție de ordinea lor de sosire.

Operația de inserare a unei cozi se numește coadă, iar ștergerea/eliminarea unui element de la începutul cozii este denumită scoatere din coadă.

Legate de: Ghid pentru începători pentru înțelegerea cozilor și a cozilor prioritare

Cozile prioritare sunt o aplicație integrală a cozilor în multe aplicații vitale, cum ar fi programarea CPU. Într-o coadă de prioritate, elementele sunt ordonate în funcție de prioritatea lor, mai degrabă decât în ​​ordinea sosirii.

6. Grămezi

Mulțile sunt un tip de arbore binar în care nodurile sunt aranjate în ordine crescătoare sau descrescătoare. Într-un heap min, valoarea cheii părintelui este egală sau mai mică decât cea a copiilor săi, iar nodul rădăcină conține valoarea minimă a întregului heap.

În mod similar, nodul rădăcină al unui Heap maxim conține valoarea maximă a cheii a heap-ului; trebuie să păstrați proprietatea heap min/max în întregul heap.

Legate de: grămezi vs. Stacks: Ce îi deosebește?

Mulțile au o mulțime de aplicații datorită naturii lor foarte eficiente; în primul rând, cozile prioritare sunt adesea implementate prin grămezi. Ele sunt, de asemenea, o componentă de bază în algoritmii heapsort.

Aflați structurile de date

Structurile de date pot părea chinuitoare la început, dar dedică suficient timp și le vei găsi ușor.

Ele sunt o parte vitală a programării și aproape fiecare proiect vă va cere să le utilizați. Este esențial să știi ce structură de date este ideală pentru un anumit scenariu.

7 algoritmi pe care fiecare programator ar trebui să-i cunoască

Acești algoritmi sunt esențiali pentru fluxul de lucru al fiecărui programator.

Citiți în continuare

Despre autor