Spojový seznam - Linked list

Propojený seznam, jehož uzly obsahují dvě pole: celočíselnou hodnotu a odkaz na další uzel. Poslední uzel je spojen s terminátorem používaným k označení konce seznamu.

V informatice je propojený seznam lineární kolekce datových prvků, jejichž pořadí není dáno jejich fyzickým umístěním v paměti. Místo toho každý prvek ukazuje na další. Jedná se o datovou strukturu sestávající ze souboru uzlů, které společně představují posloupnost . Ve své nejzákladnější podobě obsahuje každý uzel: data a odkaz (jinými slovy odkaz) do dalšího uzlu v pořadí. Tato struktura umožňuje efektivní vkládání nebo odebírání prvků z jakékoli pozice v sekvenci během iterace. Složitější varianty přidávají další odkazy, což umožňuje efektivnější vkládání nebo odebírání uzlů na libovolných pozicích. Nevýhodou spojových seznamů je, že přístupová doba je lineární (a těžko potrubí ). Rychlejší přístup, například náhodný přístup, není možný. Pole mají lepší umístění mezipaměti ve srovnání s propojenými seznamy.

Propojené seznamy patří mezi nejjednodušší a nejběžnější datové struktury. Lze je použít k implementaci několika dalších běžných abstraktních datových typů , včetně seznamů , zásobníků , front , asociativních polí a výrazů S , ačkoli není neobvyklé implementovat tyto datové struktury přímo bez použití propojeného seznamu jako základu.

Hlavní výhodou propojeného seznamu oproti konvenčnímu poli je, že prvky seznamu lze snadno vkládat nebo odebírat bez přerozdělení nebo reorganizace celé struktury, protože datové položky nemusí být uloženy souvisle v paměti nebo na disku, zatímco restrukturalizace pole na run-time je mnohem dražší operace. Propojené seznamy umožňují vkládání a odebírání uzlů v libovolném bodě seznamu a umožňují to při konstantním počtu operací tím, že se odkaz před odkazem přidá nebo odebere v paměti během procházení seznamu.

Na druhou stranu, protože jednoduché propojené seznamy samy o sobě neumožňují náhodný přístup k datům ani žádnou formu efektivního indexování, mnoho základních operací - jako je získání posledního uzlu seznamu, nalezení uzlu, který obsahuje daný údaj, nebo vyhledání místa, kam by měl být vložen nový uzel - může vyžadovat opakování většiny nebo všech prvků seznamu. Výhody a nevýhody používání propojených seznamů jsou uvedeny níže.

Dějiny

Propojené seznamy byly vyvinuty v letech 1955–1956 Allenem Newellem , Cliffem Shawem a Herbertem A. Simonem ve společnosti RAND Corporation jako primární datová struktura pro jejich jazyk zpracování informací . Autoři použili IPL k vývoji několika raných programů umělé inteligence , včetně stroje Logic Theory Machine, General Problem Solver a programu pro počítačové šachy. Zprávy o jejich práci se objevily v IRE Transactions on Information Theory v roce 1956 a několika sbornících z konferencí v letech 1957 až 1959, včetně sborníku ze Západní společné počítačové konference v letech 1957 a 1958 a zpracování informací (sborník z první mezinárodní konference UNESCO o zpracování informací UNESCO ) v roce 1959. Nyní klasický diagram skládající se z bloků představujících uzly seznamu se šipkami ukazujícími na po sobě jdoucí uzly seznamu se objeví v „Programming the Logic Theory Machine“ od Newella a Shawa v Proc. WJCC, únor 1957. Newell a Simon byli v roce 1975 oceněni Turingovou cenou ACM za to, že „učinili základní příspěvky k umělé inteligenci, psychologii lidského poznání a zpracování seznamu“. Problém strojového překladu pro zpracování přirozeného jazyka vedl Victor Yngve z Massachusetts Institute of Technology (MIT) k použití propojených seznamů jako datových struktur ve svém programovacím jazyce COMIT pro počítačový výzkum v oblasti lingvistiky . Zpráva o tomto jazyce s názvem „Programovací jazyk pro mechanický překlad“ se objevila v Mechanickém překladu v roce 1958.

Dalším raným výskytem propojených seznamů byl Hans Peter Luhn, který v lednu 1953 napsal interní memorandum IBM, které navrhovalo použití propojených seznamů v řetězových hashovacích tabulkách.

LISP , zkratka pro seznamový procesor, vytvořil John McCarthy v roce 1958, když byl na MIT, a v roce 1960 publikoval jeho návrh v příspěvku v Komunikaci ACM s názvem „Rekurzivní funkce symbolických výrazů a jejich výpočet strojem, část Já ". Jednou z hlavních datových struktur LISP je propojený seznam.

Počátkem šedesátých let byla užitečnost propojených seznamů a jazyků, které tyto struktury používají jako primární reprezentaci dat, dobře zavedená. Bert Green z MIT Lincoln Laboratory publikoval v březnu 1961 přehledový článek s názvem „Počítačové jazyky pro manipulaci se symboly“ v IRE Transactions on Human Factors in Electronics, který shrnul výhody přístupu propojeného seznamu. Pozdější recenzní článek „Srovnání počítačových jazyků pro zpracování seznamu“ od Bobrowa a Rafaela se objevil v Komunikaci ACM v dubnu 1964.

Několik operačních systémů vyvinutých společností Technical Systems Consultants (původně z West Lafayette Indiana a později z Chapel Hill v Severní Karolíně) používalo jako souborové struktury jednotlivě propojené seznamy. Položka adresáře ukazovala na první sektor souboru a následující části souboru byly umístěny procházením ukazatelů. Systémy využívající tuto techniku ​​zahrnovaly Flex (pro CPU Motorola 6800 ), mini-Flex (stejný CPU) a Flex9 (pro CPU Motorola 6809). Varianta vyvinutá společností TSC pro a prodávaná společností Smoke Signal Broadcasting v Kalifornii používala dvojitě propojené seznamy stejným způsobem.

