Linkede lister (simpel og dobbelt)
Kommunikation og IT A · HTX · A-niveau · Datastrukturer og algoritmer
💻 Linkede lister
En linket liste er en kæde af noder, hvor hver node indeholder data og en pointer til næste node.
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None # pointer til næste node
class LinketListe:
def __init__(self):
self.hoved = None
def tilføj(self, data):
ny = Node(data)
if not self.hoved:
self.hoved = ny
return
nuværende = self.hoved
while nuværende.next:
nuværende = nuværende.next
nuværende.next = ny
```
Simpel linket liste: hver node peger kun fremad.
Dobbelt linket liste: hver node peger både fremad (next) og bagud (prev) — hurtigere sletning.
Tids-kompleksitet: Indsæt ved hoved O(1), søgning O(n), sletning O(n) (for at finde elementet).
Fordel vs. Array: indsæt/slet i midten er O(1) (når noden kendes) vs. O(n) for array.
Læringsmål
- Implementere simpel linket liste med tilføj, fjern og søg
- Forklare forskellen på simpel og dobbelt linket liste
- Analysere tids-kompleksiteten og sammenligne med array
- Implementere reverse af en linket liste
Sådan kan du arbejde med emnet
- Tegn en simpel linket liste med fire elementer og vis hvordan et nyt element indsættes i midten
- Forklar fordele og ulemper ved linkede lister sammenlignet med arrays
- Implementer en funktion der finder længden af en linket liste
Træningsforslag
- Implementér en dobbelt linket liste fra bunden
- Byg en "browser-historik" med dobbelt linket liste
- Løs LeetCode #206 (Reverse Linked List)
Øv dette emne med AI — quizzer, forklaringer og feedback tilpasset dit niveau.
Prøv Fagportalen gratis