Länkade listor och andra strukturer
Länkade listor
Fördelar med en länkad lista jämfört med arrayer:
Som en List behöver man inte definiera storleken från början.
Det går ganska snabbt att lägga in något nytt i mitten, eller ta bort det.
Förstår man länkade listor så blir det väldigt lätt att sedan skapa andra strukturer såsom träd eller nätverk.
Nackdelar:
Mycket jobbiga att sortera.
Jobbigt att läsa av en specifik position.
Hur det funkar
En länkad lista består av noder. Varje nod innehåller (minst) ett värde samt en pekare till nästa nod. Det finns ingen samling av alla noder någonstans; allt som finns är pekaren från en nod till en annan.
class Node
{
public int value = 0; // Kan såklart göras generisk för mer flexibilitet.
public Node nextNode;
}Node firstNode = new Node();
firstNode.value = 3;
Node currentNode = firstNode;
// Lägg till 10 noder till den länkade listan
for (int i = 0; i < 10; i++)
{
firstNode.nextNode = new Node();
currentNode = firstNode.nextNode;
currentNode.value = 10 - i;
}
// Stoppa in en nod mellan den första och den andra
Node newNode = new Node();
newNode.value = 9;
newNode.nextNode = firstNode.nextNode;
firstNode.nextNode = newNode;Tvåvägs länkade listor, träd och nätverk
Flera pekare kan peka på samma objekt. Det gör att man kan skapa mer komplexa strukturer.
Tvåvägs
class Node
{
public int value = 0;
public Node nextNode;
public Node prevNode;
}Träd
class Node
{
public int value = 0;
public List<Node> children = new List<Node>();
}Nätverk
class Node
{
public int value = 0;
public List<Node> connections = new List<Node>();
}Last updated
Was this helpful?