Länkad lista

En länkad lista  är en grundläggande dynamisk datastruktur inom datavetenskap, bestående av noder som innehåller data och länkar ("länkar") till nästa och/eller föregående nod i listan. [1] Den grundläggande fördelen gentemot en array är strukturell flexibilitet: ordningen för elementen i en länkad lista kanske inte sammanfaller med ordningen för dataelementen i datorns minne [2] , och ordningen för genomgång av listan är alltid uttryckligen anges av dess interna länkar.

Typer av länkade listor

Linjär länkad lista

Enkellänkad lista (enkellänkad lista)

En linjär enkelriktad lista är en datastruktur som består av element av samma typ, länkade sekventiellt genom pekare. Varje element i listan har en pekare till nästa element. Det sista elementet i listan pekar på NULL . Elementet som inte pekas på är det första (huvud)elementet i listan. Här pekar länken vid varje nod till nästa nod i listan. I en enkellänkad lista kan du bara flytta mot slutet av listan. Det är omöjligt att ta reda på adressen till det föregående elementet baserat på innehållet i den aktuella noden.

Inom datavetenskap definieras en linjär lista vanligtvis som en abstrakt datatyp (ADT) som formaliserar begreppet en ordnad insamling av data . I praktiken implementeras linjära listor vanligtvis med hjälp av arrayer och länkade listor. Ibland används termen "lista" också informellt som en synonym för "länkad lista". Till exempel kan en otypad föränderlig lista ADT definieras som en uppsättning konstruktorer och grundläggande operationer:

  • En operation som kontrollerar om en lista är tom.
  • Tre operationer för att lägga till ett objekt i listan (till början, slutet eller inuti efter något (n:te) element i listan);
  • En operation som utvärderar det första (huvud)elementet i en lista;
  • En operation för att komma åt en lista som består av alla element i den ursprungliga listan utom den första.
Egenskaper
  • Listlängd . Antalet element i listan.
  • Listor kan vara maskinskrivna eller oskrivna . Om en lista skrivs, så anges typen av dess element, och alla dess element måste vara av typer som är kompatibla med den givna typen av listelement. De flesta listor är maskinskrivna.
  • Listan kan vara sorterad eller osorterad .
  • Beroende på implementeringen kan slumpmässig åtkomst till elementen i listan vara möjlig.
Enkellänkad lista i programmeringsspråk

Xi

strukturlista _ { int fält ; // datafält struct list * nästa ; // pekare till nästa element };

med en enskild länkad lista:

struct list * l1 = ( struct lista * ) malloc ( sizeof ( struct lista )); l1 -> fält = 1 ; l1 -> nästa = ( struct lista * ) malloc ( sizeof ( struct lista )); l1 -> nästa -> fält = 2 ; l1 -> nästa -> nästa = ( struct lista * ) malloc ( sizeof ( struct lista )); /* etc. */ Dubbellänkad lista (dubbellänkad lista)

Här pekar länkarna i varje nod till föregående och nästa nod i listan. Liksom en enkellänkad lista tillåter en dubbellänkad lista endast sekventiell åtkomst till element, men den tillåter också rörelse i båda riktningarna. I den här listan är det lättare att ta bort och ordna om element, eftersom adresserna till de element i listan vars pekare är riktade till elementet som ändras är lättillgängliga.

XOR länkad lista

Sällan använd.

Cirkulär länkad lista

En slags länkad lista är en ringlista (cyklisk, stängd). Den kan också vara enkellänkad eller dubbellänkad. Det sista elementet i en cirkulär lista innehåller en pekare till den första, och den första (i fallet med en dubbellänkad lista) till den sista.

Som regel implementeras en sådan struktur på basis av en linjär lista. Varje cirkulär lista lagrar dessutom en pekare till det första elementet. Det finns ingen referens till NULL i denna lista.

Det finns också cirkulära listor med ett dedikerat huvudelement för att göra det lättare att gå igenom hela listan.

Hoppa över lista

Utökad länkad lista

Fördelar

  • effektivt (i konstant tid) lägga till och ta bort element
  • storleken begränsas endast av mängden datorminne och pekarnas bitdjup
  • dynamisk tillägg och borttagning av element

Nackdelar

Nackdelarna med länkade listor beror på deras huvudsakliga egenskap - sekventiell åtkomst till data:

  • komplexiteten i direkt åtkomst till elementet, nämligen att bestämma den fysiska adressen genom dess index (serienummer) i listan
  • pekarfält (pekare till nästa och föregående element) förbrukar ytterligare minne (i arrayer behövs till exempel inte pekare)
  • vissa operationer med listor är långsammare än med arrayer, eftersom ett godtyckligt element i listan endast kan nås genom att gå igenom alla element som föregår den
  • angränsande listelement kan allokeras icke-lokalt i minnet, vilket kommer att minska effektiviteten av datacaching i processorn
  • jämfört med arrayer är det mycket svårare (även om det är möjligt) att utföra parallella vektoroperationer på länkade listor, som att beräkna summan: overheaden för iterering över element minskar effektiviteten av parallellisering

Se även

Anteckningar

  1. ↑ Cormen, Leiserson, Rivest och Stein. Introduktion till algoritmer, 2:a upplagan. The MIT Press, 2001. ISBN 0-262-03293-7
  2. ↑ Datajustering
 Data struktur
Listor
Träd
Räknar
Övrig