Operační systém TSS/360, vyvinutý společností IBM pro počítače System 360/370, používal pro katalog systému souborů dvojitě propojený seznam. Struktura adresářů byla podobná Unixu, kde adresář mohl obsahovat soubory a další adresáře a zasahovat do libovolné hloubky.

Základní pojmy a názvosloví

Každý záznam propojeného seznamu se často nazývá „prvek“ nebo „ uzel “.

Pole každého uzlu, které obsahuje adresu dalšího uzlu, se obvykle nazývá „další odkaz“ nebo „další ukazatel“. Zbývající pole jsou známá jako pole „data“, „informace“, „hodnota“, „náklad“ nebo „užitečné zatížení“.

'Hlava' seznamu je jeho první uzel. 'Ocas' seznamu může odkazovat buď na zbytek seznamu za záhlaví, nebo na poslední uzel v seznamu. V Lispu a některých odvozených jazycích může být další uzel nazýván „ cdr “ (vyslovuje se can-er ) seznamu, zatímco užitečné zatížení hlavního uzlu se může nazývat „auto“.

Jednoduše propojený seznam

Jednotlivé propojené seznamy obsahují uzly, které mají datové pole, stejně jako pole „další“, které ukazuje na další uzel v řadě uzlů. Operace, které lze provádět na jednotlivě propojených seznamech, zahrnují vkládání, mazání a procházení.

Jednoduše propojený seznam, jehož uzly obsahují dvě pole: celočíselnou hodnotu a odkaz na další uzel

Následující kód ukazuje, jak přidat nový uzel s datovou „hodnotou“ na konec jednotlivě propojeného seznamu:

node addNode(node head, int value) {
    node temp, p; // declare two nodes temp and p
    temp = createNode(); // assume createNode creates a new node with data = 0 and next pointing to NULL.
    temp->data = value; // add element's value to data part of node
    if (head == NULL) {
        head = temp;     // when linked list is empty
    }
    else {
        p = head; // assign head to p 
        while (p->next != NULL) {
            p = p->next; // traverse the list until p is the last node. The last node always points to NULL.
        }
        p->next = temp; // Point the previous last node to the new node created.
    }
    return head;
}

Dvojitě propojený seznam

Ve „dvojitě propojeném seznamu“ obsahuje každý uzel kromě odkazu na další uzel také druhé pole odkazu směřující na „předchozí“ uzel v pořadí. Tyto dva odkazy mohou být nazývány „vpřed („ s “) a„ zpět “nebo„ další “a„ předchozí “(„ předchozí “).

Dvojitě propojený seznam, jehož uzly obsahují tři pole: celočíselnou hodnotu, odkaz vpřed na další uzel a odkaz zpět na předchozí uzel

Technika známá jako propojení XOR umožňuje implementaci dvojitě propojeného seznamu pomocí jednoho pole odkazu v každém uzlu. Tato technika však vyžaduje schopnost provádět bitové operace s adresami, a proto nemusí být k dispozici v některých jazycích vyšší úrovně.

Mnoho moderních operačních systémů používá dvojitě propojené seznamy k udržování odkazů na aktivní procesy, vlákna a další dynamické objekty. Běžnou strategií, jak se rootkitům vyhnout detekci, je odpojit se od těchto seznamů.

Násobně propojený seznam

V 'multiply linked list' každý uzel obsahuje dvě nebo více propojovacích polí, přičemž každé pole se používá k propojení stejné sady datových záznamů v jiném pořadí stejné sady (např. Podle jména, podle oddělení, podle data narození, atd.). Zatímco dvojitě propojené seznamy lze považovat za zvláštní případy vícenásobně propojeného seznamu, skutečnost, že dva a více řádů jsou proti sobě, vede k jednodušším a efektivnějším algoritmům, takže jsou obvykle považovány za samostatný případ.

Kruhový propojený seznam

V posledním uzlu seznamu pole odkazu často obsahuje nulovou referenci, speciální hodnota označuje nedostatek dalších uzlů. Méně obvyklou konvencí je ukázat na první uzel seznamu; v takovém případě se říká, že seznam je „kruhový“ nebo „kruhově propojený“; jinak se říká, že je „otevřený“ nebo „lineární“. Je to seznam, kde poslední ukazatel ukazuje na první uzel.

Kruhový propojený seznam

V případě kruhového dvojitě propojeného seznamu první uzel také ukazuje na poslední uzel seznamu.

Sentinelové uzly

V některých implementacích může být před prvním datovým záznamem nebo za posledním přidán další uzel „sentinel“ nebo „dummy“. Tato konvence zjednodušuje a zrychluje některé algoritmy pro zpracování seznamu tím, že zajišťuje, že všechny odkazy lze bezpečně dereferencovat a že každý seznam (i ten, který neobsahuje žádné datové prvky) má vždy „první“ a „poslední“ uzel.

Prázdné seznamy

Prázdný seznam je seznam, který neobsahuje žádné datové záznamy. To je obvykle stejné jako říkat, že má nulové uzly. Pokud se používají sentinelové uzly, seznam je obvykle označen jako prázdný, pokud má pouze sentinelové uzly.

Propojení hash

Pole propojení nemusí být fyzicky součástí uzlů. Pokud jsou datové záznamy uloženy v poli a odkazují na ně jejich indexy, může být pole odkazu uloženo v samostatném poli se stejnými indexy jako datové záznamy.

Popisovače seznamu

Protože odkaz na první uzel poskytuje přístup k celému seznamu, je tento odkaz často nazýván 'adresa', 'ukazatel' nebo 'popisovač' seznamu. Algoritmy, které manipulují s propojenými seznamy, obvykle takové popisovače dostanou do vstupních seznamů a vrátí je do výsledných seznamů. Ve skutečnosti v kontextu takových algoritmů slovo „seznam“ často znamená „popisovač seznamu“. V některých situacích však může být vhodné odkazovat na seznam pomocí popisovače, který se skládá ze dvou odkazů a ukazuje na jeho první a poslední uzel.

Kombinace alternativ

Výše uvedené alternativy lze libovolně kombinovat téměř ve všech směrech, takže je možné mít kruhové dvojitě propojené seznamy bez indikátorů, kruhové jednotlivě propojené seznamy se sentinely atd.

