2277150872

Elementy takiej listy połączone są dwukierunkowo, co widać na poniższym rysunku:

NULL

Lista dwukierunkowa.Pole p wskazuje na element poprzedni, pole n na następny.

Wzdłuż całej listy dwukierunkowej można swobodnie poruszać się za pomocą wskaźników w obie strony. Dlatego, posiadając dowolny element listy dwukierunkowej, mamy dostęp do wszystkich pozostałych. Nie było to tak do końca możliwe w przypadku list j ednokierunkowych.

Ponieważ lista w ogólnym przypadku zaczyna się jakimś elementem i jakimś elementem się kończy (z wyjątkiem przypadków cyklicznych), początek listy przyjęto nazywać głową listy (head), zaś koniec - ogonem (taił). Dowolny element jest węzłem lub nodem (node).

Lista dwukierunkowa to tak jakby dwie listy jednokierunkowe zrealizowane wewnątrz jednej struktury. Charakterystyczne jest to, że wewnątrz jednego elementu wskaźniki pokazują na element poprzedni oraz na element następny. Jeżeli określimy inaczej, na co mają one wskazywać, np. oba na elementy następne, otrzymamy zamiast listy inną strukturę - drzewo.

KOLEJKI

Listy mogą być zależnie od sposobu obsługi traktowane inaczej. Znane są np. kolejki, czyli lista jednokierunkowa obsługiwana tak specyficznie, że pierwszy wstawiony element jest także pierwszym dającym się z listy odczytać (tzw. kolejka FIFO - First in, First out -dokładne odwzorowanie normalnej kolejki przed sklepem mięsnym w czasach kryzysu).

STOSY

Stos jest implementacją listy jednokierunkowej, która pozwana na wstawianie elementu do struktury, a potem na odzyskiwanie ich w odwrotnej kolejności - czyli pierwszy wstawiony jest ostatnim wyjętym, dokładnie tak, jakby ktoś rzucał dane na kupę, lub stos.

Jest to również wersja kolejki LIFO (last in - first out - ostatni wchodzi, pierwszy wychodzi, pasuje to trochę do pewnego rodzaju studentów).

DRZEWA

Drzewa oferują niezwykle mały czas dostępu do swoich elementów (zakładając, że są zoptymalizow ane, lub wyważone). Struktura węzła najprostszego drzewa jest identyczna jak w przypadku listy dwukierunkowej:

struct BTree {

BTree *lewy, *prawy;

/* .... dane ... */

}

Strona 5 z 41