Datastrukturer
Udforsk fundamentale datastrukturer, deres kompleksitet og praktiske anvendelser. Fra simple Arrays til komplekse Graph strukturer.
Lineær
Lineære strukturer hvor elementer er arrangeret i en sekvens
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
Hierarkiske strukturer med niveauer
Probabilistisk
Probabilistiske strukturer med space-efficient approximation
Avanceret
Avancerede datastrukturer til specialiserede use cases
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
Hash-baserede strukturer til hurtig lookup
Træ-baseret
Træ-baserede strukturer til præfiks søgning