Kompromisy

Stejně jako u většiny možností počítačového programování a designu, žádná metoda není vhodná za všech okolností. Datová struktura propojeného seznamu může v jednom případě fungovat dobře, ale v jiném způsobit problémy. Toto je seznam některých běžných kompromisů zahrnujících propojené struktury seznamu.

Propojené seznamy vs. dynamická pole

Dynamické pole je datová struktura, která přiděluje všechny prvky souvisle v paměti, a udržuje počet aktuálního počtu prvků. Pokud je prostor vyhrazený pro dynamické pole překročen, dojde k jeho přerozdělení a (případně) zkopírování, což je nákladná operace.

Propojené seznamy mají oproti dynamickým polím několik výhod. Vložení nebo vymazání prvku v určitém bodě seznamu za předpokladu, že jsme již indexovali ukazatel na uzel (před tím, který má být odstraněn, nebo před bodem vložení) již, je operace konstantního času (jinak bez tohoto odkaz je O (n)), zatímco vložení do dynamického pole na náhodných místech bude vyžadovat přesunutí poloviny prvků v průměru a všech prvků v nejhorším případě. I když je možné prvek „odstranit“ z pole v konstantním čase nějakým způsobem označit jeho slot jako „prázdný“, způsobí to fragmentaci, která brání výkonu iterace.

Kromě toho může být libovolně mnoho prvků vloženo do propojeného seznamu, omezeného pouze celkovou dostupnou pamětí; zatímco dynamické pole nakonec zaplní svou základní datovou strukturu pole a bude se muset přerozdělit - drahá operace, která nemusí být možná ani v případě fragmentace paměti, ačkoli náklady na přerozdělení lze zprůměrovat na vložení a náklady na vložení v důsledku přerozdělení by bylo stále amortizováno O (1). To pomáhá s připojováním prvků na konci pole, ale vkládání do (nebo odebírání) středních pozic stále nese nepřiměřené náklady kvůli přesunu dat, aby byla zachována souvislost. Pole, ze kterého je odebráno mnoho prvků, bude pravděpodobně také nutné změnit velikost, aby nedocházelo k plýtvání příliš velkým prostorem.

Na druhé straně dynamická pole (stejně jako datové struktury polí pevné velikosti ) umožňují náhodný přístup v konstantní době , zatímco propojené seznamy umožňují pouze sekvenční přístup k prvkům. Jednotlivé propojené seznamy lze ve skutečnosti snadno procházet pouze jedním směrem. Díky tomu jsou propojené seznamy nevhodné pro aplikace, kde je užitečné rychle vyhledat prvek podle jeho indexu, například heapsort . Sekvenční přístup na polích a dynamických polích je také rychlejší než na propojených seznamech na mnoha počítačích, protože mají optimální referenční lokalitu a dobře tak využívají ukládání dat do mezipaměti.

Další nevýhodou propojených seznamů je dodatečné úložiště potřebné pro odkazy, což je často činí nepraktickými pro seznamy malých datových položek, jako jsou znaky nebo logické hodnoty , protože režie úložiště pro odkazy může dvakrát nebo více překročit velikost data. Naproti tomu dynamické pole vyžaduje pouze prostor pro samotná data (a velmi malé množství kontrolních dat). Může být také pomalé a s naivním alokátorem, nehospodárné, přidělovat paměť zvlášť pro každý nový prvek, což je problém obecně vyřešený pomocí paměťových oblastí .

Některá hybridní řešení se snaží spojit výhody obou reprezentací. Rozvinuté propojené seznamy ukládají v každém uzlu seznamu několik prvků, což zvyšuje výkon mezipaměti a zároveň snižuje režijní náklady na odkazy. Kódování CDR dělá obojí stejně tak, že nahrazuje odkazy skutečnými odkazovanými daty, která přesahují konec referenčního záznamu.

Dobrým příkladem, který zdůrazňuje výhody a nevýhody používání dynamických polí vs. propojených seznamů, je implementace programu, který řeší problém Josephus . Josephusův problém je volební metoda, která funguje tak, že skupina lidí stojí v kruhu. Počínaje předem určenou osobou lze počítat kolem kruhu nkrát . Jakmile je dosaženo n -té osoby, měli byste je odstranit z kruhu a nechat členy kruh uzavřít. Proces se opakuje, dokud nezůstane pouze jedna osoba. Ten člověk vyhraje volby. To ukazuje silné a slabé stránky propojeného seznamu vs. dynamické pole, protože pokud jsou lidé v kruhovém propojeném seznamu považováni za propojené uzly, ukazuje to, jak snadno je propojený seznam schopen uzly odstranit (protože pouze musí přeskupit odkazy na různé uzly). Propojený seznam však bude špatný při hledání další osoby k odstranění a bude muset procházet seznam, dokud tuto osobu nenajde. Na druhé straně dynamické pole bude špatné při odstraňování uzlů (nebo prvků), protože nemůže odebrat jeden uzel, aniž by jednotlivě přesouvalo všechny prvky v seznamu o jeden. Je však výjimečně snadné najít n -tu osobu v kruhu přímým odkazováním na jejich pozici v poli.

Problém s hodnocením seznamu se týká efektivní konverze reprezentace propojeného seznamu do pole. Přestože je to pro konvenční počítač triviální, řešení tohoto problému paralelním algoritmem je komplikované a bylo předmětem mnoha výzkumů.

Vyvážený strom má podobné vzory přístup k paměti a prostor nad hlavou do propojeného seznamu, zatímco umožňuje mnohem účinnější indexování, přičemž O (log n) namísto O (n) pro náhodný přístup. Operace vkládání a odstraňování jsou však dražší kvůli režii manipulací se stromy, aby byla zachována rovnováha. Existují schémata pro stromy, které se automaticky udržují ve vyváženém stavu: stromy AVL nebo červeno -černé stromy .

Jednoduše propojené lineární seznamy vs. jiné seznamy

Zatímco dvojitě propojené a kruhové seznamy mají výhody oproti jednotlivě propojeným lineárním seznamům, lineární seznamy nabízejí určité výhody, díky nimž jsou v některých situacích vhodnější.

