Att göra en (Enkel)Länkad Lista i PHP - Version 0.1
Skriven av Filip Ekberg 2006 frw@frw.se
För er alla där ute som undrar hur man skapar en länkad lista, så tänker jag nu gå igenom det. Detta kräver dock
att ni sedan tidigare, har lite programmeringskunskaper.
Kod och text får gärna användas i utlärningssyfte.
Struktur
Dokumentet kommer att vara uppbyggt på följande vis
Förord
Denna texten är deddikerad till min klass och även till alla de andra där ute på nätet som vill ha hjälp att skapa
en länkad lista i PHP. Sjävlfallet kan denna användas som undervisningsmaterial i och med att jag tagit en del av
materialet från min kursliteratur.
Jag hoppas att denna guiden kommer vara till stor nytta och i framtiden även översatt till engelska så att fler personer
kan ta del av den!
Lycka till!
Sektion 1 - Grundläggande förklaring av länkade listor
Först och främst, Vad är en länkad lista?. Tänk dig att detta är en lista med Namn, först i varje lista har vi en Head, denna säga till att "Här startar vår lista".
I slutet av varje Lista vill vi ha en svans, denna kallar vi Tail. Mellan dessa två skapar vi våra Noder också kallade index/possitioner. I våra Noder kan vi då lagra data,
t.ex. ett objekt, en sträng eller dylikt. Ungefär såhär kan en lista se ut:
( Head ) => ( Node 1 ) => ( Node 2 ) => ( Tail ) , sedan så har även Tail'en en pekare, fast mot sig själv! Det är massa nya ord på gång nu men jag ska försöka förklara de under tiden!
Först och främst, en referens / pekare är något som visar oss vägen till något annat. Tänk dig t.ex. en vägskylt mot Göteborg, denna är en Pekare eller en Referens för vart du ska köra för att kommma
mot rätt håll!
Det jag försökt visualisera ovan är alltså, vår Head ( som för övrigt också är en Node, men denna är reserverad som Head! ) har bara en Attribut. Den ska peka mot vår första Node som vi lagt in! För övrigt
så kommer alla Noder innehålla 2 attributer. Första attributen är, Var finns nästa node? andra är, Vad innehåller noden?.
Alltså, för att raskt svara på den första frågan, Vad är en länkad lista?
Det är en "Lista" som innehåller data.
Då tänker du klart, jag kan väl lika gärna använda mig av arrayer? Visst kan du det, men vi vill väl inte göra det så enkelt för oss?
Det finns många fördelar med att använda en länkad lista, just i PHP har det ingen större funktion på grund av funktioner som finns för att hantera arrayer på ett mycket fint och dynamiskt vis.
Men på mer lågnivå-programmering så får man oftast skriva sånna här saker själv och då är PHP ett bra språk att öva i!
Om du tar en snabb titt på detta ( Head ) => ( Node 1 ) => ( Node 2 ) => ( Tail ) igen så ska jag fortsätta förklara.
En länkad-lista är så att säga, Dynamisk. Med detta menar jag att du kan skapa en lista utan att definiera hur många rum det finns i den ( alltså hur många noder som får plats ).
Om du är van vid t.ex. Java eller liknande språk så vet du att man får sätta in hur stor man vill att sin lista ska vara.
Dynamik? Kanske du frågar dig! Nu kommer en liten snabb förklaring av hur du kan ta bort och få in nya Noder.
Ta nu en titt igen på ( Head ) => ( Node 1 ) => ( Node 2 ) => ( Tail ) . Sådär ser vår lista ut för tillfället, tänk dig då att vi har en lista med namn.
Node 2 innehåller namnet Bertil som vi nu vill ta bort! Hur ska vi då göra? Jo! Vi börjar med att kolla, Vilken Node pekar på Node 2? När vi väl hittat att det är
Node 1, så säger vi, Node 1, kan du vara snäll att peka på det Node 2 pekar på? Då kommer listan att se ut såhär:
( Head ) => ( Node 1 ) => ( Tail )
Vi har alltså blivit av med ( Node 2 ).
Om vi då ska trycka in ett nytt objekt. Nu kommer vår Head node till användning. Vi har ju nu en Lista som ser ut på följande vis:
( Head ) => ( Node 1 ) => ( Tail )
Vi vill då först och främst fråga Head, vart pekar du? Sedan så gör vi en Ny Node och säger, va snäll och peka på det som Head pekar på. Sedan säger vi åt Head att peka på den Nya Noden.
Då har vi en lista som ser ut på följande vis:
( Head ) => ( Node 3 ) => ( Node 1 ) => ( Tail )
Man kan även arbeta med Dubbel-länkade listor, men detta kommer jag inte att gå igenom.
Summering
Under denna sektionen har vi alltså fått förståelse över att en Länkad lista är en Lista som innehåller länkad information. Exempel på detta är en lista med namn,
tänk dig att du vill kunna ha ett papper, fyllt med namn, men när en person inte längre är aktuell så vill du sudda ut hans namn men inte ha en tom position? Detta löser du fint med en länkad lista!
Vi har även fått förståelse i teorin över hur du en länkad lista är strukturerar och hur det ser ut om du tar bort eller lägger till en lista.
Sektion 2 - Strukturera din kod med OOP
Det är viktigt att du har koll på vad OOP är, är du inte van vid förkortningen? Object Oriented Programming. Vi ska under guiden använda oss av
objekt orienterad programmering.
Först och främst, starta upp ett nytt PHP dokuement, se till att din server kör PHP5 och att allt annat är fixat innan vi sätter igång!
Det första och viktigaste är att vi får igång våra Noder, så att vi vet att vi kan lägga till och ta bort dessa.
För att skapa en Node behöver vi en mall för detta också kallat en Klass. Innanför dina PHP-taggar skriver du följande:
class Node
{
public $Next_Node;
public $Obj_info;
}
Nu har vi gjort en mall för våra Node objekt! Vi ser här att Noden har 2 attributer, första är att den kan peka på nästa Node och den andra är att
den innehåller någon form at Objekt information, detta kan vara en sträng, en lista, ett objekt eller dylikt!
Vårat nästa steg är att länka ihop skapade noder och samla de på samma ställe.
Så vad jag föreslår är att vi skapar oss en mall över hur själva listan är uppbyggd.
Till att börja med, vi vill alltid att Headern och Tailen ska vara lättillgängliga, så vi gör de publika i vår klass LinkedList.
Lägg koden under Node klassen.
class LinkedList
{
public $Head;
public $Tail;
Efter detta så vill vi självklart att så fort vi initierar ett objekt av klassen så ska det skapas en lista åt oss, denna listan kommer vara "tom" alltså enbart innehålla en
header och en tail. Detta löser vi med hjälp av en konstruktör!
public function __construct()
{
$this->Head = new Node();
$this->Tail = new Node();
$this->Head->Next_Node = $this->Tail;
$this->Tail->Next_Node = $this->Tail;
}
Denna koden betyder alltså, skapa en ny Node på den publika variablen Head och skapa en ny Node på den publika variablen Tail.
Efter detta ser vi till att följa modellen som jag ritade upp i början ( Head ) => ( Tail ) <= , detta är en version av de jag ritade upp. Detta betyder alltså,
Head pekar på Tail, och Tail pekar på sig själv. Du kan nu kolla, ifall den noden du står på är sista i listan genom att kolla, är Next_Node samma som Tail?
Nu skulle det ju även vara fint då om vi kan stoppa in lite information i vår lista, tänk nu såhär, Detta är gjort:
-
En mall för Noder
-
En platts att lagra våra Noder på, alltså vår LinkedList klass
Det som då nu är kvar att göra är följand:
-
Lägg till Noder
-
Sök upp Noder
Vi tar en titt över hur man lägger till noder, detta är en funktion som ska finnas inne i LinkedList klassen.
public function add_node($Obj_info)
{
$_tmp_node = new Node();
$_tmp_node->Next_Node = $this->Head->Next_Node;
$_tmp_node->Obj_info = $Obj_info;
$this->Head->Next_Node = $_tmp_node;
}
Okej, vi fortsätter med att förklara hur funktionen fungear. Som du ser kräver funktionen en typ av indata, detta kan som sagt
då varierar beroende på vad det är du vill att din node ska lagra.
För min del kommer den att lagra strängar.
Om vi då tar en titt på hur klassen startar, vi skapar en ny Temporär variabel som vi gör till ett Node objekt.
Vi säger sedan att denna nya Noden ska peka på vad Head pekar på. På detta viset så blir vi inte relations-lösa.
Ta en titt på följande exempel och försök lista ut vad skillnaden är:
( Head ) => ( Node 1 ) => ( Node 2 ) => ( Tail )
Vad händer nu om vi stoppar in en ny Node och säger, Head, kan du vara snäll och peka på den nya Noden!
Hur vet vi nu då vilken vår nya node ska peka på? Om ingen annan pekar på den?
Istället så ber vi Head om att få veta vem den pekar på och sedan ber vi Head att peka på oss, då har vi stoppat in en ny Node i listan!
Vad vi sedan gör är att tilldela den nya Noden vår indata, alltså i detta fallet strängen som vi skickar in.
Till slut så säger vi att Head:ens nästa position är den nya Noden. För vår nya Node pekar redan på fortsättningen i listan.
Nu kommer vi till funktionen där vi ska leta upp en position i listan. Ta en titt på följande kod:
public function getNodeAt($pos)
{
if (is_int($pos) )
{
$_tmp_node = $this->Head;
for( $i = 0; $i < $pos; $i ++ )
$_tmp_node = $_tmp_node->Next_Node;
return $_tmp_node;
}
}
}
Jag kan bara snabbt säga att alla kod-snuttar hänger ihop, så glöm inga } eller dylikt, då kommer det bli stora problem!
Om du tar en titt på vad vi vill ha för att köra funktionen, så ser du att vi självklart vill ha en position.
När vi kollat att det är en int, så går vi igenom listan, Node för Node och kollar om det är rätt Node.
Vi måste hela tiden säga tt får Temporära Node är lika med vad vår Aktuella Node pekar på. När vi har kört så långt i listan som vi vill
så kommer den att stoppa.
Denna kommer inte att räkna med Head eller Tail!
Summering
Vi har nu gått igenom hur man kod-messigt skapar en länkad lista, vi har även förklarat alla detaljer som behövs för att
förstå strukturen av en länkad lista. Du borde nu vara kvalificerad till att skapa en lista och matta in och plocka ut data.
Om det är något du inte förstått så försök att läsa en gång till och om det fortfarande är helt oklart så skicka ett mail till mig.
Sektion 3 - Få liv i din lista
Nu har du kommit så långt att du borde förstå grunderna i hur en länkad lista fungerar och vad det är, men för att du ska bli ännu bättre så tänkte jag gå igenom lite vad skillnanden mellan en
Länkad lista och en Array är.
Du har säkerligen funderat över, varför ska jag använda mig av en länkad lista när jag kan mycket snabbare använda mig av
en array?
Som jag nämnde tidigare i denna guiden så är detta en "vägledning" för att du ska förstå dig på mer avancerad programmering och även en del minneshantering.
I många andra språk som C och C++ får du allokera upp det minne som din array MAX ska ta. Men med en Länkad lista behöver du inte detta för här kan du dynamiskt skapa
och ta bort Noder.
Visst går det slöare än en array, men lite tid kan man kompromissa med om det bara ger dig en mer effektivitet. Om det är något
som önskas ska förklaras närmare så tveka inte att skicka förslag till mig via min mail som är listad på toppen av sidan!
Vi ska ta en titt på hur du fyller din lista, ta en titt på följande kod:
$List = new LinkedList();
$List->add_node("Obj_1");
$List->add_node("Obj_2");
$List->add_node("Obj_3");
$Node = $List->Head->Next_Node;
echo $List->getNodeAt(2)->Obj_info;
Först initierar vi en Lista, i vår länkade lista vill vi såklart stoppa in Noder, vi stoppar alltså in 3 nya Noder med 3 olika värden. I detta fallet är de strängar.
Vår lista ser alltså ut såhär:
( Head ) => ( Node 1 = "Obj_3" ) => ( Node 2 = "Obj_2" ) => ( Node 3 = "Obj_1" ) => ( Tail )
Våra element blir alltså inlaggda i fel ordning, hur kommer det sig? Jo! Som jag förklarade innan så lägs varje ny node in efter Headen.
Efter att vi lagt in alla våra Noder vi vill ha, så testar vi att säga att vår variabel $Node innehåller första noden i listan, detta är för att vi vill inte räkna med Head när vi söker i Listan.
Vi hämtar sedan Obj_info från noden på plats 2, i detta fallet blir resultatet Obj_2, hade vi skrivit 1 där, så hade det resulterat Obj_3.
Summering
Du borde nu ha fått en hel del kött på benen för att kunna arbeta med Länkade listor, jag hoppas att det har varit intressant läsning och att du kommer referera alla dina vänner hit!
Uppgift
Du borde nu klara av att skapa en funktion i LinkedList klassen som tar bort en Node och pekar om listan. Alternativt är att du skapar en dubbel-länkad lista. I teorin
skulle den se ut såhär:
( Head ) <=> ( Node 1 ) <=> ( Node 2 ) <=> ( Tail )
När du gjort det får du gärna maila mig och visa ditt resultat!