Lenket liste
 | Kildeløs: Denne artikkelen mangler kildehenvisninger, og opplysningene i den kan dermed være vanskelige å verifisere. Kildeløst materiale kan bli fjernet. Helt uten kilder. (10. okt. 2015) |
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
