Lista (komputer)

W informatyce , A lista jest struktura danych umożliwiając danych razem grupę, tak, aby móc do niego dostępu swobodnego (w przeciwieństwie do kolejki i stosów , które są dostępne w FIFO i LIFO trybie odpowiednio ).

Lista jest podstawą bardziej złożonych struktur danych, takich jak stos , kolejka , drzewa itp. Znaczenie listy jako struktury danych jest takie, że jest ona podstawą języka programowania Lisp (angielski list processing ).

Prymitywy

Oto prymitywy powszechnie używane do manipulowania listami; nie ma standaryzacji dla prymitywów manipulacji listami, więc ich nazwy są podawane nieformalnie.

Podstawowe prymitywy:

• „Wstaw”: dodaje pozycję do listy. Odpowiedni termin w języku angielskim: „  Add  ”;
• „Usuń”: usuwa element z listy. Odpowiedni termin w języku angielskim: „  Usuń  ”;
• „Czy lista jest pusta?” „: Zwraca„ true ”, jeśli lista jest pusta,„ false ”w przeciwnym razie. Odpowiedni termin w języku angielskim: „  IsNull  ”;
• „Liczba elementów na liście”: zwraca liczbę elementów na liście. Odpowiedni termin w języku angielskim: „  Length  ”.

Często spotykane prymitywy pomocnicze:

• „First”: zwraca pierwszy element z listy. Odpowiedni termin w języku angielskim: „  First  ”;
• „Last”: zwraca ostatni element na liście. Odpowiedni termin w języku angielskim: „  Last  ”;
• „Dalej”: zwraca następny element na liście. Odpowiedni termin w języku angielskim: „  Next  ”;
• „Poprzedni”: zwraca element poprzedzający na liście. Odpowiedni termin w języku angielskim: „  Poprzedni  ”;
• „Znajdź”: wyszukuje, czy określony element znajduje się na liście i zwraca jego pozycję. Odpowiedni termin w języku angielskim: „  Find  ”.

Typy list

Lista to kontener elementów, w którym każdy element zawiera dane, a także inne informacje umożliwiające pobranie danych w ramach listy. Charakter (rodzaje) tych informacji charakteryzuje inny typ listy.

Ogólnie możemy wyróżnić dwa rodzaje list:

• stoły ;
• połączone listy.

Tablica

Dostęp do elementu odbywa się za pomocą indeksu, który reprezentuje położenie elementu w strukturze.

Dane w tabeli są ciągłe w pamięci. Powoduje to stały rozmiar tablicy, tj. Niezmienność; jednak niektóre języki wysokiego poziomu udostępniają tablice, które zmieniają swój rozmiar w zależności od ich zastosowania: nazywa się to tablicą o rozmiarze dynamicznym. Jednak ich implementacja opiera się na zasadzie list połączonych (patrz poniżej).

Tablice mogą również mieć wiele wymiarów, reprezentowanych przez sekwencję indeksów dolnych. W tym przypadku, jeśli n jest wymiarem macierzy (gdzie n jest liczbą całkowitą różną od zera naturalne), wymiar elementów tablicy 1 (z 1 ul  indeksem sekwencji) każdego wskazującego z innym (pod) Tablica wymiar n 1 .

Połączona lista

W przeciwieństwie do tablicy, rozmiar listy połączonej nie ma ograniczeń innych niż rozmiar dostępnej pamięci. To ograniczenie jest przezwyciężane przez fakt, że każdy element może wskazywać, zgodnie z typem połączonej listy, jeden lub więcej elementów listy przy użyciu definicji rekurencyjnej. W związku z tym, aby zwiększyć rozmiar listy połączonej, wystarczy utworzyć nowy element i skierować pewne elementy, które już znajdują się na liście, do nowego elementu.

Istnieją dwa główne typy list połączonych:

• po prostu połączone listy: każdy element ma wskaźnik do następnego (lub następcy) elementu na liście. Trasa przebiega w jednym kierunku;
• listy podwójnie połączone: każdy element ma dwa wskaźniki, odpowiednio do następnego elementu (lub następcy) i do poprzedniego elementu (lub poprzednika). Kurs może wtedy odbywać się w dwóch przeciwstawnych kierunkach: od następcy do następcy lub od poprzednika do poprzednika.

Do tego możemy dodać właściwość: cykl. Tym razem połączona lista tworzy pętlę. Gdy tylko dojdziesz do „końca” listy i zechcesz kontynuować, znajdziesz się na „pierwszym” elemencie listy. W tym przypadku pojęcie początku lub końca łańcucha nie ma już żadnego powodu do istnienia.