Lenket liste
En lenket liste (engelsk: linked list) er en grunnleggende datastruktur som brukes i dataprogrammering. Den består av en sekvens av noder, som alle inneholder noe data og én eller to referanser til den neste og/eller den forrige noden. En lenket liste er en selv-refererende datatype fordi en node inneholder en peker eller lenke til en node av samme type. Lenkede lister tillater innsetting eller sletting av noder hvor som helst i listen i konstant tid, men tillater ikke random access. Både dobbelt-lenkede og enkelt-lenkede er vanlige.
Lenkede lister kan bli implementert i de fleste programmeringsspråk. Språk som Lisp og Scheme har denne datastrukturen innebygget, sammen med operasjoner for å aksessere den. II språk som C, C++ og Java brukes muterbare referanser til å danne lenkede lister.
Enkel-lenket liste[rediger | rediger kilde]
Den enkleste formen for lenket liste er den enkelt lenkede listen (engelsk: singly-linked list), som har en link per node. Denne lenken peker til den neste noden i listen, eller til en null-verdi dersom det er den siste noden.
En enkelt-lenket liste som inneholder tre tall
Dobbelt-lenket liste[rediger | rediger kilde]
En mer sofistikert form for lenket liste er en dobbelt-lenket liste (engelsk: doubly linked list) eller en toveis lenket liste. Hver node har to lenker; den ene peker til den forrige noden, eller til null dersom det er den første noden; og den andre peker til den neste eller til null dersom det er den siste noden.
Eksterne lenker[rediger | rediger kilde]
- (en) Linked lists – kategori av bilder, video eller lyd på Commons