Jednoduše propojený lineární seznam je rekurzivní datová struktura, protože obsahuje ukazatel na menší objekt stejného typu. Z tohoto důvodu má mnoho operací na jednoduše propojených lineárních seznamech (například sloučení dvou seznamů nebo vyjmenování prvků v opačném pořadí) často velmi jednoduché rekurzivní algoritmy, mnohem jednodušší než jakékoli řešení využívající iterační příkazy . Zatímco tato rekurzivní řešení lze upravit pro dvojitě propojené a kruhově propojené seznamy, postupy obecně vyžadují další argumenty a komplikovanější základní případy.

Lineární jednotlivě propojené seznamy také umožňují sdílení ocasu , použití společné konečné části dílčího seznamu jako koncové části dvou různých seznamů. Zejména pokud je na začátek seznamu přidán nový uzel, zůstane předchozí seznam k dispozici jako konec nového - jednoduchý příklad trvalé datové struktury . U ostatních variant to opět neplatí: uzel nesmí nikdy patřit do dvou různých kruhových nebo dvakrát propojených seznamů.

Zejména koncové sentinelové uzly mohou být sdíleny mezi jednotlivě propojenými nekruhovými seznamy. Pro každý takový seznam lze použít stejný koncový sentinelový uzel . Například v Lispu každý správný seznam končí odkazem na speciální uzel označený nilnebo (), jehož CARa CDRodkazy směřují k sobě. Tedy postup Lisp může bezpečně vzít CAR, nebo CDRz jakéhokoliv seznamu.

Výhody efektních variant jsou často omezeny na složitost algoritmů, nikoli na jejich účinnost. Zejména kruhový seznam lze obvykle emulovat lineárním seznamem společně se dvěma proměnnými, které ukazují na první a poslední uzel, a to bez dalších nákladů.

Dvojitě propojené vs. jednotlivě propojené

Dvojitě propojené seznamy vyžadují více místa na uzel (pokud jeden nepoužívá propojení XOR ) a jejich základní operace jsou dražší; ale často se s nimi lépe manipuluje, protože umožňují rychlý a snadný sekvenční přístup k seznamu v obou směrech. Ve dvojitě propojeném seznamu lze vložit nebo odstranit uzel s konstantním počtem operací s uvedením pouze adresy daného uzlu. Chcete -li udělat totéž v jednotlivě propojeném seznamu, musíte mít adresu ukazatele na tento uzel, což je buď popisovač celého seznamu (v případě prvního uzlu), nebo pole odkazu v předchozím uzlu. Některé algoritmy vyžadují přístup v obou směrech. Na druhou stranu dvojitě propojené seznamy neumožňují sdílení ocasu a nelze je použít jako trvalé datové struktury .

Kruhově vs. lineárně propojeno

Kruhově propojený seznam může být přirozenou možností, jak reprezentovat pole, která jsou přirozeně kruhová, např. Rohy polygonu , fond vyrovnávacích pamětí, které se používají a uvolňují v pořadí FIFO („první dovnitř, první ven“), nebo sada procesy, které by měly být sdíleny časem v pořadí každý s každým . V těchto aplikacích slouží ukazatel na libovolný uzel jako popisovač celého seznamu.

U kruhového seznamu poskytuje ukazatel na poslední uzel snadný přístup také k prvnímu uzlu pomocí jednoho odkazu. V aplikacích, které vyžadují přístup na oba konce seznamu (např. Při implementaci fronty), tedy kruhová struktura umožňuje zpracovat strukturu pomocí jediného ukazatele namísto dvou.

Kruhový seznam lze v konstantním čase rozdělit na dva kruhové seznamy zadáním adres posledního uzlu každého kusu. Operace spočívá v prohození obsahu polí odkazů těchto dvou uzlů. Použití stejné operace na libovolné dva uzly ve dvou odlišných seznamech spojí dva seznamy do jednoho. Tato vlastnost výrazně zjednodušuje některé algoritmy a datové struktury, jako jsou quad-edge a face-edge .

Nejjednodušší reprezentací prázdného kruhového seznamu (když taková věc dává smysl) je nulový ukazatel, který označuje, že seznam nemá žádné uzly. Bez této volby musí mnoho algoritmů testovat tento speciální případ a zpracovávat jej samostatně. Naproti tomu použití null k označení prázdného lineárního seznamu je přirozenější a často vytváří méně zvláštních případů.

Pomocí sentinelových uzlů

Uzel Sentinel může zjednodušit určité operace se seznamem tím, že zajistí, aby pro každý prvek existovaly další nebo předchozí uzly a že i prázdné seznamy mají alespoň jeden uzel. Lze také použít sentinelový uzel na konci seznamu s příslušným datovým polem k odstranění některých testů na konci seznamu. Například při skenování seznamu hledajícího uzel s danou hodnotou x je nastavení datového pole sentinelu na x zbytečné testovat konec seznamu uvnitř smyčky. Dalším příkladem je sloučení dvou seřazených seznamů: pokud mají jejich strážci datová pole nastavená na +∞, volba dalšího výstupního uzlu nepotřebuje zvláštní zpracování prázdných seznamů.

Sentinelové uzly však zabírají více místa (zejména v aplikacích, které používají mnoho krátkých seznamů) a mohou komplikovat další operace (například vytvoření nového prázdného seznamu).

Pokud se však kruhový seznam používá pouze k simulaci lineárního seznamu, lze se některé této složitosti vyhnout přidáním jednoho sentinelového uzlu do každého seznamu mezi poslední a první datový uzel. U této konvence se prázdný seznam skládá pouze ze sentinelového uzlu, který na sebe ukazuje přes odkaz na další uzel. Pokud není seznam prázdný, měl by být popisovač seznamu ukazatelem na poslední datový uzel před sentinelem; nebo na samotný hlídač, je -li seznam prázdný.

Stejný trik lze použít ke zjednodušení zpracování dvojitě propojeného lineárního seznamu tím, že jej změníte na kruhový dvojitě propojený seznam s jediným sentinelovým uzlem. V tomto případě by však měl být popisovač jediným ukazatelem na samotný fiktivní uzel.

