Vad är en datastruktur?

En datastruktur är en metod för att organisera en uppsättning data. Strukturen definieras av hur data lagras och hur operationer, såsom datatillgång, infogning och radering, utförs på den lagrade datan. Datastrukturer är viktiga verktyg för programmerare, eftersom varje struktur har en uppsättning fördelar som gör det användbart för att lösa vissa typer av problem.

Länkade listor

Allmän uppfattning

En länkad lista består av en serie noder. Varje nod lagrar ett stycke data och en pekare som pekar på nästa nod i listan. Det finns två speciella pekare i listan:

  1. Huvudpekaren, detta pekar på den första noden i listan. Huvudpekaren är allt som behövs för att komma åt hela listan.
  2. En nollpekare, detta indikerar att listans slut har nåtts (Om huvudet är en nollpekare representerar detta en tom lista).

Eftersom pekare används för att länka informationen ihop, finns det inget krav på att listans data lagras sammanhängande i minnet.

Ett exempel länkade teckenlista som används för att lagra ordet "test". Data lagrade i en nod är blå färgade.

Genomförande

 mallklass LinkedList {public: LinkedList (): head {nullptr} {} ~ LinkedList () {while (head! = nullptr) {Node * föregående {head}; huvud = huvud-> nästa; radera tidigare; }} void Insert (const T data_in); T At (const int position) const; void Delete (const int position); privat: strukt Nod {T data; Nod * nästa; }; Nod * huvud; }; 

Ovanstående kod förklarar en malllänkad listklass i C ++. Den enda information som klassen direkt lagrar är en huvudpekare. Strukturen för listnoderna måste också deklareras (men detta kan flyttas ur klassen). Klassen innehåller medlemsfunktioner för att infoga en ny datamängd och få åtkomst till eller radera informationen på en viss plats i listan.

Konstruktören initialiserar bara huvudpekaren som en nollpekare, dvs. en ny lista börjar som en tom lista. Förstöraren är mycket viktigare. Den går över hela listan och frigör minnet som används för att lagra var och en av listans noder. Detta är avgörande eftersom nya listnoder skapas med dynamiskt tilldelat minne och därför behöver de omlokaliseras när listan förstörs.

Införande

 mall void LinkedList :: Insert (const T data_in) {Node * new_node {new Node}; new_node-> data = data_in; new_node-> next = head; head = new_node; } 

Ovanstående kod implementerar infogningsmetoden för vår länkade listklass. För det första fördelar det minne för att skapa en ny nod. Den ställer sedan in nodens data till användardata och ställer in noden så att den pekar på den aktuella listan. Listhuvudet ändras sedan för att peka på den nya noden.

Ett exempel på införande av tecknet 't' i en länkad lista som för närvarande lagrar ordet 'est'. Nya pekare är röda.

Denna insättningsmetod sätter in varje element från huvudläget. Att göra detta val leder till att insättningar är väldigt enkla och endast involverar tilldelning av pekare. Detta leder till införandet av skalningen som O (1), dvs insättningen är mycket snabb.

Åtkomst till data

 mall T LinkedList :: At (const int position) const {int current_position {0}; Nod * aktuell {head}; medan (nuvarande! = nullptr && nuvarande_position nästa; nuvarande_position ++;} om (nuvarande == nullptr) {/ * hanterar elementet som inte hittas eftersom positionen är utanför räckvidden * /} returnera nuvarande-> data;} 

Ovanstående kod implementerar metoden för att få åtkomst till data i vår länkade listaklass. Det skapar en lokal pekare för att lagra den aktuella noden och ett heltal som representerar den aktuella nodens position i listan. Den aktuella pekaren initialiseras till listhuvudet (som vi väljer att märka som 0: e position). Den flyttas sedan upprepade gånger till nästa nod. Detta slingras tills antingen användarens begärda position eller listans slut har nåtts. Om den aktuella pekaren hamnar som en nollpekare har användaren begärt en position som är utanför listans intervall och programmeraren måste välja hur hantera detta. Annars returnerar vi helt enkelt de data som den aktuella pekaren pekar på.

