Datalogi · Gymnasiet 2 · Datastrukturer · 2.º Período

Listor och arrayer

Studie av linjära datastrukturer som arrayer och länkade listor. Eleverna undersöker hur data lagras i minnet och hur man itererar över dem.

Kort sammanfattning:Listor och arrayer är de mest grundläggande sätten att organisera data i datorns minne. I den här delen av kursen undersöker vi hur dessa strukturer skiljer sig åt tekniskt, särskilt när det gäller minnesallokering och åtkomsttid. Eleverna får lära sig att en array har en fast storlek och snabb åtkomst, medan länkade listor erbjuder flexibilitet på bekostnad av sökbarhet.

• Skolverket Kursplaner
• DAODAT0 - 1. Algoritmer och datastrukturer
• DAODAT0 - 3. Programkonstruktion

Om detta ämne

Listor och arrayer är de mest grundläggande sätten att organisera data i datorns minne. I den här delen av kursen undersöker vi hur dessa strukturer skiljer sig åt tekniskt, särskilt när det gäller minnesallokering och åtkomsttid. Eleverna får lära sig att en array har en fast storlek och snabb åtkomst, medan länkade listor erbjuder flexibilitet på bekostnad av sökbarhet.

Enligt Skolverkets kursplan ska eleverna kunna välja och använda lämpliga datastrukturer för att lösa problem. Genom att förstå hur data faktiskt lagras (sekventiellt i minnet kontra utspritt med pekare) får de en djupare förståelse för varför vissa operationer är dyrare än andra. Detta är avgörande för att kunna skriva effektiv kod i större projekt.

Konceptet landar bäst när eleverna får visualisera minnesadresser och pekare genom fysiska modeller eller samarbetsövningar där de agerar noder i en lista.

Nyckelfrågor

1. Vad är skillnaden mellan en array och en länkad lista?
2. Hur hanteras minnesallokering för listor?
3. När är en array det bästa valet?

Se upp för dessa missuppfattningar

Vanlig missuppfattning

Att listor i Python fungerar exakt som arrayer i C++ eller Java.

Vad man ska lära ut istället

Förklara att Python-listor är mer komplexa objekt (dynamiska arrayer). Genom att diskutera minneshantering på låg nivå förstår eleverna varför 'enkla' operationer ibland kan vara långsamma.

Vanlig missuppfattning

Att länkade listor alltid är bättre för att de kan växa.

Vad man ska lära ut istället

Visa att sökning i en länkad lista kräver att man går igenom varje element. Genom att jämföra 'indexering' i båda strukturerna ser eleverna arrayens fördel vid direktåtkomst.

Idéer för aktivt lärande

Simuleringsövning

Den mänskliga länkade listan

Varje elev agerar en 'nod' som håller ett värde och en lapp med namnet på nästa person i listan. Genom att fysiskt flytta på sig eller ändra sina lappar simulerar de hur element läggs till eller tas bort utan att flytta på hela gruppen.

25 min·Hela klassen

Utforskande cirkel

Array vs Lista

I små grupper får eleverna i uppdrag att implementera en enkel telefonbok. De ska testa att lägga till kontakter i mitten av en array respektive en länkad lista och räkna hur många 'steg' eller flyttar som krävs i varje fall.

40 min·Smågrupper

EPA (Enskilt-Par-Alla)

Minnespusslet

Eleverna får ett scenario där de ska lagra data för en sensor som skickar värden varje sekund. De diskuterar i par om en array eller en länkad lista är bäst lämpad baserat på hur datan ska användas och delas sedan med klassen.

15 min·Par

Vanliga frågor

Varför pratar vi om länkade listor när moderna språk hanterar allt automatiskt?

Att förstå länkade listor är grundläggande för att förstå hur mer avancerade strukturer som träd och grafer är uppbyggda. Det ger också en viktig insikt i hur pekare och minnesreferenser fungerar, vilket är centralt för att förstå systemarkitektur och prestanda.

Hur kan laborativt arbete hjälpa eleverna att förstå minnesallokering?

Genom att använda fysiska lådor eller rutat papper för att representera minnesadresser kan eleverna se hur en array kräver ett sammanhängande block, medan en länkad lista kan spridas ut. Denna visuella representation gör det tydligt varför det är svårt att förstora en array när minnet runt den redan är upptaget.

Vad är den viktigaste skillnaden eleverna bör ta med sig?

Skillnaden i tidskomplexitet för olika operationer. De bör veta att arrayer är snabba för läsning via index (O(1)), medan länkade listor är effektiva för insättning och borttagning i början av listan.

Hur kopplas detta till verklig mjukvaruutveckling?

Valet av datastruktur påverkar allt från batteritid i mobiler till svarstider på webbplatser. Genom att lära sig dessa grunder tränas eleverna i att göra professionella avvägningar som ingenjörer.