Listy - operacje i zastosowania
1. Czym jest lista?
Lista to uporządkowana, mutowalna (modyfikowalna) kolekcja elementów, która może przechowywać wartości różnych typów.
Kluczowe cechy listy:
- Uporządkowana – elementy mają określoną kolejność (indeksy).
- Mutowalna – można dodawać, usuwać i modyfikować elementy.
- Dynamiczna – rozmiar listy może się zmieniać.
- Heterogeniczna – może zawierać różne typy danych.
- Indeksowana – dostęp do elementów po indeksie (od 0).
2. Tworzenie list
2.1. Pusta lista
2.2. Lista z elementami
2.3. Lista z powtórzeniami
2.4. List comprehension
3. Dostęp do elementów
3.1. Indeksowanie (od zera)
Złożoność czasowa: O(1)
3.2. Wycinki (slicing)
Składnia: lista[start:stop:step]
Złożoność czasowa: O(k), gdzie k to długość wycinka.
4. Modyfikacja elementów
4.1. Zmiana pojedynczego elementu
Złożoność czasowa: O(1)
4.2. Zmiana wycinka
5. Dodawanie elementów
5.1. append() – dodaj na końcu
Złożoność czasowa: O(1) amortyzowane
5.2. insert() – wstaw na określonej pozycji
Złożoność czasowa: O(n) – wszystkie elementy po indeksie muszą zostać przesunięte.
5.3. extend() – dodaj wiele elementów
Złożoność czasowa: O(k), gdzie k to długość dodawanej listy.
5.4. Operator +
Uwaga: Tworzy nową listę, nie modyfikuje oryginalnych!
6. Usuwanie elementów
6.1. remove() – usuń pierwszą wartość
Złożoność czasowa: O(n)
6.2. pop() – usuń element po indeksie
Złożoność czasowa:
- pop() (ostatni element): O(1)
- pop(i): O(n)
6.3. del – usuń przez indeks lub wycinek
6.4. clear() – usuń wszystkie elementy
7. Wyszukiwanie i sprawdzanie
7.1. in – sprawdź, czy element istnieje
Złożoność czasowa: O(n)
7.2. index() – znajdź indeks pierwszego wystąpienia
Wyjątek: ValueError jeśli element nie istnieje.
Złożoność czasowa: O(n)
7.3. count() – zlicz wystąpienia
Złożoność czasowa: O(n)
8. Sortowanie i odwracanie
8.1. sort() – sortuj na miejscu
Złożoność czasowa: O(n log n)
8.2. sorted() – zwróć posortowaną kopię
8.3. Sortowanie z kluczem
8.4. reverse() – odwróć listę na miejscu
Złożoność czasowa: O(n)
9. Inne operacje
9.1. len() – długość listy
Złożoność czasowa: O(1)
9.2. min(), max(), sum()
Złożoność czasowa: O(n)
9.3. copy() – kopia płytka
Uwaga: Dla zagnieżdżonych list użyj copy.deepcopy().
10. Iterowanie po listach
10.1. Pętla for
10.2. enumerate() – z indeksem
10.3. zip() – iterowanie po dwóch listach
11. List comprehension (zaawansowane)
11.1. Podstawowa składnia
11.2. Z warunkiem
11.3. Zagnieżdżone pętle
11.4. Z funkcją
12. Listy zagnieżdżone (macierze)
12.1. Tworzenie macierzy
12.2. Iterowanie po macierzy
12.3. List comprehension dla macierzy
13. Złożoność czasowa operacji na listach
| Operacja | Złożoność | Opis |
|---|---|---|
lista[i] |
O(1) | Dostęp po indeksie |
lista.append(x) |
O(1)* | Dodanie na końcu (amortyzowane) |
lista.insert(i, x) |
O(n) | Wstawienie na pozycji i |
lista.remove(x) |
O(n) | Usunięcie pierwszego wystąpienia |
lista.pop() |
O(1) | Usunięcie ostatniego elementu |
lista.pop(i) |
O(n) | Usunięcie elementu na pozycji i |
x in lista |
O(n) | Sprawdzenie, czy element istnieje |
lista.sort() |
O(n log n) | Sortowanie |
lista.reverse() |
O(n) | Odwrócenie listy |
len(lista) |
O(1) | Długość listy |
14. Praktyczne zastosowania
14.1. Stos (Stack) – LIFO
14.2. Kolejka (Queue) – FIFO
Uwaga: deque jest znacznie szybsze dla kolejek niż zwykła lista.
14.3. Historia poleceń (undo/redo)
15. Najczęstsze błędy
Błąd 1: Modyfikacja listy podczas iteracji
Źle:
Dobrze:
Błąd 2: Płytka vs głęboka kopia
Błąd 3: Indeks poza zakresem
16. Podsumowanie
Listy to najbardziej uniwersalna struktura danych w Pythonie:
- Dynamiczna, mutowalna kolekcja elementów
- Doskonała do przechowywania sekwencji danych
- Szybki dostęp po indeksie: O(1)
- List comprehension pozwala na zwięzły kod
- Idealna do implementacji stosu
Kiedy używać listy?
- Potrzebujesz zachować kolejność elementów
- Musisz często dodawać elementy na końcu
- Potrzebujesz dostępu po indeksie
- Elementy mogą się powtarzać
Co dalej warto poznać:
- Tuple – niezmienne listy
- Deque – szybsze kolejki
- Słowniki – szybkie wyszukiwanie
- Zbiory – unikalne elementy