Det går snabbt att komma åt de första listans element, ungefär O (1). Men den allmänna åtkomsttiden skalas som O (n), där n är listans storlek. Detta beror på att listan måste korsas i följd (i ordning från början av listan). Detta gör att åtkomst till data i långa listor blir mycket långsam.

Radering

 mall void LinkedList :: Delete (const int position) {int current_position {0}; Nod * aktuell {head}; Nod * föregående {nullptr}; medan (nuvarande! = nullptr && nuvarande_position nästa; nuvarande_position ++;} om (nuvarande == nullptr) {/ * hanterar att elementpositionen är utanför räckvidden * /} if (position == 0) {head = head-> next; } annars {föregående-> nästa = nuvarande-> nästa;} ta bort nuvarande;} 

Ovanstående kod implementerar borttagningsmetoden för vår länkade listklass. Det liknar mycket den tidigare implementerade åtkomstmetoden. Den korsar listan på exakt samma sätt men lagrar också en pekare till den tidigare besökta noden. Den föregående noden ändras sedan för att peka på noden efter den aktuella noden (i grund och botten skär den aktuella noden ur listan). När huvudet raderas finns det ingen tidigare nod så huvudpekaren ändras istället. Den nuvarande noden raderas sedan från minnet.

Ett exempel på att radera karaktären 'e' från en länkad lista som för närvarande lagrar ordet 'test'. Den raderade noden kryssas ut tillsammans med tillhörande pekare. Observera hur den nya pekaren tilldelas för att återansluta listnoderna.

Tidseffektiviteten för borttagning är identisk med åtkomst till listelement. De första elementen är O (1) men i allmänhet är det O (n).

Fördelar och nackdelar

+ Den länkade listan är en dynamisk struktur. Det tillåter storleksändring vid körning och behöver inte initialiseras som en specifik storlek under kompileringstiden.

+ Insättning kan implementeras snabbt, oberoende av datastorleken.

+ Radering kan också implementeras snabbt om element togs bort från huvudet.

- Listan slösar bort lite minne genom att lagra en pekare längs varje datainsamling.

- Element måste nås i följd, mycket långsammare än slumpmässig åtkomst.

- Reversering (bakifrån och fram) av en länkad lista är mycket svår.

användningsområden

Liksom alla andra datastrukturer bör en länkad lista användas när dess attribut är lämpliga för problemet. Några exempel är:

  • För att lagra en historik över besökta webbsidor. Den senaste besökta webbsidan som läggs till högst upp i listan är vettig. Visning av historiken kräver naturligtvis att hela listan ska komma åt i följd.
  • Att lagra fienderna i ett videospel. Väsentliga operationer som kollisionskontroll måste utföras på hela fiendegruppen. Potentiella raderingar skulle också utföras som ett resultat av kollisionskontrollen. Därför är bristen på snabb slumpmässig åtkomst för specifika fiender inte ett problem.
  • För att implementera andra datastrukturer. Länkade listor kan användas som underliggande implementering av andra datastrukturer, såsom matriser med varierande storlek, staplar och köer.
  • Länkade listor används ofta för att lösa kollisioner i hashtabeller.

Dubbel länkad lista

En dubbel länkad lista innehåller noder som också lagrar en pekare till föregående nod. Detta avlägsnar svårigheten med omvänd traversering, till kostnaden för att lagra en extra pekare i varje nod. Dubbelbundna listor lagrar också vanligtvis en svanspekare som pekar på det sista elementet i listan. En svanspekare gör det möjligt att snabbt införa eller radera element från svansen.

Cirkulär länkad lista

Cirkulärt länkade listor skapas genom att ha en nod som pekar tillbaka till en tidigare listnod (skapar en cirkulär slinga). Detta innebär att listan kan korsas fullständigt genom att starta från vilken nod som helst, inte bara huvudet som för en linjär länkad lista. Cirkulära länkade listor är användbara för applikationer där listan måste gå igenom upprepade gånger.

Ett exempel cirkulärt länkad lista över koordinatpunkter, som används för att lagra topparna i en triangel.

Testa din kunskap

visa frågesportstatistik

Alternativa datastrukturer

  • arrayer
  • Staplar och köer
  • träd