Különböző problémák számítógépes megoldása során gyakran van szükség olyan adatszerkezetre, amely nagyszámú, azonos típusú elem tárolására alkalmas, esetleg nem jelent problémát a közvetlen elérés hiánya, azonban gyakran van szükség az adatszerkezet olyan szinten történő megváltoztatására, hogy bizonyos elemeit kitöröljük, illetve a már sorozatbeli elemek közé adott helyre újat vegyünk fel, lehetőleg kevés adatmozgatás elvégzésével. Ez utóbbi feltételezi, hogy nem feltétlenül ismert előre a sorozat elemszáma.
A listaelem feladata kettős. Egyrészt helyet kell biztosítania a sokaság egy eleme számára, másrészt biztosítania kell a következő elem elérését, hiszen a memória tetszőleges területén lehet.
Ennek megfelelően a listaelem funkcionálisan két részből áll: a tárolandó sorozat egy eleme és mutató a következő elem eléréséhez.
A láncolt lista olyan homogén, dinamikus, szekvenciális elérésű adatszerkezet, amelynek minden eleme - a tárolandó adatokon kívül - azt az információt is tárolja, hogy a következő elemet hol tárolja a rendszer a számítógép memóriájában.
Megjegyzés:
A lista első elemének eléréséhez csupán egy mutató is elegendő. Ennek ismerete a teljes lista ismeretét jelenti, mert így hozzáférhetünk az elemben tárolt minden adathoz, tehát azt az információt is ki tudjuk olvasni, hogy hol található a következő elem.
Ha a listaelemeket úgy építjük fel, hogy bennük m≥1 számú mutatót tárolunk, akkor ez lehetővé teszi a listaelemek m-féle sorrendben történő elérését. Ilyenkor általában szükség van m számú mutatóra is, mert ami az egyikféle elérési sorrend szerint első elem, az a másikban nem feltétlenül az.
A sorozat utolsó elemének érzékelésére a mutató kitüntetett értéke, a végjel szolgál. Az utolsó elem mutatójának értéke tehát VÉGJEL.
Ha üres a lista, a listát azonosító mutató értéke VÉGJEL.
A ciklikusan láncolt lista olyan láncolt lista, amelynek utolsó elemét az jellemzi, hogy mutatójának értéke nem végjel, hanem az első elem címét tárolja. Ha üres a lista, a listát azonosító mutató értéke végjel.
A két irányban láncolt lista minden eleme a tárolandó adaton kívül két mutatót tartalmaz. Az egyik (F1) a következő, míg a másik (F2) az őt megelőző elem memóriában elfoglalt helyét tárolja. Ennek megfelelően a lista azonosításához két mutatóra van szükség, az egyik az első, míg a másik az utolsó elem tárolási címét tartalmazza. Továbbá az is teljesül, hogy a ciklikusan láncolt lista olyan végjeles lista, amelyben az utolsó elem F1, míg az első elem F2 mutatójának értéke végjel.
Ha üres a lista, a listát azonosító mutatók értéke végjel.
A strázsás lista megvalósításához a tárolandó sorozat elemszámánál eggyel több elemre van szükség, ezt nevezzük strázsaelemnek. Ezt az elemet a sorozat utolsó elemének tárolására szolgáló elemtől lehet elérni, de biztosítunk egy egyszerűbb elérési lehetőséget is: egy külön mutatóban is tároljuk a címét. Ez lehetővé teszi, hogy a listaelemek végigolvasása nélkül is elérhessük. Üres állapotban tehát a strázsás lista egy elemből és két mutatóból áll. Ekkor mindkét mutató a strázsaelem tárolási címét tartalmazza.
A zárt fejelt lista megvalósításához egy mutatóra és a tárolandó sorozat elemszámánál eggyel több listaelemre (Fej) van szükség. Ennek az elemnek a mutatója tartalmazza a sorozat első elemének tárolására szolgáló elem címét, a mutató tartalma alapján pedig a Fej érhető el. A lista utolsó elemének mutatója a Fejre mutat. Üres állapotban tehát a zárt fejelt lista egy elemből és egy mutatóból áll.
Szabad helyek kezelése
A lista-adatszerkezetek szervezéséből adódóan a listaelemek a memória különböző területein, szétszórtan helyezkedhetnek el (különösen kellő számú új elemmel való bővítés és feleslegessé vált elem listából való elhagyása után). Ez természetesen nem okoz gondot, mert az egyes listaelemek elérését az őket megelőző elemek mutatói biztosítják. A listaelemekkel végezhető műveletek (lista bővítése egy elemmel, feleslegessé vált elem elhagyása a listából) azt feltételezik, hogy a listából törölt elemek is szétszórtan helyezkednek el a memóriában. Az így felszabadult elemekre a későbbiekben egy újabb bővítés alkalmával még szükség lehet, hiszen a lista dinamikus adatszerkezet. Meg kell tehát oldani a szabad helyek kezelését. Ennek legkézenfekvőbb megvalósítása, hogy a szabaddá vált listaelemeket egyszerűen egy listába fűzve tároljuk.