Operace propojeného seznamu

Při manipulaci s propojenými seznamy na místě je třeba dbát na to, abyste nepoužívali hodnoty, které jste v předchozích přiřazeních zneplatnili. Díky tomu jsou algoritmy pro vkládání nebo mazání uzlů propojeného seznamu poněkud subtilní. Tato část poskytuje pseudokód pro přidávání nebo odebírání uzlů z jednotlivě, dvojitě a kruhově propojených seznamů na místě. V celém textu budeme používat null k označení značky na konci seznamu nebo hlídače , které lze implementovat několika způsoby.

Lineárně propojené seznamy

Jednotlivé seznamy

Naše datová struktura uzlu bude mít dvě pole. Také uchováváme proměnnou firstNode, která vždy ukazuje na první uzel v seznamu, nebo je pro prázdný seznam nulová .

record Node
{
    data; // The data being stored in the node
    Node next // A reference to the next node, null for last node
}

record List
{
    Node firstNode // points to first node of list; null for empty list
}

Přechod jednotlivě propojeného seznamu je jednoduchý, začíná v prvním uzlu a sleduje každý další odkaz, dokud se nedostaneme na konec:

node := list.firstNode
while node not null
    (do something with node.data)
    node := node.next

Následující kód vloží uzel za existující uzel v jednotlivě propojeném seznamu. Diagram ukazuje, jak to funguje. Vložení uzlu před existující nelze provést přímo; místo toho je třeba sledovat předchozí uzel a vložit za něj uzel.

Schéma vložení uzlu do jednotlivě propojeného seznamu

function insertAfter(Node node, Node newNode) // insert newNode after node
    newNode.next := node.next
    node.next    := newNode

Vložení na začátek seznamu vyžaduje samostatnou funkci. To vyžaduje aktualizaci firstNode .

function insertBeginning(List list, Node newNode) // insert node before current first node
    newNode.next   := list.firstNode
    list.firstNode := newNode

Podobně máme funkce pro odebrání uzlu za daným uzlem a pro odebrání uzlu ze začátku seznamu. Diagram ukazuje první. Abyste našli a odstranili konkrétní uzel, musíte znovu sledovat předchozí prvek.

Schéma odstranění uzlu z jednotlivě propojeného seznamu

function removeAfter(Node node) // remove node past this one
    obsoleteNode := node.next
    node.next := node.next.next
    destroy obsoleteNode

function removeBeginning(List list) // remove first node
    obsoleteNode := list.firstNode
    list.firstNode := list.firstNode.next // point past deleted node
    destroy obsoleteNode

Všimněte si, že se removeBeginning()nastaví list.firstNodena nullpři odebírání posledního uzlu v seznamu.

Vzhledem k tomu, že nemůžeme iterovat zpět, nejsou efektivní insertBeforeani removeBeforeoperace možné. Vložení do seznamu před konkrétní uzel vyžaduje procházení seznamu, což by mělo v nejhorším případě dobu běhu O (n).

Připojování jednoho propojeného seznamu k jinému může být neúčinné, pokud není jako součást struktury seznamu zachován odkaz na konec, protože musíme najít celý první seznam, abychom našli ocas, a poté k němu připojit druhý seznam. Tak, jestliže dva lineární spojové seznamy jsou každý o délce seznam připojením má asymptotické časovou složitost a . V rodině jazyků Lisp je připojení seznamu zajištěno postupem. ${\ displaystyle n}$${\ Displaystyle O (n)}$append

Mnoho zvláštních případů operací spojených se seznamem lze eliminovat vložením fiktivního prvku na začátek seznamu. Tím je zajištěno, že neexistují žádné zvláštní případy na začátku seznamu a činí tak insertBeginning()i removeBeginning()zbytečné. V tomto případě první užitečné údaje v seznamu najdete na . list.firstNode.next

Kruhově propojený seznam

V kruhově propojeném seznamu jsou všechny uzly propojeny v souvislém kruhu bez použití hodnoty null. U seznamů s předním a zadním seznamem (jako je fronta) se uloží odkaz na poslední uzel v seznamu. Další uzel po posledním uzlu je první uzel. Prvky lze přidávat na konec seznamu a odebírat zepředu v konstantním čase.

Kruhově propojené seznamy mohou být propojeny jednotlivě nebo dvakrát.

Oba typy cyklicky propojených seznamů těží ze schopnosti procházet celý seznam počínaje kterýmkoli daným uzlem. To nám často umožňuje vyhnout se ukládání firstNode a lastNode , ačkoli pokud může být seznam prázdný, potřebujeme pro prázdný seznam speciální reprezentaci, například proměnnou lastNode, která ukazuje na nějaký uzel v seznamu nebo je nulová, pokud je prázdná; zde používáme takový lastNode . Tato reprezentace výrazně zjednodušuje přidávání a odebírání uzlů pomocí neprázdného seznamu, ale prázdné seznamy jsou pak speciální případ.

Algoritmy

Za předpokladu, že someNode je nějaký uzel v neprázdném kruhovém jednotlivě propojeném seznamu, tento kód iteruje tímto seznamem počínaje someNode :

function iterate(someNode)
    if someNode ≠ null
        node := someNode
    do
        do something with node.value
        node := node.next
    while node ≠ someNode

Všimněte si, že test „ while node ≠ someNode“ musí být na konci smyčky. Pokud by byl test přesunut na začátek smyčky, postup by selhal, kdykoli by seznam měl pouze jeden uzel.

Tato funkce vloží uzel „newNode“ do kruhového propojeného seznamu za daný „uzel“ daného uzlu. Pokud je "uzel" null, předpokládá, že je seznam prázdný.

function insertAfter(Node node, Node newNode)
    if node = null    // assume list is empty
        newNode.next := newNode
    else
        newNode.next := node.next
        node.next := newNode
    update lastNode variable if necessary

Předpokládejme, že "L" je proměnná směřující k poslednímu uzlu kruhového propojeného seznamu (nebo null, je -li seznam prázdný). Chcete -li připojit „newNode“ na konec seznamu, udělejte to

