Array (datastruktur) – definition, index, storlek och typer
Lär dig vad en array är: definition, indexering (0- eller 1-baserad), storlek, begränsningar och vanliga typer i programmering — praktiska exempel och tydliga förklaringar.
I programmeringsspråk är en array en datastruktur som används för att lagra flera element av samma typ, till exempel heltal eller strängar. Varje plats i arrayen innehåller ett element och har ett unikt nummer som kallas index. Genom indexet kan programmeraren snabbt läsa eller skriva ett visst element.
Grundläggande egenskaper
- Homogenitet: Alla element i en array har samma datatyp (t.ex. bara heltal eller bara strängar).
- Kontinuerligt minne: Många implementationsmodeller lägger elementen i intilliggande minnesceller vilket gör direkt åtkomst möjlig.
- Fast eller dynamisk storlek: I vissa språk är arrayens storlek bestämd när den skapas och kan inte ändras utan att skapa en ny array. Andra språk erbjuder dynamiska varianter (t.ex. vektorer, listor) som kan växa.
Indexering
Index börjar i regel antingen vid 0 eller vid 1 beroende på språket:
- Index från 0: Det vanligaste i språk som C, C++ och Java — det första elementet har index 0, det andra 1, osv.
- Index från 1: Vissa språk eller bibliotek använder 1-baserad indexering (det första elementet har index 1).
Vilken modell som används påverkar hur man beräknar adressen till ett element och kan ge upphov till vanliga fel som off-by-one-buggar.
Storlek och minneshantering
När en array skapas måste man ofta ange storleken — antalet element som arrayen kan hålla. För statiska arrayer är denna storlek fast. Vill man lagra fler element än arrayens kapacitet måste man skapa en ny, större array och kopiera över elementen. Detta är skälet till att dynamiska array-typer (t.ex. C++ std::vector, Java ArrayList) internt skapar nyare, större arrayer och kopierar innehållet när kapaciteten överskrids.
Att placera elementen i sammanhängande minnesadresser ger O(1)-åtkomst till ett element via dess index, men gör insättning eller borttagning i mitten av arrayen kostsamt (O(n)), eftersom elementen efter måste flyttas.
Typer av arrayer
- En-dimensionella arrayer: En rak lista av element.
- Flervariabla arrayer (matriser): Två- eller flerdimensionella arrayer (t.ex. matris med rader och kolumner). Kan vara regelbundna (alla rader lika långa) eller sågtandade (jagged arrays) där rader har olika längd.
- Statisk vs dynamisk: Statisk array (fast storlek) respektive dynamisk array som kan växa automatiskt.
Exempel i vanliga språk
Olika språk erbjuder arrays på olika sätt:
- C: Arrays har fast storlek och ligger i kontinuerligt minne. Exempel: int a[10];
- Java: Arrays är objekt och har fast längd efter skapandet: int[] a = new int[10]; Java har också ArrayList för dynamisk storlek.
- Python: Python har inte en inbyggd "array" med statisk typ i samma bemärkelse; listor fungerar som dynamiska arrayer (heterogena element är möjliga), och modulen array eller NumPy-arrayer används när man behöver homogena, effektiva numeriska arrayer.
Vanliga operationer och deras komplexitet
- Åtkomst (read/write) vid känt index: O(1)
- Sökning (osorterad): O(n)
- Insättning eller borttagning i mitten: O(n) (på grund av förskjutning av element)
- Lägga till i slutet: O(1) amortiserat för dynamiska arrayer (kan ibland trigga omallokering och kopiering)
När ska man använda en array?
- Använd array när du behöver snabb, slumpmässig åtkomst till element via index.
- Array är bra när antalet element är känt i förväg eller när minneslayouten (kontinuerligt minne) är viktig för prestanda.
- Om du ofta behöver infoga eller ta bort element i mitten kan andra datastrukturer (länkade listor, träd, eller specialiserade strukturer) vara mer passande.
Flervariabla tillämpningar
Tvådimensionella arrayer används ofta för matrisberäkningar, bilder (pixlar i rader och kolumner) och spelbrädor. Numeriska bibliotek (t.ex. NumPy i Python) använder optimerade N-dimensionella arrayer för vetenskapliga beräkningar.
Sammanfattning: En array är en enkel och effektiv datastruktur för lagring av flera element av samma typ med snabb åtkomst via index. Begränsningen ligger i storleksflexibilitet och kostnaden för insättningar/borttagningar i mitten — därför kompletteras arrays ofta av dynamiska varianter eller andra datastrukturer beroende på behov.
Matriser i C
I programmeringsspråket C kan matriser skapas på följande sätt:
Detta skapar en array av heltal och den kan lagra 5 heltal. Programmeraren kan nu lagra heltal i matrisen genom att göra följande:
Programmeraren kan använda ett värde i matrisen på följande sätt:
Matriser i Java
I programmeringsspråket Java kan matriser skapas på följande sätt:
Detta skapar en array av heltal och den kan lagra 5 heltal. Programmeraren kan nu lagra heltal i matrisen genom att göra följande:
Programmeraren kan använda ett värde i matrisen på följande sätt:
Frågor och svar
F: Vad är en array i programmeringsspråk?
S: En array är ett sätt att lagra flera objekt av samma typ i programmeringsspråk.
F: Vilken typ av objekt kan lagras i en array?
S: Endast objekt av samma typ, t.ex. heltal eller strängar, kan lagras i en array.
Fråga: Vad är ett index i en array?
S: Ett index är ett nummer som tilldelas varje objekt i en array så att programmeraren kan komma åt objektet med hjälp av det numret.
Fråga: Hur bestäms indexet för det första objektet i en array?
S: I vissa programmeringsspråk är indexet för den första posten 0, medan det i andra språk är 1.
Fråga: Vad måste programmeraren tillhandahålla när han skapar en array?
S: Programmeraren måste ange storleken på matrisen, vilket är det antal objekt som kan lagras i matrisen.
F: Varför kan man inte ändra storleken på en array?
S: Storleken på en array kan inte ändras eftersom den fastställs när arrayen skapas.
F: Vad måste en programmerare göra om han eller hon vill lagra fler objekt än vad arrayens storlek tillåter?
S: Om en programmerare vill lagra fler objekt än vad arrayens storlek tillåter måste han/hon skapa en ny array med en större storlek.
Sök