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)Circular Buffer (Ring Buffer)
En fast-størrelse buffer der bruger et enkelt, fixed-size array som om enderne var forbundet i en ring.
O(1)O(n)Deque (Double-Ended Queue)
En dobbelt-ended kø der tillader insertion og deletion af elementer fra både front og back i O(1) tid.
O(n) for arbitrary, O(1) for endsO(n)Linked List
En sekvens af nodes hvor hvert element peger til det næste element i kæden via en pointer.
O(n)O(n)Queue
En FIFO (First In First Out) datastruktur hvor det første element tilføjet er det første der fjernes.
O(n)O(n)Stack
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 Tree
Et self-balancing binært søgetræ hvor højdeforskellen mellem venstre og højre subtræ er maksimalt 1.
O(log n)O(log n)B-Tree
Et self-balancing træ optimeret til systemer der læser og skriver store datablokke som databaser og filsystemer.
O(log n)O(log n)Fenwick Tree (Binary Indexed Tree)
En space-efficient datastruktur til cumulative frequency tables og prefix sum queries i O(log n) tid.
O(log n)O(log n) for prefix sumRed-Black Tree
Et self-balancing binært søgetræ hvor hver node har en farve (rød eller sort) med specifikke balanceringsregler.
O(log n)O(log n)Segment Tree
En træstruktur til effektive range queries og updates på arrays, som sum, minimum, maximum på intervaller.
O(1) for single elementO(log n) for range querySuffix Tree
En komprimeret trie der indeholder alle suffixes af en string, brugt til effektiv string matching og pattern søgning.
O(m) for pattern length mO(m) for pattern matchingHierarkisk
Hierarkiske strukturer med niveauer
Probabilistisk
Probabilistiske strukturer med space-efficient approximation
Avanceret
Avancerede datastrukturer til specialiserede use cases
Disjoint Set (Union-Find)
En datastruktur der tracker elementer partitioneret i disjunkte sets og understøtter effektiv union og find operations.
N/AO(α(n)) amortizedSkip List
En probabilistisk datastruktur der bruger multiple layers af linked lists til at opnå O(log n) performance.
O(log n) averageO(log n) averageGraf
Netværksstrukturer med noder og forbindelser
Hash
Hash-baserede strukturer til hurtig lookup
Træ-baseret
Træ-baserede strukturer til præfiks søgning