insertAfter(L, newNode)
L := newNode

Chcete -li vložit „newNode“ na začátek seznamu, můžete to udělat

insertAfter(L, newNode)
if L = null
    L := newNode

Tato funkce vloží hodnotu „newVal“ před „uzel“ daného uzlu v čase O (1). Vytvoříme nový uzel mezi „uzlem“ a dalším uzlem a poté do tohoto nového uzlu vložíme hodnotu „uzlu“ a do „uzlu“ vložíme „novýVal“. Jednoduše spojený kruhově propojený seznam pouze s proměnnou firstNode lze tedy vložit do přední i zadní části v čase O (1).

function insertBefore(Node node, newVal)
    if node = null    // assume list is empty
        newNode := new Node(data:=newVal, next:=newNode)
    else
        newNode := new Node(data:=node.data, next:=node.next)
        node.data := newVal
        node.next := newNode
    update firstNode variable if necessary

Tato funkce odstraní nenulový uzel ze seznamu o velikosti větší než 1 v čase O (1). Zkopíruje data z dalšího uzlu do uzlu a poté nastaví další ukazatel uzlu, aby přeskočil další uzel.

function remove(Node node)
    if node ≠ null and size of list > 1
        removedData := node.data
        node.data := node.next.data
        node.next = node.next.next
        return removedData

Propojené seznamy pomocí polí uzlů

Jazyky, které nepodporují žádný typ odkazu, mohou stále vytvářet odkazy nahrazením ukazatelů indexy pole. Tento přístup je dávat pole o záznamů , kde každý záznam má celé číslo pole označující index následující (a případně předchozí) uzlu v poli. Není nutné použít všechny uzly v poli. Pokud nejsou podporovány ani záznamy, lze místo toho často použít paralelní pole .

Jako příklad zvažte následující záznam propojeného seznamu, který místo ukazatelů používá pole:

record Entry {
    integer next; // index of next entry in array
    integer prev; // previous entry (if double-linked)
    string name;
    real balance;
}

Propojený seznam lze vytvořit vytvořením pole těchto struktur a celočíselnou proměnnou pro uložení indexu prvního prvku.

integer listHead
Entry Records[1000]

Vazby mezi prvky jsou vytvořeny umístěním indexu pole další (nebo předchozí) buňky do pole Další nebo Předchozí v rámci daného prvku. Například:

Ve výše uvedeném příkladu ListHeadby bylo nastaveno na 2, umístění prvního záznamu v seznamu. Všimněte si, že položky 3 a 5 až 7 nejsou součástí seznamu. Tyto buňky jsou k dispozici pro jakékoli doplnění seznamu. Vytvořením ListFreeceločíselné proměnné lze vytvořit bezplatný seznam pro sledování dostupných buněk. Pokud jsou použity všechny položky, musela by být velikost pole zvětšena nebo některé prvky odstraněny, než by mohly být nové položky uloženy v seznamu.

Následující kód by procházel seznamem a zobrazovanými jmény a zůstatkem na účtu:

i := listHead
while i ≥ 0 // loop through the list
    print i, Records[i].name, Records[i].balance // print entry
    i := Records[i].next

Když stojí před volbou, výhody tohoto přístupu zahrnují:

• Propojený seznam je přemístitelný, což znamená, že jej lze libovolně přesouvat v paměti a lze jej také rychle a přímo serializovat pro ukládání na disk nebo přenos přes síť.
• Zejména u malého seznamu mohou indexy polí zabírat podstatně méně místa než plný ukazatel na mnoha architekturách.
• Lokalitu reference lze zlepšit udržováním uzlů pohromadě v paměti a pravidelným přeskupováním, i když to lze také provést v obchodě se smíšeným zbožím.
• Naivní dynamické alokátory paměti mohou produkovat nadměrné množství režijního úložiště pro každý přidělený uzel; v tomto přístupu nevzniká téměř žádná alokační režie na uzel.
• Převzetí položky z předem přiděleného pole je rychlejší než použití dynamické alokace paměti pro každý uzel, protože dynamická alokace paměti obvykle vyžaduje hledání bloku volné paměti požadované velikosti.

Tento přístup má však jednu hlavní nevýhodu: vytváří a spravuje soukromý paměťový prostor pro své uzly. To vede k následujícím problémům:

• Zvyšuje složitost implementace.
• Rozmnožování velkého pole, když je plné, může být obtížné nebo nemožné, zatímco hledání místa pro nový uzel propojeného seznamu ve velké, obecné oblasti paměti může být snazší.
• Přidání prvků do dynamického pole bude příležitostně (když je plné) nečekaně trvat lineární ( O (n)) místo konstantního času (i když je to stále amortizovaná konstanta).
• Pokud je seznam menší, než se očekávalo, nebo pokud se uvolní mnoho uzlů, použití obecného fondu paměti ponechá více paměti pro jiná data.

Z těchto důvodů se tento přístup používá hlavně pro jazyky, které nepodporují dynamické přidělování paměti. Tyto nevýhody jsou také zmírněny, pokud je v době vytvoření pole známá maximální velikost seznamu.

Jazyková podpora

Mnoho programovacích jazyků, jako je Lisp a Scheme, má zabudované jednotlivě propojené seznamy. V mnoha funkčních jazycích jsou tyto seznamy sestaveny z uzlů, kterým se každý říká buňka proti nebo proti . Nevýhody mají dvě pole: auto , odkaz na data pro tento uzel a cdr , odkaz na další uzel. Přestože lze buňky Cons použít k vytváření dalších datových struktur, je to jejich primární účel.

V jazycích, které podporují abstraktní datové typy nebo šablony, jsou k dispozici propojené seznamy ADT nebo šablony pro vytváření propojených seznamů. V jiných jazycích se propojené seznamy obvykle vytvářejí pomocí odkazů společně se záznamy .

Interní a externí úložiště

