Liste (datastruktur): Forskelle mellem versioner
Content deleted Content added
Glenn (diskussion | bidrag) m interwiki |
Rune (diskussion | bidrag) Detaljeret beskrivelse af enkelt-kædet liste |
||
Linje 8:
*Dobbelt-kædet liste. Elementerne i listen har både en reference til det foregående og det efterfølgende element.
Det kan være en fordel, at vedligeholde en reference til det sidste element i listen. En sådan reference vil gøre det nemmere at implementere en [[kø (datastruktur)|kø]].
==Implementering==
Mange [[programmeringssprog]] giver mulighed for at arbejde med referencer til dataelementer, og dette gør det muligt, at implementere en dynamisk liste. Som eksempel kan en enkelt-kædet liste laves så dan her:
Selve listen er blot en reference. Hvis referencen ikke peger på noget, er listen tom. Hvert element i listen har en reference, der skal pege på det næste element i listen.
===Søgning===
Søgning i en enkelt-kædet liste kan kun foregå i en retning. Da alle elementer i listen har en reference til det næste element i listen, er søgning efter data simpel. Den kan også være langsommelig i en lang liste.
Ved sletning af elementer i listen er det nødvendigt, at have en reference til det foregående element. Da de enkelte elementer ikke indeholder oplysninger om det foregående element må søgningen laves, så det foregående element huskes. Dette kan opnås med følgende [[algoritme]]: Der bruges to referencer, ''aktuel'' og ''forrige''. Ved søgningens start peger ''forrige'' ikke på nogent mens ''aktuel'' peger på det første element i listen. Herefter sker søgningen i følgende trin.
*''Forrige'' sættes til det samme som ''aktuel''.
*''Aktuel'' sættes til at pege på det næste element.
*Hvis ''aktuel'' ikke peger på noget, er listen ikke længere og ''forrige'' peger på det sidste element. Det søgte element blev altså ikke fundet.
*Hvis ''aktuel'' peger på det ønskede element, peger ''forrige'' på elementet før.
*Forløbet gentages indtil ''aktuel'' peger på det rette element eller ikke peger på noget mere.
===Indsættelse===
Indsættelse af et element sker på forskellig måde alt efter hvor i listen det skal tilføjes. Hvis elemetet skal forrest i listen, sættes det nye element til at pege på det første element i den eksisterende liste. Derefter rettes listen, så den peger på det nye element.
Indsættelse midt i listen kræver en søgning, så man har en reference til elementet, der skal indsættes efter. Dette bliver det nye 'foregående' element. Det nye element sættes til at pege på det samme element, som det foregående peger på. Det foregående element rettes, så det peger på det nye element.
Elementer, der skal indsættes sidst i listen indsættes på samme måde som elementer, der indsættes midt i listen.
===Sleetning===
Hvis det første element i listen skal slettes, sættes listen blot til at starte med det næste element i den oprindelige liste, og det første element slettes.
Ved sletning findes det element, der skal fjernes med algoritmen beskrevet under søgning. Det forrige element i listen sættes til at pege videre til det element, som det aktuelle element peger på. Dermed er det aktuelle element ude af listen, og det kan slettes.
==Se også==
| |||