Linket liste

En sammenkædet liste  er en grundlæggende dynamisk datastruktur inden for datalogi, bestående af noder, der indeholder data og links ("links") til den næste og/eller forrige node på listen. [1] Den grundlæggende fordel i forhold til et array er strukturel fleksibilitet: rækkefølgen af ​​elementerne i en sammenkædet liste falder muligvis ikke sammen med rækkefølgen af ​​dataelementerne i computerens hukommelse [2] , og rækkefølgen af ​​gennemgangen af ​​listen er altid udtrykkeligt angivet af dets interne links.

Typer af linkede lister

Lineær linket liste

Enkelt linket liste (enkelt linket liste)

En lineær enkelt-dirigeret liste er en datastruktur, der består af elementer af samme type, forbundet sekventielt gennem pointere. Hvert element på listen har en markør til det næste element. Det sidste element på listen peger på NULL . Det element, der ikke peges på, er det første (hoved) element på listen. Her peger linket ved hver node til den næste node på listen. I en enkelt linket liste kan du kun bevæge dig mod slutningen af ​​listen. Det er umuligt at finde ud af adressen på det forrige element baseret på indholdet af den aktuelle node.

I datalogi er en lineær liste normalt defineret som en abstrakt datatype (ADT), der formaliserer begrebet en ordnet samling af data . I praksis implementeres lineære lister normalt ved hjælp af arrays og sammenkædede lister. Nogle gange bruges udtrykket "liste" også uformelt som et synonym for "linket liste". For eksempel kan en ADT for en utyperet mutabel liste defineres som et sæt konstruktører og grundlæggende operationer:

  • En operation, der kontrollerer, om en liste er tom.
  • Tre operationer med at tilføje et objekt til listen (til begyndelsen, slutningen eller inde efter ethvert (n-te) element på listen);
  • En operation, der evaluerer det første (hoved)element i en liste;
  • En handling for at få adgang til en liste bestående af alle elementer i den originale liste undtagen den første.
Karakteristika
  • Listens længde . Antallet af elementer på listen.
  • Lister kan indtastes eller ikke indtastes . Hvis en liste er skrevet, så er typen af ​​dens elementer angivet, og alle dens elementer skal være af typer, der er kompatible med den givne type listeelementer. De fleste lister er maskinskrevne.
  • Listen kan være sorteret eller usorteret .
  • Afhængigt af implementeringen kan tilfældig adgang til listens elementer være mulig.
Enkeltforbundet liste i programmeringssprog

Xi

strukturliste _ { int felt ; // data felt struct list * næste ; // pointer til næste element };

ved hjælp af en enkelt linket liste:

struct liste * l1 = ( struct liste * ) malloc ( sizeof ( struct liste )); l1 -> felt = 1 ; l1 -> næste = ( struct liste * ) malloc ( sizeof ( struct liste )); l1 -> næste -> felt = 2 ; l1 -> næste -> næste = ( struct liste * ) malloc ( sizeof ( struct liste )); /* etc. */ Dobbelt linket liste (dobbelt linket liste)

Her peger linkene i hver node til den forrige og næste node på listen. Som en enkelt-linket liste tillader en dobbelt-linket liste kun sekventiel adgang til elementer, men den tillader også bevægelse i begge retninger. I denne liste er det nemmere at slette og omarrangere elementer, da adresserne på de elementer på listen, hvis pointer er rettet mod det element, der ændres, er let tilgængelige.

XOR linket liste

Sjældent brugt.

Cirkulær linket liste

En slags sammenkædet liste er en ring (cyklisk, lukket) liste. Det kan også være enkelt- eller dobbelt-linket. Det sidste element i en cirkulær liste indeholder en pointer til den første, og den første (i tilfælde af en dobbelt kædet liste) til den sidste.

Som regel implementeres en sådan struktur på grundlag af en lineær liste. Hver cirkulær liste gemmer desuden en pointer til det første element. Der er ingen reference til NULL i denne liste.

Der er også cirkulære lister med et dedikeret hovedelement for at gøre det nemmere at gå gennem hele listen.

Spring over listen

Udvidet linket liste

Fordele

  • effektiv (i konstant tid) tilføjelse og fjernelse af elementer
  • størrelsen er kun begrænset af mængden af ​​computerhukommelse og bitdybden af ​​pointere
  • dynamisk tilføjelse og fjernelse af elementer

Ulemper

Ulemperne ved linkede lister stammer fra deres hovedegenskab - sekventiel adgang til data:

  • kompleksiteten af ​​direkte adgang til elementet, nemlig at bestemme den fysiske adresse ved dets indeks (serienummer) på listen
  • markørfelter (pegere til det næste og forrige element) bruger yderligere hukommelse (i arrays er der for eksempel ikke behov for pointere)
  • nogle operationer med lister er langsommere end med arrays, da et vilkårligt element i listen kun kan tilgås ved at gå gennem alle de forudgående elementer
  • nabolisteelementer kan allokeres ikke-lokalt i hukommelsen, hvilket vil reducere effektiviteten af ​​datacache i processoren
  • sammenlignet med arrays er det meget vanskeligere (selv om det er muligt) at udføre parallelle vektoroperationer på sammenkædede lister, såsom at beregne summen: overhead ved iteration over elementer reducerer effektiviteten af ​​parallelisering

Se også

Noter

  1. ↑ Cormen, Leiserson, Rivest og Stein. Introduktion til Algoritmer, 2. udgave. The MIT Press, 2001. ISBN 0-262-03293-7
  2. ↑ Datajustering
 Datastrukturer
Lister
Træer
Tæller
Andet