Při konstrukci propojeného seznamu stojí před volbou, zda data seznamu uložit přímo do uzlů propojeného seznamu, nazývaných interní úložiště , nebo pouze uložit odkaz na data, nazývaný externí úložiště . Interní úložiště má tu výhodu, že zefektivňuje přístup k datům, vyžaduje celkově méně úložiště, má lepší referenční lokalitu a zjednodušuje správu paměti pro seznam (jeho data jsou přidělována a uvolňována současně s uzly seznamu).

Externí úložiště má naopak tu výhodu, že je obecnější, protože pro propojený seznam lze použít stejnou datovou strukturu a strojový kód bez ohledu na velikost dat. Umožňuje také snadné umístění stejných dat do více propojených seznamů. Ačkoli s interním úložištěm lze stejná data umístit do více seznamů zahrnutím více dalších odkazů do datové struktury uzlu, bylo by pak nutné vytvořit samostatné rutiny pro přidání nebo odstranění buněk na základě každého pole. Je možné vytvořit další propojené seznamy prvků, které používají interní úložiště, pomocí externího úložiště a buňky dalších propojených seznamů ukládají odkazy na uzly propojeného seznamu obsahující data.

Obecně platí, že pokud je třeba do propojených seznamů zahrnout sadu datových struktur, je nejlepším přístupem externí úložiště. Pokud musí být sada datových struktur zahrnuta pouze do jednoho propojeného seznamu, pak je vnitřní úložiště o něco lepší, pokud není k dispozici generický balíček propojeného seznamu využívající externí úložiště. Podobně, pokud mají být do jednoho propojeného seznamu zahrnuty různé sady dat, která mohou být uložena ve stejné datové struktuře, pak by bylo vhodné interní úložiště.

Další přístup, který lze v některých jazycích použít, zahrnuje různé datové struktury, ale všechna mají počáteční pole, včetně odkazů na další (a předchozí, pokud je dvojitě propojený seznam) na stejném místě. Po definování samostatných struktur pro každý typ dat lze definovat obecnou strukturu, která obsahuje minimální množství dat sdílených všemi ostatními strukturami a obsažených v horní části (začátku) struktur. Potom lze vytvořit obecné rutiny, které používají minimální strukturu k provádění operací typu propojeného seznamu, ale konkrétní rutiny pak mohou zpracovávat konkrétní data. Tento přístup se často používá v rutinách analýzy zpráv, kde je přijímáno několik typů zpráv, ale všechny začínají stejnou sadou polí, obvykle včetně pole pro typ zprávy. Obecné rutiny se používají k přidání nových zpráv do fronty, když jsou přijaty, a jejich odebrání z fronty za účelem zpracování zprávy. Pole typu zprávy se pak používá k volání správné rutiny ke zpracování konkrétního typu zprávy.

Příklad interního a externího úložiště

Předpokládejme, že byste chtěli vytvořit propojený seznam rodin a jejich členů. Při použití interního úložiště může struktura vypadat takto:

record member { // member of a family
    member next;
    string firstName;
    integer age;
}
record family { // the family itself
    family next;
    string lastName;
    string address;
    member members // head of list of members of this family
}

Chcete -li vytisknout kompletní seznam rodin a jejich členů pomocí interního úložiště, mohli bychom napsat:

aFamily := Families // start at head of families list
while aFamily ≠ null // loop through list of families
    print information about family
    aMember := aFamily.members // get head of list of this family's members
    while aMember ≠ null // loop through list of members
        print information about member
        aMember := aMember.next
    aFamily := aFamily.next

Pomocí externího úložiště bychom vytvořili následující struktury:

record node { // generic link structure
    node next;
    pointer data // generic pointer for data at node
}
record member { // structure for family member
    string firstName;
    integer age
}
record family { // structure for family
    string lastName;
    string address;
    node members // head of list of members of this family
}

Chcete -li vytisknout kompletní seznam rodin a jejich členů pomocí externího úložiště, mohli bychom napsat:

famNode := Families // start at head of families list
while famNode ≠ null // loop through list of families
    aFamily := (family) famNode.data // extract family from node
    print information about family
    memNode := aFamily.members // get list of family members
    while memNode ≠ null // loop through list of members
        aMember := (member)memNode.data // extract member from node
        print information about member
        memNode := memNode.next
    famNode := famNode.next

Všimněte si, že když používáte externí úložiště, je potřeba extra krok k extrahování záznamu z uzlu a jeho přenesení do správného datového typu. Důvodem je, že jak seznam rodin, tak seznam členů v rámci rodiny jsou uloženy ve dvou propojených seznamech využívajících stejnou datovou strukturu ( uzel ) a tento jazyk nemá parametrické typy.

Dokud je v době kompilace znám počet rodin, do kterých může člen patřit, funguje interní úložiště dobře. Pokud by však člen potřeboval být zahrnut do libovolného počtu rodin s konkrétním počtem známým pouze za běhu, bylo by nutné externí úložiště.

Zrychlení vyhledávání

Nalezení konkrétního prvku v propojeném seznamu, i když je seřazeno, obvykle vyžaduje čas O ( n ) ( lineární vyhledávání ). Toto je jedna z hlavních nevýhod propojených seznamů oproti jiným datovým strukturám. Kromě výše uvedených variant jsou níže uvedeny dva jednoduché způsoby, jak zkrátit dobu hledání.

V neuspořádaném seznamu je jednou jednoduchou heuristikou pro zkrácení průměrného času hledání heuristika přesunu na začátek, která jednoduše přesune prvek na začátek seznamu, jakmile je nalezen. Toto schéma, praktické pro vytváření jednoduchých keší, zajišťuje, že naposledy použité položky lze také nejrychleji znovu najít.

Dalším běžným přístupem je „ indexování “ propojeného seznamu pomocí efektivnější externí datové struktury. Například lze vytvořit červeno -černý strom nebo hashovací tabulku, jejíž prvky jsou odkazy na uzly propojeného seznamu. Na jednom seznamu lze vytvořit více takových indexů. Nevýhodou je, že tyto indexy může být nutné aktualizovat pokaždé, když je uzel přidán nebo odebrán (nebo alespoň předtím, než bude tento index znovu použit).

Seznamy náhodného přístupu

