Lister, dictionaries, sets

Programmering B · HTX · B-niveau · Datastrukturer og algoritmer

💻 Datastrukturer

De rette datastrukturer gør koden hurtig og læselig.

Liste (Array)

• Ordnet samling af elementer
• Adgang via index O(1)
• Indsætning/sletning i midten O(n)
• Python: [1, 2, 3]
• JavaScript: [1, 2, 3]
• Anvendelse: når rækkefølge betyder noget

Dictionary (Hash map / Object)

• Key-value-par
• Lookup O(1) gennemsnitligt
• Python: {"navn": "Alice", "alder": 25}
• JavaScript: {navn: "Alice", alder: 25}
• Anvendelse: hurtigt opslag, JSON-data

Set

• Unikke elementer, ingen rækkefølge
• Lookup, add, remove alle O(1)
• Python: {1, 2, 3}
• JavaScript: new Set([1, 2, 3])
• Anvendelse: fjern duplikater, mængdeoperationer (union, intersection)

Tuple (Python)

• Uforanderlig liste
• Python: (1, 2, 3)
• Anvendelse: data der ikke ændrer sig (koordinater)

Eksempler

```python

Liste — alle elever (rækkefølge)

elever = ["Anna", "Bob", "Cecilie"]

Dictionary — opslag på navn

karakterer = {"Anna": 10, "Bob": 7, "Cecilie": 12}

Set — unikke fag

fag_taget = {"Dansk", "Matematik", "Dansk"} # bliver {"Dansk", "Matematik"}

Tuple — fast struktur

lokation = (55.6761, 12.5683) # København koordinater

```

Performance-sammenligning

| Operation | Liste | Dictionary | Set |

|---|---|---|---|

| Lookup | O(n) | O(1) | O(1) |

| Add | O(1) | O(1) | O(1) |

| Delete | O(n) | O(1) | O(1) |

Big-O notation

• O(1): konstant tid (uanset størrelse)
• O(log n): logaritmisk (binær søgning)
• O(n): lineær (gå gennem en liste)
• O(n²): kvadratisk (nested loops)
• O(2ⁿ): eksponentiel (rekursive problemer)

Læringsmål

• Vælge passende datastruktur til problemet
• Forstå tids-kompleksitet (Big-O)
• Bruge dictionary-lookup i stedet for liste-søgning
• Anvende sets til at fjerne duplikater

Sådan kan du arbejde med emnet

• Skriv kode, der opretter en liste af navne og udskriver dem i alfabetisk orden
• Forklar hvornår man bruger en dictionary i stedet for en liste, med et eksempel
• Beskriv hvad der kendetegner et set, og hvordan det adskiller sig fra en liste

Træningsforslag

• Implementér en simpel "kontaktbog" med dictionary
• Sammenlign tid for liste-søgning vs. dictionary-lookup
• Læs "Grokking Algorithms" af Aditya Bhargava