Linkede lister (simpel og dobbelt)

It A · STX · A-niveau · Datastrukturer og algoritmer

💻 Linkede lister (simpel og dobbelt)

Lineære datastrukturer gemmer elementer i sekvens.

Liste (Array/Dynamic Array): tilfældig adgang O(1), indsæt/slet i slutning O(1) amortiseret, midten O(n). Python's list er dynamisk array.

Stakk (Stack, LIFO): Last In, First Out. Operationer: push (tilføj øverst), pop (fjern øverst), peek (vis øverste). Implementeret med liste: stack = []; stack.append(x); stack.pop(). Anvendelser: undo-funktionalitet, funktionskaldsstakken, DFS-søgning, parentesvalidering.

Kø (Queue, FIFO): First In, First Out. Operationer: enqueue (tilføj bagpå), dequeue (fjern forfra). Python's collections.deque er optimalt (O(1) begge ender). queue.Queue til trådsikker kø. Anvendelser: BFS-søgning, opgavekø (task queue), printerprint-kø, message queue (Kafka, RabbitMQ).

Dobbelt-linket liste (Doubly Linked List): hvert node har next OG prev pointer. O(1) indsæt/slet ved kendte positioner. O(n) søgning. Implementeret manuelt med Node-klasser.

Prioritetskø (Priority Queue/Heap): elementer serviceres efter prioritet, ikke indkomst-rækkefølge. Python: heapq. Min-heap: mindste element rykkes til top.

Læringsmål

• Redegøre for opbygningen af simple og dobbelt linkede lister
• Sammenligne linkede lister med arrays
• Implementere indsættelse og sletning i en linket liste

Sådan kan du arbejde med emnet

• Implementér en enkelt-linket liste med metoder til at tilføje, slette og søge
• Forklar, hvad der er forskellen på en simpel og en dobbelt-linket liste
• Sammenlign en linket liste med et Python-array (list) med hensyn til tidskompleksitet for søgning og indsættelse

Arbejd iterativt med prototyper og dokumentation. Test, evaluér og dokumentér.