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ść wska1nika elementu poprzedzającego należy wypełnić wartością wskazującą na element następny 0(n) (trzeba ten wska-Anik znale1ć!) i usunąć z pamięci dany element 0(1) _ 0(n).
Lista dwukierunkowa Budowa:
każdy element, oprócz wartości i wska1nika na następny element zawiera też wskaAnik na element poprzedzający , a oprócz głowy zawiera też (choć nie jest to konieczne) tzw. ogon, czyli wskaxnik 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: