Lista
Z Wikipedii
Lista to struktura danych używana w infomatyce. Jest to pojemnik składający się z połączonych ze sobą w łańcuszek komórek zawierających dane.
Spis treści |
[edytuj] Popularne sposoby łączenia elementów listy
Typowa lista jest łączona jednostronnie - komórki zawierają tylko odnośnik do kolejnej komórki. Innym przypadkiem jest lista dwustronna, gdzie komórki zawierają także odnośnik do poprzednika.
Popularna jest także lista zwana słownikową, która zazwyczaj jest wariacją listy jednostronnej. Z reguły stosuje się ją tam, gdzie elementy listy zawierają kilka pól z danymi, a kolejny element może rozszerzać pojęcie (definicję poprzedniego). Przykładem jest prosty translator tekstu, zrealizowany jako lista, gdzie każdy z elementów zawiera dane wyraz i definicja wyrazu - może się okazać, że definicja danego wyrazu ma swoje rozwinięcie (definicję) w pewnym innym elemencie, wówczas tam kieruje się dodatkowy łącznik.
[edytuj] Implementacja listy
Istnieją dwie popularne implementacje struktury listy: tablicowa i wskaźnikowa.
[edytuj] Tablicowa
Jak wskazuje nazwa, lista zaimplementowana w ten sposób opiera się na tablicy obiektów (lub rekordów) danego typu.
Dopisanie elementu do listy to wstawienie elementu do tablicy:
- jeśli ma ono nastąpić na końcu listy, będzie to kolejny element w tablicy;
- jeśli nowy element ma znaleźć się między innymi elementami, należy przesunąć o jedno pole w prawo wszystkie elementy o indeksie wyższym niż pole, na które będzie wstawiany obiekt; następnie w powstałą lukę wpisuje się nowy element.
Usunięcie elementu znajdującego się pod danym indeksem tablicy to przesunięcie o jedno pole w lewo wszystkich elementów o indeksie wyższym.
Zalety tej implementacji: prosta nawigacja wewnątrz listy, korzystanie z gotowej struktury tablicy, szybki dostęp do elementu o konkretnym numerze, większa odporność na błędy. Wady: niska elastyczność, szczególnie dotycząca rozmiaru tablicy, złożoność operacji wstawiania i usuwania.
Implementację tablicową stosuje się tam, gdzie elastyczność nie odgrywa istotnej roli, a wymagana jest szybka i prosta nawigacja.
[edytuj] Wskaźnikowa
W tej implementacji każdy obiekt na liście musi (co nie było konieczne w wersji tablicowej) zawierać dodatkowy element: wskaźnik do innego obiektu tego typu. Wynika to z faktu, że to wskaźniki są podstawą nawigacji w tym typie listy, a dostęp do jej elementów jest możliwy wyłącznie przez wskaźnik.
Dopisanie elementu (dla prostej listy jednostronnej):
- jeśli ma ono nastąpić na końcu listy, to wskaźnik wiążący w obiekcie ostatnim ustawia się na nowy obiekt danego typu;
- jeśli ma ono nastąpić wewnątrz listy, to najpierw tworzy się nowy obiekt danego typu i jego wskaźnik wiążący ustawia się na następnik elementu, za którym ma być wstawiany. Później wskaźnik poprzednika przestawia się na ten nowy obiekt. W tym przypadku bardzo ważna jest kolejność, której zachwianie jest częstą przyczyną błędów. Np. można najpierw przestawić wskaźnik poprzednika na nowy obiekt, co spowoduje bezpowrotną utratę dostępu do dalszych elementów listy, na które już nie będzie pokazywał żaden wskaźnik. Ustawienie wskaźnika nowego elementu na następnik nie będzie możliwe, bo nie będzie znany jego adres.
Usunięcie elementu jest odwrotne do wstawiania: w pewnym miejscu zapisuje się wskaźnik do usuwanego elementu (aby nie "zgubić" jego adresu), następnie wskaźnik wiążący poprzednika przestawia się na następnik, i dopiero w tym momencie zwalnia się pamięć po obiekcie usuwanym (do tego potrzebny jest ten wskaźnik tymczasowy).
Zalety i wady tej implementacji są komplementarne w stosunku do implementacji tablicowej.
Wgłębiając się w szczegóły implementacji listy za pomocą wskaźników można wyróżnić następujące rodzaje list:
- lista jednokierunkowa - w każdym elemencie listy jest przechowywane odniesienie tylko do jednego sąsiada (następnika lub poprzednika).
- lista dwukierunkowa - w każdym elemencie listy jest przechowywane odniesienie zarówno do następnika jak i poprzednika elementu w liście. Taka reprezentacja umożliwia swobodne przemieszczanie się po liście w obie strony.
- lista cykliczna - następnikiem ostatniego elementu jest pierwszy element, a poprzednikiem pierwszego ostatni. Po liście można więc przemieszczać się cyklicznie. Nie ma w takiej liście charakterystycznego ogona (ani głowy), często rozpoznawanego po tym, że jego następnik jest pusty (NULL).
- lista z wartownikiem - lista z wyróżnionym elementem zwanym wartownikiem. Jest to specjalnie oznaczony element niewidoczny dla programisty wykorzystującego listę. Pusta lista zawiera wtedy tylko wartownika. Zastosowanie wartownika znacznie upraszcza implementację operacji na listach.
Powyższe cechy można prawie dowolnie łączyć, co daje możliwość stworzenia wielu różnych implementacji listy, zależnie od potrzeb.
