Lista (abstrakcyjny typ danych) - List (abstract data type)

W informatyce , A lista lub sekwencja jest abstrakcyjny typ danych , który reprezentuje skończoną liczbę zamówionych wartości , w których ta sama wartość może wystąpić więcej niż raz. Przykładem listy jest komputerowa reprezentacja matematycznego pojęcia krotki lub skończonej sekwencji ; (potencjalnie) nieskończonym odpowiednikiem listy jest strumień . Listy są podstawowym przykładem kontenerów , ponieważ zawierają inne wartości. Jeśli ta sama wartość występuje wiele razy, każde wystąpienie jest traktowane jako odrębny element.

Pojedynczo połączona struktura listy, implementująca listę z trzema elementami całkowitymi.

Nazwa lista służy również do kilku konkretnych struktur danych , które mogą być wykorzystane do realizacji abstrakcyjnych list, zwłaszcza związanych list i tablic . W niektórych kontekstach, takich jak programowanie w Lispie , termin lista może odnosić się konkretnie do połączonej listy, a nie tablicy. W programowaniu opartym na klasach listy są zwykle dostarczane jako instancje podklas ogólnej klasy „listy” i przechodzą przez oddzielne iteratory .

Wiele języków programowania zapewnia obsługę typów danych list oraz specjalną składnię i semantykę list i operacji na listach. Listę można często utworzyć, wpisując elementy w kolejności, oddzielone przecinkami , średnikami i/lub spacjami , w parze ograniczników, takich jak nawiasy „()”, nawiasy „[]”, nawiasy klamrowe „{}” lub nawiasy kątowe '<>'. Niektóre języki mogą zezwalać na indeksowanie lub wycinanie typów list jak typy tablicowe , w którym to przypadku typ danych jest dokładniej określany jako tablica.

W teorii typów i programowaniu funkcjonalnym listy abstrakcyjne są zwykle definiowane indukcyjnie przez dwie operacje: nil, która daje pustą listę, oraz cons , która dodaje element na początku listy.

Operacje

Implementacja struktury danych listy może zapewnić niektóre z następujących operacji :

konstruktor do tworzenia pustej listy;
operacja sprawdzania, czy lista jest pusta;
operacja dodawania encji do listy
operacja dołączania encji do listy
operacja określania pierwszego składnika (lub „nagłówka”) listy
operacja odwoływania się do listy składającej się ze wszystkich składników listy z wyjątkiem pierwszego (jest to nazywane „ogonem” listy).
operacja dostępu do elementu pod danym indeksem.

Realizacje

Listy są zazwyczaj implementowane jako listy połączone (pojedynczo lub podwójnie połączone) lub jako tablice , zwykle tablice o zmiennej długości lub tablice dynamiczne .

Standardowy sposób implementacji list, wywodzący się z języka programowania Lisp , polega na tym, aby każdy element listy zawierał zarówno swoją wartość, jak i wskaźnik wskazujący położenie kolejnego elementu na liście. Daje to połączoną listę lub drzewo , w zależności od tego, czy lista zawiera zagnieżdżone podlisty. Niektóre starsze implementacje Lisp (takie jak implementacja Lisp w Symbolics 3600) również obsługiwały "listy skompresowane" (używające kodowania CDR ), które miały specjalną wewnętrzną reprezentację (niewidoczną dla użytkownika). Listami można manipulować za pomocą iteracji lub rekurencji . Ten pierwszy jest często preferowany w imperatywnych językach programowania , podczas gdy drugi jest normą w językach funkcjonalnych .

Listy mogą być zaimplementowane jako samorównoważące się binarne drzewa wyszukiwania zawierające pary indeks-wartość, zapewniające dostęp w równym czasie do dowolnego elementu (np. wszystkich znajdujących się na marginesie i wewnętrznych węzłów przechowujących indeks potomny z prawej strony, używany do kierowania wyszukiwaniem) , biorąc czas logarytmiczny w rozmiarze listy, ale tak długo, jak niewiele się to zmieni, zapewni iluzję losowego dostępu i umożliwi operacje wymiany, prefiksów i dołączania również w czasie logarytmicznym.

Obsługa języka programowania

Niektóre języki nie oferują struktury danych listy , ale oferują użycie tablic asocjacyjnych lub pewnego rodzaju tabeli do emulacji list. Na przykład Lua udostępnia tabele. Chociaż Lua przechowuje listy, które mają wewnętrznie indeksy liczbowe jako tablice, nadal pojawiają się one jako słowniki.

W Lisp listy są podstawowym typem danych i mogą reprezentować zarówno kod programu, jak i dane. W większości dialektów listę pierwszych trzech liczb pierwszych można zapisać jako (list 2 3 5). W kilku dialektach Lispu, w tym Scheme , lista jest zbiorem par, składającym się z wartości i wskaźnika do następnej pary (lub wartości null), tworząc pojedynczo połączoną listę.

Aplikacje

Jak sama nazwa wskazuje, listy mogą służyć do przechowywania listy elementów. Jednak w przeciwieństwie do tradycyjnych tablic , listy mogą się rozszerzać i zmniejszać oraz są przechowywane dynamicznie w pamięci.

W informatyce listy są łatwiejsze do zaimplementowania niż zestawy. Skończony zbiór w sensie matematycznym może być zrealizowany jako lista z dodatkowymi ograniczeniami; oznacza to, że zduplikowane elementy są niedozwolone, a kolejność nie ma znaczenia. Sortowanie listy przyspiesza ustalenie, czy dana pozycja jest już w zestawie, ale aby zapewnić porządek, potrzeba więcej czasu na dodanie nowego wpisu do listy. Jednak w wydajnych implementacjach zestawy są implementowane przy użyciu samobalansujących binarnych drzew wyszukiwania lub tabel mieszających , a nie listy.

Listy stanowią również podstawę dla innych abstrakcyjnych typów danych, w tym kolejki , stosu i ich odmian.

Abstrakcyjna definicja

Lista abstrakcyjna typu L z elementami pewnego typu E ( lista monomorficzna ) jest definiowana przez następujące funkcje:

zero: () → L

minusy: E × L → L

pierwszy: L → E

reszta: L → L

z aksjomatami

pierwszy (cons ( e , l )) = e

reszta (przeciw ( e , l )) = l

dla dowolnego elementu e i dowolnej listy l . Jest domniemane, że

minusy ( e , l ) ≠ l

minusy ( e , l ) ≠ e

minusy ( e ₁ , l ₁ ) = minusy ( e ₂ , l ₂ ) jeśli e ₁ = e ₂ i l ₁ = l ₂

Zauważ, że pierwszy (nil()) i reszta (nil()) nie są zdefiniowane.

Te aksjomaty są równoważne aksjomatom abstrakcyjnego typu danych stosu .

W teorii typów powyższa definicja jest prościej traktowana jako typ indukcyjny zdefiniowany w kategoriach konstruktorów: zero i cons . W kategoriach algebraicznych można to przedstawić jako transformację 1 + E × L → L . najpierw i reszta są następnie uzyskiwane przez dopasowanie wzorca w konstruktorze cons i oddzielną obsługę przypadku zerowego .

Lista monada

Typ listy tworzy monadę z następującymi funkcjami (używając E ^* zamiast L do reprezentowania list monomorficznych z elementami typu E ):

{\ Displaystyle {\ tekst {powrót}} \ dwukropek A \ do A ^ {*} = a \ mapsto {\ tekst {przeciw}} \ a \ {\ tekst {nil}}}

{\ Displaystyle {\ tekst {wiązać}} \ dwukropek A ^ {*} \ do (A \ do B ^ {*}) \ do B ^ {*} = l \ mapsto f \ mapsto {\ zacząć {przypadki} { \text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{append}}\,(f\,a)\,({\text{bind} }\,l'\,f)&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}}

gdzie dodatek jest zdefiniowany jako:

{\ Displaystyle {\ tekst {dołączyć}} \ dwukropek A ^ {*} \ do A ^ {*} \ do A ^ {*} = l_ {1} \ mapsto l_ {2} \ mapsto {\ zacząć {przypadki} l_{2}&{\text{if}}\ l_{1}={\text{nil}}\\{\text{cons}}\,a\,({\text{append}}\,l_ {1}'\,l_{2})&{\text{if}}\ l_{1}={\text{cons}}\,a\,l_{1}'\end{cases}}}

Alternatywnie monadę można zdefiniować w kategoriach operacji return , fmap i join , przy czym:

{\ Displaystyle {\ tekst {fmap}} \ dwukropek (A \ do B) \ do (A ^ {*} \ do B ^ {*}) = f \ mapsto l \ mapsto {\ zacząć {przypadki} {\ tekst {nil}}&{\text{if}}\ l={\text{nil}}\\{\text{cons}}\,(f\,a)({\text{fmap}}f\, l')&{\text{if}}\ l={\text{przeciw}}\,a\,l'\end{przypadki}}}

{\ Displaystyle {\ tekst {dołączyć}} \ dwukropek {A ^ {*}} ^ {*} \ do A ^ {*} = l \ mapsto {\ zacząć {przypadki} {\ tekst {nil}} i {\ text{if}}\ l={\text{nil}}\\{\text{append}}\,a\,({\text{połącz}}\,l')&{\text{if}} \ l={\text{przeciw}}\,a\,l'\end{przypadki}}}

Zauważ, że fmap , join , append i bind są dobrze zdefiniowane, ponieważ są stosowane do coraz głębszych argumentów przy każdym wywołaniu rekurencyjnym.

Typ listy to monada addytywna, gdzie zero to monadyczne zero i dołączane jako suma monadyczna.

Listy tworzą monoid w ramach operacji dołączania . Elementem tożsamości monoidu jest pusta lista, nil . W rzeczywistości jest to wolny monoid nad zbiorem elementów listy.

Languages

In other projects