Lista (datavetenskap)

Inom datavetenskap är en lista ( engelsk  lista ) en abstrakt datatyp , som är en ordnad uppsättning värden där ett visst värde kan förekomma mer än en gång. En instans av en lista är en datorimplementering av det matematiska konceptet med en ändlig sekvens . Förekomster av värden i en lista kallas element i listan ( engelsk  objekt, post eller element ); om värdet förekommer flera gånger betraktas varje förekomst som ett separat element.

Termen lista syftar också på flera specifika datastrukturer som används vid implementering av abstrakta listor, särskilt länkade listor .

Definition

Med hjälp av notationen av C. Hoares syntaktiskt orienterade konstruktionsmetod kan definitionen av en lista skrivas på följande sätt:

Den första raden i denna definition betyder att listan över element av typen (säg: "lista över ") är den diskriminerade föreningen av den tomma listan och den kartesiska produkten av atomen av typen med listan över . För att skapa listor används två konstruktorer (den andra raden i definitionen), varav den första skapar en tom lista, och den andra - en icke-tom. Det är helt klart att den andra konstruktören tar emot någon atom och en lista som parametrar som indata, och returnerar en lista, vars första element är den ursprungliga atomen, och resten är elementen i den ursprungliga listan. Det vill säga att atomen har prefix till listan, vilket är anledningen till ett sådant namn för konstruktören. Den tomma listan är inte en atom och kan därför inte ha prefix. Å andra sidan är en tom lista null-elementet för att konstruera listor, så vilken lista som helst innehåller en tom lista i slutet - konstruktionen börjar med den.

Den tredje raden definierar väljarna för listan, det vill säga operationerna för att komma åt elementen i listan. Väljaren tar en lista som indata och returnerar det första elementet i denna lista, det vill säga typen av resultatet är typ . Denna väljare kan inte ta emot en tom lista som indata - i detta fall är resultatet av operationen odefinierat. Väljaren returnerar listan som erhållits från inmatningen som ett resultat av att huvudet kapades av (det första elementet). Denna väljare kan inte heller acceptera en tom lista som indata, eftersom resultatet av operationen i detta fall är odefinierat. Genom att använda dessa två operationer kan du få vilket element som helst från listan. Till exempel, för att få det tredje elementet i listan (om det finns ett), måste du använda väljaren två gånger i följd och sedan använda väljaren . Med andra ord, för att få det element i listan som är på plats (som börjar med det första elementet, som är vanligt vid programmering), måste du använda väljaren en gång och sedan använda väljaren .

Den fjärde raden i definitionen beskriver listpredikat , det vill säga funktioner som returnerar ett booleskt värde beroende på vissa villkor. Det första predikatet returnerar ett värde om den givna listan är tom. Det andra predikatet fungerar omvänt. Slutligen beskriver den femte raden de delar av listan, som, som redan nämnts, är de tomma och icke-tomma listorna.

Egenskaper

Datastrukturen som definieras på detta sätt har några egenskaper:

• Storleken på listan  är antalet element i den, exklusive det sista "null"-elementet, som per definition är en tom lista.
• Typen av element  är samma typ som listan är uppbyggd över; alla element i listan måste vara av denna typ.
• Sorterad  - listan kan sorteras enligt vissa sorteringskriterier (till exempel stigande heltalsvärden, om listan består av heltal).
• Tillgänglighet  - Vissa listor, beroende på implementeringen, kan förse programmeraren med väljare för att komma åt det numrerade elementet direkt.
• Jämförbarhet  - listor kan jämföras med varandra för korrespondens, och beroende på implementeringen kan listjämförelsen använda olika teknologier.

Listor används för att lagra uppsättningar av element av samma typ. Sådana element kan sorteras för användning i sökfunktioner eller funktioner för att snabbt infoga nya element i en lista.

Listor på programmeringsspråk

Funktionella språk

Listor på funktionella språk är en grundläggande struktur. De flesta funktionella språk har inbyggda faciliteter för att arbeta med listor, såsom att få längden på listan, huvudet (det första elementet i listan), svansen (den del av listan som följer det första elementet), tillämpa en funktion på varje element i listan ( Karta ), vika listan osv.