6 datastrukturer som alla programmerare bör känna till

Vägen till att bli en skicklig och framgångsrik programmerare är svår, men en som verkligen är möjlig. Datastrukturer är en kärnkomponent som varje programmeringsstudent måste behärska, och chansen är stor att du redan har lärt dig eller arbetat med några grundläggande datastrukturer som arrayer eller listor.

Intervjuare tenderar att föredra att ställa frågor relaterade till datastrukturer, så om du förbereder dig för en anställningsintervju kommer du att behöva fräscha upp dina kunskaper om datastrukturer. Läs vidare när vi listar de viktigaste datastrukturerna för programmerare och anställningsintervjuer.

Länkade listor är en av de mest grundläggande datastrukturerna och ofta utgångspunkten för studenter i de flesta datastrukturkurser. Länkade listor är linjära datastrukturer som tillåter åtkomst till sekventiell data.

Element i den länkade listan lagras i individuella noder som är anslutna (länkade) med hjälp av pekare. Du kan tänka på en länkad lista som en kedja av noder kopplade till varandra via olika pekare.

Relaterad: En introduktion till att använda länkade listor i Java

Innan vi går in på detaljerna för de olika typerna av länkade listor är det avgörande att förstå strukturen och implementeringen av den enskilda noden. Varje nod i en länkad lista har minst en pekare (dubbellänkade listnoder har två pekare) som kopplar den till nästa nod i listan och själva dataobjektet.

Varje länkad lista har en huvud- och svansnod. Enkellänkade listnoder har bara en pekare som pekar på nästa nod i kedjan. Förutom nästa pekare har dubbellänkade listnoder ytterligare en pekare som pekar på föregående nod i kedjan.

Intervjufrågor relaterade till länkade listor kretsar vanligtvis kring infogning, sökning eller radering av ett specifikt element. Att infoga i en länkad lista tar O(1) tid, men radering och sökning kan ta O(n) tid i värsta fall. Så länkade listor är inte idealiska.

2. Binärt träd

Binära träd är den mest populära delmängden av trädfamiljens datastruktur; element i ett binärt träd är ordnade i en hierarki. Andra typer av träd inkluderar AVL, röd-svart, B-träd, etc. Noder i det binära trädet innehåller dataelementet och två pekare till varje underordnad nod.

Varje föräldernod i ett binärt träd kan ha maximalt två underordnade noder, och varje undernod kan i sin tur vara en förälder till två noder.

Relaterad: En nybörjarguide till binära träd

Ett binärt sökträd (BST) lagrar data i en sorterad ordning, där element med ett nyckel-värde mindre än det överordnade noden lagras till vänster, och element med ett nyckel-värde som är större än föräldernoden lagras på höger.

Binära träd är ofta frågade i intervjuer, så om du gör dig redo för en intervju bör du veta hur du plattar ut ett binärt träd, slår upp ett specifikt element och mer.

3. Hash tabell

Hash-tabeller eller hash-kartor är en mycket effektiv datastruktur som lagrar data i ett matrisformat. Varje dataelement tilldelas ett unikt indexvärde i en hashtabell, vilket möjliggör effektiv sökning och radering.

Processen att tilldela eller mappa nycklar i en hashkarta kallas hashing. Ju effektivare hash-funktionen är, desto bättre effektivitet har själva hashtabellen.

Varje hashtabell lagrar dataelement i ett värdeindexpar.

Där värde är data som ska lagras och index är det unika heltal som används för att mappa elementet i tabellen. Hashfunktioner kan vara mycket komplexa eller mycket enkla, beroende på vilken effektivitet som krävs för hashtabellen och hur du kommer att lösa kollisioner.

Kollisioner uppstår ofta när en hashfunktion producerar samma mappning för olika element; hashkartakollisioner kan lösas på olika sätt, med öppen adressering eller kedja.

Hashtabeller eller hashkartor har en mängd olika applikationer, inklusive kryptografi. De är förstahandsvalets datastruktur när infogning eller sökning i konstant O(1)-tid krävs.

4. Stackar

Stackar är en av de enklare datastrukturerna och är ganska lätta att bemästra. En stackdatastruktur är i princip vilken som helst stack i verkligheten (tänk på en bunt lådor eller plåtar) och fungerar på ett LIFO-sätt (Last In First Out).

Stacks LIFO-egenskap betyder att elementet du infogade senast kommer att nås först. Du kan inte komma åt element under det översta elementet i en stack utan att poppa elementen ovanför det.

Stackar har två primära funktioner - push och pop. Push används för att infoga ett element i stapeln, och pop tar bort det översta elementet från stapeln.

De har också massor av användbara applikationer, så det är väldigt vanligt att intervjuare ställer frågor relaterade till stackar. Att veta hur man vänder en stack och utvärderar uttryck är ganska viktigt.

5. Köer

Köer liknar stackar men fungerar på ett FIFO-sätt (First In First Out), vilket innebär att du kan komma åt de element som du infogade tidigare. Ködatastrukturen kan visualiseras som vilken verklig kö som helst, där människor placeras baserat på deras ankomstordning.

Att infoga en kö kallas för enqueue, och att ta bort/ta bort ett element från början av kön kallas för att ta bort en kö.

Relaterad: En nybörjarguide för att förstå köer och prioriterade köer

Prioritetsköer är en integrerad tillämpning av köer i många viktiga applikationer som CPU-schemaläggning. I en prioriterad kö ordnas element enligt deras prioritet snarare än ankomstordningen.

6. Högar

Högar är en typ av binärt träd där noder är ordnade i stigande eller fallande ordning. I en Min Heap är nyckelvärdet för föräldern lika med eller mindre än dess underordnade värde, och rotnoden innehåller minimivärdet för hela högen.

På liknande sätt innehåller rotnoden för en Max Heap det maximala nyckelvärdet för högen; du måste behålla min/max heap-egenskapen under hela heapen.

Relaterad: Högar vs. Stacks: Vad skiljer dem åt?

Högar har många användningsområden på grund av sin mycket effektiva natur; i första hand implementeras prioriterade köer ofta genom heaps. De är också en kärnkomponent i heapsort-algoritmer.

Lär dig datastrukturer

Datastrukturer kan verka upprörande till en början men ägna tillräckligt med tid, och du kommer att finna dem lätta som en plätt.

De är en viktig del av programmering, och nästan varje projekt kräver att du använder dem. Att veta vilken datastruktur som är idealisk för ett givet scenario är avgörande.

7 algoritmer som alla programmerare bör känna till

Dessa algoritmer är viktiga för varje programmerares arbetsflöde.

Läs Nästa

Om författaren