Lista

WPROWADZENIE

Lista to ADT, który reprezentuje skończoną liczbę uporządkowanych elementów (wartości) mogących się powtarzać. Jeżeli liczba uporządkowanych elementów może być potencjalnie nieskończona, to używa się pojęcia strumienia. Lista to podstawowy przykład kontenera do przechowywania elementów. Typowe operacje dla ADT List:

• konstruktor tworzący pustą listę,
• testowanie, czy lista nie jest pusta [len(L) == 0, empty()],
• dołączanie elementu do początku listy [L.insert(0, item)],
• dołączanie elementu na koniec listy [L.append(item)],
• dołączanie elementu przed element na pozycji i [L.insert(i, item)],
• dostęp do głowy (head), czyli pierwszego (lewego skrajnego) elementu (L[0]),
• dostęp do ogona (tail), czyli ostatniego (prawego skrajnego) elementu (L[-1]),
• dostęp do elementu o danym indeksie i (numeracja od 0 lub 1, L[i], find(i)),
• pobieranie wycinka listy (L[i:j]),
• sortowanie listy [sort()],
• łączenie dwóch list posortowanych w jedną listę posortowaną [merge()],
• usunięcie elementu o danym indeksie i (del L[i]),
• czyszczenie listy [clear()].

ADT List jest typowo implementowany jako lista powiązana (liniowa lub cykliczna) lub tablica, zwykle o zmiennej długości. W Pythonie ADT List jest realizowany przez wbudowany typ 'list', który wykorzystuje tablicę dynamiczną (dynamic array). [The growth pattern is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...]

https://stackoverflow.com/questions/3917574/how-is-pythons-list-implemented

http://www.laurentluce.com/posts/python-list-implementation/

https://en.wikipedia.org/wiki/Dynamic_array