Datastrukturer
Fra simple Arrays til komplekse Graph-strukturer. Forstå kompleksitet, use cases og hvornår du bruger hvad i praksis.
Lineær
Sekventielt arrangerede elementer — Arrays, Stacks, Queues
Array
En sekvens af elementer gemt i sammenhængende hukommelse med fast eller dynamisk størrelse.
O(1)O(n)
Cirkulær buffer (ringbuffer)
En buffer med fast størrelse der bruger et enkelt array af fast størrelse som om enderne var forbundet i en ring.
O(1)O(n)
Deque (Dobbelt-endet kø)
En dobbelt-endet kø der tillader indsættelse og sletning af elementer fra både front og bagende i O(1) tid.
O(n) for vilkårlig, O(1) for enderO(n)
Kø
En FIFO (First In First Out) datastruktur hvor det første element tilføjet er det første der fjernes.
O(n)O(n)
Linked List
En sekvens af noder hvor hvert element peger til det næste element i kæden via en pointer.
O(n)O(n)Stak
En LIFO (Last In First Out) datastruktur hvor det sidste element tilføjet er det første der fjernes.
O(n)O(n)Træ
Hierarkiske strukturer med parent-child relationer
AVL-træ
Et selvbalancerende binært søgetræ hvor højdeforskellen mellem venstre og højre undertræ er maksimalt 1.
O(log n)O(log n)
B-træ
Et selvbalancerende træ optimeret til systemer der læser og skriver store datablokke som databaser og filsystemer.
O(log n)O(log n)
Fenwick-træ (binært indekseret træ)
En pladseffektiv datastruktur til kumulative frekvenstabeller og præfikssumforespørgsler i O(log n) tid.
O(log n)O(log n) for præfikssum
Rød-sort-træ
Et selvbalancerende binært søgetræ hvor hver node har en farve (rød eller sort) med specifikke balanceringsregler.
O(log n)O(log n)
Segmenttræ
En træstruktur til effektive intervalforespørgsler og opdateringer på arrays, som sum, minimum, maksimum på intervaller.
O(1) for enkelt elementO(log n) for intervalforespørgsel
Suffikstræ
En komprimeret trie der indeholder alle suffikser af en streng, brugt til effektiv strengmatching og mønstersøgning.
O(m) for mønsterlængde mO(m) for mønstermatchingHierarkisk
Flerlagede strukturer med definerede niveauer
Probabilistisk
Space-efficient approksimative strukturer
Avanceret
Specialiserede strukturer til komplekse problemer
Disjunkt mængde (Union-Find)
En datastruktur der sporer elementer partitioneret i disjunkte mængder og understøtter effektive union- og find-operationer.
N/AO(α(n)) amortiseret
Skip List
En probabilistisk datastruktur der bruger flere lag af lænkede lister til at opnå O(log n) ydeevne.
O(log n) gennemsnitO(log n) gennemsnitGraf
Netværksstrukturer med noder og forbindelser
Hash
Nøgle-værdi opslag med gennemsnitlig O(1) tid
Træ-baseret
Præfiks-baseret søgning og indexing
