Post 3 — LinkedList

#

Læringsmål

#

De studerende kan efter aktiviteten…

• Forklare hvad en LinkedList er og hvordan den adskiller sig fra Array og ArrayList
• Bestemme kompleksiteten for opslag på index, søgning, indsættelse og sletning i en LinkedList
• Forklare forskellen mellem kompleksiteten for at finde et element og at udføre operationen

Forudsætninger

#

De studerende forventes at kende til:

• Begrebet kompleksitet og O-notation
• Post 1 og/eller Post 2 er en fordel men ikke et krav

Kort beskrivelse

#

Studerende stiller sig i en kæde med hænderne på hinandens skuldre — uden tal og uden fast placering. Kæden kan kun traverseres fra første person. Det gør opslag på index overraskende langsomt sammenlignet med Post 1 og 2, mens selve indsættelsen og sletningen er hurtig. Den centrale indsigt er at LinkedList har to omkostninger: at finde stedet (O(n)) og at udføre operationen (O(1)).

Faglig kontekst

#

• Semester/fag: 4. semester — Avanceret Programmering
• Holdstørrelse: 6–8 studerende pr. gruppe
• Organisering: Grupper — roterer mellem stationer

Trin-for-trin

#

1. Alle undtagen én tager en seddel med et tilfældigt ord.
2. De stiller sig i en række og lægger hænderne på skuldrene af personen foran sig.
3. Den sidste studerende er “programmøren”.
4. Gruppen gennemfører øvelse 1–4 i rækkefølge.
5. Efter hver øvelse udfylder alle svararket.

Materialer

#

• post3_instruktion.md — instruktionsark til gruppen (print ét pr. gruppe)
• post3_svar.md — svarark til den enkelte studerende (print ét pr. studerende)
• post3_svar_facit.md - udfyldt svarark til underviseren
• Sedler med tilfældige ord (ét ord pr. seddel. Et af ordene skal være “HUND”)
• Blyanter

Tidsforbrug

#

Ca. 15 min. pr. gruppe inkl. udfyldning af svarark.

Modtagelse

#

Udvidelser

#

• Diskuter i plenum: hvornår ville man vælge LinkedList frem for ArrayList?
• Hvad sker der hvis man altid tilføjer og sletter fra enden af listen?
• Man kan evt. lade være med at fortælle dem hvilken datastruktur der er tale om og lade dem selv finde ud af det senere.

Noter til underviseren

#

• Den vigtigste indsigt er at opslag på index er O(n) — ikke O(1) som i ArrayList. Lad dem selv opdage det.
• Svararket spørger separat til “finde stedet” og “udføre operationen” — det er bevidst. Mange forveksler de to.
• Første og sidste element er særtilfælde (O(1)) — lad dem tænke på det selv via svararket.
• Giv evt de studerende det udfyldte svarark til sidst til at tjekke deres egne svar med