Seznam náhodného přístupu je seznam s podporou rychlého náhodného přístupu ke čtení nebo úpravě jakéhokoli prvku v seznamu. Jednou z možných implementací je šikmý binární seznam s náhodným přístupem pomocí systému šikmých binárních čísel , který zahrnuje seznam stromů se speciálními vlastnostmi; to umožňuje operace hlavy/nevýhody konstantní časové konstanty v nejhorším případě a logaritmický časově náhodný přístup k prvku podle indexu. Seznamy náhodného přístupu lze implementovat jako trvalé datové struktury .

Seznamy s náhodným přístupem lze považovat za neměnné propojené seznamy v tom smyslu, že rovněž podporují stejné operace hlavy a ocasu O (1).

Jednoduchým rozšířením seznamů s náhodným přístupem je min-list , který poskytuje další operaci, která poskytuje minimální prvek v celém seznamu v konstantním čase (bez složitosti mutací).

Související datové struktury

Oba zásobníky a fronty jsou často realizovány pomocí provázané seznamy a jednoduše omezit typ operací, které jsou podporovány.

Seznam přeskočení je propojený seznam rozšířený o vrstvy ukazatelů pro rychlé přeskakování velkého počtu prvků a následný sestup do další vrstvy. Tento proces pokračuje až do spodní vrstvy, což je skutečný seznam.

Na binární strom lze pohlížet jako na typ propojeného seznamu, kde prvky jsou samy propojenými seznamy stejné povahy. Výsledkem je, že každý uzel může obsahovat odkaz na první uzel jednoho nebo dvou dalších propojených seznamů, které spolu s jejich obsahem tvoří podstromy pod tímto uzlem.

Rozvinul spojový seznam je spojový seznam, ve kterém každý uzel obsahuje pole datových hodnot. To vede ke zlepšenému výkonu mezipaměti , protože více prvků seznamu na sebe navazuje v paměti a snižuje režii paměti, protože pro každý prvek seznamu je třeba uložit méně metadat.

Tabulka hash může použít propojené seznamy k uložení řetězců položek, které mají hodnotu hash na stejné pozici v tabulce hash.

A haldy sdílí některé vlastnosti objednávkových z připojeného seznamu, ale je téměř vždy realizovány pomocí pole. Namísto odkazů z uzlu na uzel se další a předchozí datové indexy vypočítávají pomocí indexu aktuálních dat.

Seznam samoorganizující se přeskupuje své uzly na základě nějaké heuristiky, která snižuje hledat časy pro získávání dat při zachování běžně přístupné uzlů v čele seznamu.

Poznámky

Reference

Další čtení

• Juan, Angel (2006). „Ch20 –Data Structures; ID06 - PROGRAMOVÁNÍ s JAVA (snímek z knihy„ Velká Java “, CayS. Horstmann)“ (PDF) . p. 3. Archivováno z originálu (PDF) 6. ledna 2012 . Citováno 2011-07-10 .
• Black, Paul E. (2004-08-16). Pieterse, Vreda; Black, Paul E. (eds.). „propojený seznam“ . Slovník algoritmů a datových struktur . Národní institut pro standardy a technologie . Citováno 2004-12-14 .
• Antonakos, James L .; Mansfield, Kenneth C., Jr. (1999). Praktické datové struktury pomocí C/C ++ . Prentice-Hall. s.  165–190 . ISBN 0-13-280843-9.
• Collins, William J. (2005) [2002]. Datové struktury a rámec Java Collections Framework . New York: McGraw Hill. s. 239–303. ISBN 0-07-282379-8.
• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2003). Úvod do algoritmů . Stiskněte MIT. s. 205–213, 501–505. ISBN 0-262-03293-7.
• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). „10.2: Propojené seznamy“. Úvod do algoritmů (2. vyd.). Stiskněte MIT. s. 204–209. ISBN 0-262-03293-7.
• Green, Bert F., Jr. (1961). „Počítačové jazyky pro manipulaci se symboly“. Transakce IRE na lidské faktory v elektronice (2): 3–8. doi : 10,1109/THFE2.1961.4503292 .
• McCarthy, John (1960). „Rekurzivní funkce symbolických výrazů a jejich výpočet strojově, část I“ . Komunikace ACM . 3 (4): 184. doi : 10,1145/367177,367199 .
• Knuth, Donald (1997). „2.2.3-2.2.5“. Základní algoritmy (3. vyd.). Addison-Wesley. s. 254–298. ISBN 0-201-89683-4.
• Newell, Allen ; Shaw, FC (1957). „Programování stroje logické teorie“. Proceedings of the Western Joint Computer Conference : 230–240.
• Parlante, Nick (2001). „Základy propojeného seznamu“ (PDF) . Stanfordská univerzita . Citováno 2009-09-21 .
• Sedgewick, Robert (1998). Algoritmy v C . Addison Wesley. s.  90–109 . ISBN 0-201-31452-5.
• Shaffer, Clifford A. (1998). Praktický úvod do datových struktur a analýzy algoritmů . New Jersey: Prentice Hall. s. 77–102. ISBN 0-13-660911-2.
• Wilkes, Maurice Vincent (1964). „Experiment s vlastním kompilátorem pro jednoduchý jazyk pro zpracování seznamu“. Roční kontrola v automatickém programování . Pergamon Press. 4 (1): 1. doi : 10,1016/0066-4138 (64) 90013-8 .
• Wilkes, Maurice Vincent (1964). „Seznamy a proč jsou užitečné“. Výnosy z národní konference ACM, Philadelphia 1964 . ACM (P – 64): F1–1.
• Shanmugasundaram, Kulesh (2005-04-04). „Seznam propojených jader Linuxu vysvětlen“ . Citováno 2009-09-21 .

externí odkazy

• Popis ze slovníku algoritmů a datových struktur
• Úvod do propojených seznamů , Stanfordská univerzitní knihovna počítačových věd
• Linked List Problems , Stanford University Computer Science Library
• Otevřené datové struktury - Kapitola 3 - Propojené seznamy , Pat Morin
• Patent na myšlenku mít uzly, které jsou v několika propojených seznamech současně (všimněte si, že tato technika byla široce používána po mnoho desetiletí před udělením patentu)