Linked List

Linked List

Linked List  är en dynamisk datastruktur som används inom programmering. Att den är dynamisk innebär att den enkelt kan öka och minska i storlek efter behov, till skillnad från till exempel en array, som har en fix storlek. I en länkad lista kan även element läggas till och tas bort i mitten. I detta fall så skapas en lista med noder som har en pekare till nästa nod. Alltså, första noden vet vilken andra noden är, andra noden vet vilket tredje noden är och så vidare. Det finns två typer av Linked List; Single Linked List och Double Linked List. I en Double Linked List vet noden även om vilket nod som är innan. Alltså, den tredje noden vet vilket den andra noden är och andra noden vet vilken den första noden är.

Uppgift 1 gick delvis ut på att man ska skapa en egen Linked List och jag har valt att göra Single Linked List.

Till en början skapar jag en struct som har två variabler, ett värde och en pekare till nästa nod. Med dem två har man allt man behöver till att skapa en Single Linked List. Utanför structen så skapar jag en nod som jag döper till m_root som kommer bli den första noden i listan.

Det första jag gör när programmet ska starta är att i konstruktorn så sätter jag m_root till nullptr för att undvika diverse felmeddelande och så att jag vet att den pekar på null. Till Linked List fanns det krav om metoder man behövde ha med som är ”Push Front, Push Back, Pop Front, Pop Back, Clear, Find, Size”.

 

Jag började med att göra Push Back, som är att varje gång du lägger till en nod så ska den läggas längst bak i listan. Det som händer när man använder metoden är att användaren skriver in ett värde på noden och ifall m_root fortfarande pekar på nullptr så får m_root värdet som användaren skickade in. Men ifall m_root redan pekar på något så skapar koden först en temporär nod som får samma värde som första noden. Sen går koden in i en loop som är att så länge den temporära noden inte är nullptr så sätts den temporära nodens värde till nästa nods värde. Den går ur loopen när den pekar på nullptr, för då vet koden att den är på sista platsen i listan. Nodens värde sätts då till det värde som användaren skickade in.

Push Front är som Push Back fast istället för att noden ska lägga sig sist i listan så ska den lägga sig först. Push Front börjar likadant som Push Back, den kollar ifall m_root är null eller om den redan har ett värde. Ifall den är null, så sätts noden till det värde som användaren skickar in. Men om m_root redan har ett värde så sätts den nya nodens nästa nod till m_root’s nästa nod. Sen sätts m_root’s nästa nod till den noden som användaren skickar in. Sen sätts den nya nodens värde till m_root’s värde och efter så sätts m_root’s värde till det nya värdet. Alltså, om koden har tre noder och en fjärde nod ska läggas till, så sätts den fjärde nodens värden till första nodens värden och första nodens värden sätts till de nya värdena och pekar sen på fjärde noden.

Pop Front är motsatsen till Push Front. Pop Front tar bort den första noden i listan. Hur den fungerar är att den skapar en temporär nod som sätts till den andra noden, sen sätts den första noden till samma värde som den temporära och efter det så sätts den temporära till nullptr och förstörs med delete.

Pop Back är motsatsen till Push Back, den tar bort den sista i listan istället för att lägga till. Den funkar nästan likadant, den skapar en temporär som får samma värde som m_root. Om temporära inte är nullptr så går den in i en loop som fungerar att så länge den temporära nodens nästa nods nästa nod inte är nullptr så får den temporära den nästa nods värde. När nästa nodens nästa nod är nullptr så vet vi att nästa nod är den sista i listan och då sätts den till nullptr och raderas.

Clear är en metod som ska rensa hela listan. Den fungerar så att den skapar två temporära noder som döps till ”current” för nuvarande nod och ”temp” för temporära noden. Det första som händer är att den sätter ”temp” till samma värden som m_root. Koden går in i en loop som pågår så länge ”temp” nodens nästa nod inte är nullptr så ska den köra. Det som händer i loopen är att ”current” får samma värden som ”temp”, ”temp” får ”currents” nästa nods värden. ”Current” raderas och sätts till nullptr, sen börjar loopen om. Sista som händer är att m_root sätts till nullptr och raderas.

Find är en metod för att kolla ifall listan har ett specifikt nummer som användaren skickat in. Användaren får skicka in det värde den vill kolla ifall det finns till koden och det som händer i metoden är att det först skapas en temporär nod som får samma värde som m_root. Sen går den in i en loop som pågår så länge nodens värde inte är samma värde som värdet som användaren skickade in eller att noden inte pekar på nullptr. I loopen sätts den temporära noden till nästa nods värde. Om värdet användaren skickade in är samma som en nods värde så skriver koden ut i konsolen det värdet och ”Was found”. Om värderna inte är samma så skriver koden ut i konsolen ”Could not find that node”.

Size är en metod som berättar för användaren hur många noder det finns i listan. Den fungerar så att den först skapar en temporär nod som får samma värde som m_root. Sen går metoden in i en loop med en variabel av typen int blir plus ett för varje gång den temporära nodens nästa nod inte är nullptr. Loopen pågår tills den temporära nodens nästa nod är nullptr. När loopen är klar skriver koden ut i konsolen vad int variabeln blev.