95924

Dostęp do elementu: jeżeli element jest umieszczony na końcu listy, to aby do niego dotrzeć, trzeba przejrzeć wszystkie pozostałe n-1 elementów - O(n).

Wyszukanie:

Wyszukanie elementu: jak wyżej _ O(n).

Wstawienie:

Wstawienie elementu: należy utworzyć nową komórkę 0(1), wypełnić wartość pola danych 0(1), pole wska^Łnika wypełnić wartością głowy 0(1), a wartość głowy wypełnić wartością wskazującą na nowy element 0(1) _ całkowity czas omawianej operacji wynosi zatem 0(1).

Usunięcie:

Usunięcie elementu: wartość wska¹nika elementu poprzedzającego należy wypełnić wartością wskazującą na element następny 0(n) (trzeba ten wska-^Anik znale¹ć!) i usunąć z pamięci dany element 0(1) _ 0(n).

Lista dwukierunkowa Budowa:

każdy element, oprócz wartości i wska¹nika na następny element zawiera też wska^Anik na element poprzedzający , a oprócz głowy zawiera też (choć nie jest to konieczne) tzw. ogon, czyli wska^xnik na ostatni element struktury.

Złożoność obliczeniowa Wyszukanie:

skraca operacje wyszukiwania elementu w najgorszym wypadku o połowę , jednak z punktu widzenia efektywności to nadal jest złożoność tego samego rzędu (0(n/2) = 0(n)).

Wstawienie:

Skraca w najgorszym wypadku o połowę , jednak z punktu widzenia efektywności to nadal jest złożoność tego samego rzędu (0(n/2) = O(n)).

Usunięcie:

Skraca w najgorszym wypadku o połowę , jednak z punktu widzenia efektywności to nadal jest złożoność tego samego rzędu (0(n/2) = 0(n)).

Lista cykliczna Budowa:

wskaźnik ostatniego elementu wskazuje na pierwszy element Złożoność obliczeniowa

jak wyżej

Lista samoorganizująca się Opis:

elementy w strukturze są uporządkowane niemalejąco lub nierosnąco (względem wartości pól danych).

Cechy charakterystyczne:

Korzyści pojawiają się w niektórych szczególnych sytuacjach (gdy np. interesuj ąnas głównie maksymalne / minimalne elementy).

Złożoność obliczeniowa Wstawienie: