Lineární spojový seznam

Z CHWiki

http://tutchek.igroup.cz/wiki/spojak-ico.gif (angl. Linked list)

Obsah 1 Popis 2 Složitost 3 Implementace 4 Algoritmy 4.1 Vložení prvku na konec 4.2 Vložení prvku X za prvek Y 4.3 Smazání posledního prvku 4.4 Smazání prvku X 4.5 Vyhledání prvku X

[editovat] Popis

Lineární spojový seznam je datová struktura určená k ukládání dat předem neznámé délky. Program obsahuje ukazatel na první prvek seznamu (volitelně i na poslední prvek. V případě, že není ukazatel na poslední prvek seznamu neplatí složitosti u vkládání a mazání z konce). Každý prvek seznamu obsahuje data a ukazatel na další prvek seznamu. Je-li seznam obousměrný lineární spojový seznam obsahuje každý prvek i ukazatel na předchozí prvek. První a případně poslední prvek mají ukazatel na následovníka resp. předchůdce nastavený na NIL.

[editovat] Složitost

• Vložení prvku na konec - O(1)
• Vložení prvku X za prvek Y - O(n)
• Delete prvku na konci - O(1)
• Delete prvku X - O(n)
• Vyhledání prvku X - O(n)

[editovat] Implementace

Mnoha způsoby, my zde zavedeme tuto (jedná se o obousměrný lineární spojiový seznam):

struktura prvek:

• data: libovolný datový typ - informace ukládaná do seznamu
• dalsi: ukazatel na prvek
• predchozi: ukazatel na prvek

struktura seznam:

• prvni: ukazatel na prvek - výchozí hodnota NIL
• posledni: ukazatel na prvek - výchozí hodnota NIL

[editovat] Algoritmy

[editovat] Vložení prvku na konec

1. Vytvoř objekt X typu prvek
2. X.data = data, X.dalsi = NIL
3. Pokud seznam.posledni = NIL: seznam.prvni = ukazatel(X), seznam.posledni = ukazatel(X), X.predchozi = NIL

[editovat] Vložení prvku X za prvek Y

1. Vytvoř objekt X typu prvek
2. uk = Find(Y)
3. Pokud uk není NIL
   1. X.dalsi = uk.dalsi
   2. uk.dalsi = ukazatel(X)
   3. X.predchozi = uk
   4. Pokud seznam.posledni == uk, potom seznam.posledni = ukazatel(X)

[editovat] Smazání posledního prvku

1. uk = seznam.posledni.predchozi
2. Smaž seznam.posledni
3. seznam.posledni = uk
4. Pokud uk == NIL, potom seznam.prvni = NIL, jinak uk.dalsi = NIL

[editovat] Smazání prvku X

1. uk = Find(X)
2. Pokud uk není NIL
   1. Pokud seznam.posledni == uk, potom seznam.posledni = uk.predchozi
   2. Pokud seznam.prvni == uk, potom seznam.prvni = uk.dalsi
   3. Pokud uk.predchozi není NIL, potom uk.predchozi.dalsi = uk.dalsi
   4. Pokud uk.dalsi není NIL, potom uk.dalsi.predchozi = uk.predchozi
   5. Smaž uk

[editovat] Vyhledání prvku X

1. uk = seznam.prvni
2. Dokud platí: (uk není NIL) a zároveň (uk není X) opakuj:
   1. uk = uk.dalsi
3. Návratová hodnota = uk