# 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.

 

![](https://3459450691-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MHmNgpRz-b16wpwGwZI%2F-MILSXMq47IUxVwcbOff%2F-MILVckt7rr3e_whb7wS%2Fimage.png?alt=media\&token=79c0b90c-e5b0-4b69-82de-872f2d9fa21e)

{% code title="Node.cs" %}

```csharp
class Node
{
  public int value = 0; // Kan såklart göras generisk för mer flexibilitet.
  public Node nextNode;
}
```

{% endcode %}

{% code title="Program.cs" %}

```csharp
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;
```

{% endcode %}

## 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

![En tvåvägs länkad lista](https://3459450691-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MHmNgpRz-b16wpwGwZI%2F-MILSXMq47IUxVwcbOff%2F-MILWD7k57Cx92Eb8lkg%2Fimage.png?alt=media\&token=45309480-0bd2-476c-bc3f-df55286baa4a)

{% code title="Node.cs" %}

```csharp
class Node
{
  public int value = 0;
  public Node nextNode;
  public Node prevNode;
}
```

{% endcode %}

### Träd

![](https://3459450691-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MHmNgpRz-b16wpwGwZI%2F-MILSXMq47IUxVwcbOff%2F-MILWMUk6QAe6ow7MnAR%2Fimage.png?alt=media\&token=00b147fc-2e9f-4e36-bd48-55204f152efb)

{% code title="Node.cs" %}

```csharp
class Node
{
  public int value = 0;
  public List<Node> children = new List<Node>();
}
```

{% endcode %}

### Nätverk

![](https://3459450691-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MHmNgpRz-b16wpwGwZI%2F-MILSXMq47IUxVwcbOff%2F-MILWQYO8CiCeRrATDcT%2Fimage.png?alt=media\&token=2babc59d-4ac5-441c-add0-5052f1446614)

{% code title="Node.cs" %}

```csharp
class Node
{
  public int value = 0;
  public List<Node> connections = new List<Node>();
}
```

{% endcode %}