Lista

WPROWADZENIE

Lista to ADT, który reprezentuje skończoną liczbę uporządkowanych elementów (wartości) mogących się powtarzać. Elementy są uporządkowane (każdy ma swoją ustaloną pozycję), ale nie muszą być posortowane, nie jest wymagane istnienie operacji porównywania elementów. 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 (multiple of 4): 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

Geometryczne rozszerzanie tablicy dynamicznej.
+---+
| 2 | size=1, capacity=2
+---+
+---+---+
| 2 | 7 | size=2, capacity=2
+---+---+
+---+---+---+---+
| 2 | 7 | 1 |   | size=3, capacity=4
+---+---+---+---+
+---+---+---+---+
| 2 | 7 | 1 | 3 | size=4, capacity=4
+---+---+---+---+
+---+---+---+---+---+---+---+---+
| 2 | 7 | 1 | 3 | 8 |   |   |   | size=5, capacity=8
+---+---+---+---+---+---+---+---+
Usuwamy 8, 3.
+---+---+---+---+---+---+---+---+
| 2 | 7 | 1 |   |   |   |   |   | size=3, capacity=8
+---+---+---+---+---+---+---+---+
Usuwamy 1, zmniejszenie tablicy (histereza).
+---+---+---+---+
| 2 | 7 |   |   | size=2, capacity=4
+---+---+---+---+

https://chalmersgu-data-structure-courses.github.io/OpenDSA/Published/ChalmersGU-DSABook/html/ListArrayDynamic.html

Zbadajmy liczbę kopiowań elementów podczas powiększania tablicy o czynnik 2. Zakładamy, że elementy są kolejno wstawiane do tablicy.
resize(2), kopiowany 1 element
resize(4), kopiowane 2 elementy
resize(8), kopiowane 4 elementy
resize(16), kopiowane 8 elementów
resize(32), kopiowane 16 elementów
resize(64), kopiowane 32 elementy
resize(128), kopiowane 64 elementy
resize(2^k), kopiowane 2^{k-1} elementów

Załóżmy najbardziej niekorzystny przypadek, że liczba elementów wstawionych do tablicy wynosi n = 2^k + 1. Tablica rozszerzy się do rozmiaru 2^{k+1}. Łączna liczba kopiowań elementów wynosi
1 + 2 + 4 + ... + 2^k = (1 - 2^{k+1}) / (1 - 2) = 2^{k+1} -1 = 2 * 2^k -1 = 2 (n-1) -1 = 2n -3.
Pokazaliśmy, że stosując strategię podwajania rozmiaru tablicy, wstawianie do tablicy n elementów wymaga mniej niż 2n kopiowań elementów. Inaczej mówiąc, wstawienie jednego elementu do tablicy kosztuje co najwyżej dwa kopiowania elementów.

Osobnym zagadnieniem jest zmniejszanie rozmiaru tablicy przy zmniejszającej się liczbie elementów. Załóżmy, że aktualny rozmiar tablicy wynosi 2^k. Dobrą strategią jest zmniejszanie rozmiaru do 2^k / 2, jeżeli liczba elementów zmaleje do 2^k / 4 lub 2^k / 3, a nie do 2^k / 2. Unikamy wtedy częstego powiększania i zmniejszania rozmiaru tablicy, kiedy liczba elementów oscyluje koło 2^k / 2.