7. Obojsmerný lineárny zoznam

7.1  Čo je to?

Obojsmerný lineárny zoznam sa od jednosmerného lineárneho zoznamu líši tým, že každý jeho uzol obsahuje dva ukazovatele:

  • ukazovateľ na nasledujúci uzol
  • ukazovateľ na predchádzajúci uzol
Samozrejme, keďže prvý uzol zoznamu nemá predchodcu a posledný uzol zoznamu nemá zase nasledovníka, hodnoty príslušných ukazovateľov sú NULL.

Nový údajový typ pre uzly obojsmerného lineárneho zoznamu celých čísel definujeme napr. takto:

typedef struct uzol {
  int hodnota;
  struct uzol *nasled;
  struct uzol *predch;
} TUzol;
Graficky by sme mohli túto dynamickú štruktúru reprezentovať takto:

Výhody obojsmerného lineárneho zoznamu:

  • môžeme ho prezerať oboma smermi (od začiatku aj od konca)
  • okrem nasledovníka máme prístup vždy aj k predchodcovi aktuálneho prvku (t.j. toho, na ktorý práve ukazuje smerník).
Pri riešení mnohých úloh sa aj zásobník či rad môžu implementovať ako obojsmerné linárne zoznamy!

Precvičme si

  Vytvorte program, ktorý umožní vo forme menu pracovať s obojsmerným lineárnym zoznamom (vytvorenie zoznamu; pridávanie nových prvkov na koniec; odoberanie prvkov, ktoré vyhovujú nejakej podmienke; výpis prvkov zoznamu oboma smermi; vloženie prvku do vnútra zoznamu). Prvkami zoznamu nech sú celé čísla.

[Riešenie]

  Napíšte program, ktorý načíta zo vstupu reťazec znakov ukončený bodkou, ktorý po znakoch uloží do obojsmerného lineárneho zoznamu, a následne overí, či je zadaný reťazec palindrom (t.j. či je rovnaký odpredu i odzadu).

[Riešenie]