ALG7

5.2. Tablicowa implementacja list 127

5.2.3.Listy innych typów

Listy jednokierunkowe są bardzo wygodne w stosowaniu i zajmują stosunkowo mało pamięci. Tym niemniej operacje na nich niekiedy zajmują dużo czasu. Zauważyło ten fakt sporo ludzi i tym sposobem zostały wymyślone inne typy list, np.:

lista dwukierunkowa - komórka robocza zawiera wskaźniki do elementów: poprzedniego i następnego:

Rys. S -13. Lista dwukierunkowa.

•    pierwsza komórka znajdująca się w liście nie posiada swojego poprzednika; zaznaczamy to wpisując wartość NULL do pola poprzedni;

•    ostatnia komórka znajdująca się w liście nie posiada swojego następnika; zaznaczamy to wpisując wartość NULL do pola następny. Lista dwukierunkowa jest dość „kosztowna”, jeśli chodzi o zajętość pamięci, tym niemniej czasami ważniejsza jest szybkość działania od ewentualnych strat pamięci.

Struktura wewnętrzna listy dwukierunkowej jest oczywista:

typedef struct rob

{

Iint wartość;

struct rob 'następny; struct rob 'poprzedni;

(ELEMENT;

Załóżmy teraz, że podczas przeglądania elementów listy zapamiętaliśmy wskaźnik pozycji bieżącej p. (Przykładowo szukaliśmy elementu spełniającego pewien warunek i na wskaźniku p nasze poszukiwania zakończyły się sukcesem).

I    Jak usunąć elementp z listy'? Jak pamiętamy z paragrafów poprzednich, do pra

widłowego wykonania tej operacji niezbędna była znajomość wskaźników przed i po, wskazujących odpowiednio na komórki poprzednią i następną. W przypadku listy dwukierunkowej w' komórce wskazywanej przez p tc dwie informacje już się znajdują i wystarczy tylko po nie sięgnąć:

void usunżkier(ELEMENT *p)

(

if(p->poprzedni!-NULL)    II nie jest to element pierwszy

p->poprzećni->nastepny=p->nastepny; if(p->nastcpny!-NULL)    II nic jest to element ostatni

p->nastepr.y->poprzedni=p->poprzedni;

)