# Λίστες

> Δημιουργία, δείκτες, append, insert, pop, διάσχιση και λίστες μέσα σε λίστες.

Προγραμματισμός Υπολογιστών, Γ΄ ΕΠΑΛ. https://www.akademio.gr/el/epal-c/programming/lists

## Τι θα μάθεις

- Να δημιουργείς λίστες, να βρίσκεις και να αλλάζεις στοιχεία τους με δείκτη, και να χρησιμοποιείς τα in, not in, len, + και list.
- Να προσθέτεις και να αφαιρείς στοιχεία με append, insert και pop, και να προβλέπεις τη λίστα μετά από κάθε κλήση.
- Να διασχίζεις μια λίστα με for, ανά στοιχείο ή ανά δείκτη, για άθροισμα, μέσο όρο, μέγιστο και διαχωρισμό.
- Να ξεχωρίζεις το αντίγραφο L[:] από το δεύτερο όνομα a = L, και να χρησιμοποιείς λίστες μέσα σε λίστες.

## Τι είναι μια λίστα

Η **λίστα** είναι μια διατεταγμένη ακολουθία αντικειμένων, όχι απαραίτητα του ίδιου τύπου, και η βασική δομή δεδομένων της Python. Γράφεται μέσα σε αγκύλες, με τα στοιχεία χωρισμένα με κόμμα. Η εντολή `L = [3, 5, 8, 13, 21, 34]` δημιουργεί τη μεταβλητή `L`, που αναφέρεται σε αυτή τη λίστα:

| Στοιχείο | $3$ | $5$ | $8$ | $13$ | $21$ | $34$ |
| -------- | --- | --- | --- | ---- | ---- | ---- |
| Δείκτης  | $0$ | $1$ | $2$ | $3$  | $4$  | $5$  |

Η προσπέλαση γίνεται όπως στις συμβολοσειρές: με το όνομα της λίστας και τον δείκτη μέσα σε αγκύλες. Το 1ο στοιχείο είναι το `L[0]`, ίσο με $3$, και το τελευταίο το `L[5]`, ή `L[-1]`, ίσο με $34$. Η `[]` είναι η **κενή λίστα**.

Μια λίστα μπορεί να έχει στοιχεία διαφορετικού τύπου: η `mix = [6, 3.14159, True, "Guido van Rossum"]` έχει έναν ακέραιο, έναν πραγματικό, μια λογική τιμή και μια συμβολοσειρά, και `len(mix)` ίσο με $4$.

> **Στον υπολογιστή σου, με Python 3**
>
> Το βιβλίο και οι εξετάσεις γράφουν σε Python 2.7. Στην Python 3 το `print L` γράφεται `print(L)` και το `print a, b` γράφεται `print(a, b)`. Αριθμό διαβάζεις με `int(input())`. Ο `/` δίνει πάντα δεκαδικό· το ακέραιο πηλίκο το δίνει ο `//`. Η `range(4)` δεν είναι λίστα, αλλά η `for` την περνά ίδια· τη λίστα τη φτιάχνει το `list(range(4))`.

Σε αντίθεση με τη συμβολοσειρά, η λίστα είναι **δυναμική** και **μεταβαλλόμενη** (mutable): δεν έχει σταθερό μέγεθος, μεγαλώνει και μικραίνει όσο τρέχει το πρόγραμμα, και κάθε στοιχείο της αλλάζει. Το `L[0] = 2` κάνει τη λίστα `[2, 5, 8, 13, 21, 34]`.

## Τελεστές και συναρτήσεις

Λίστες και συμβολοσειρές είναι και οι δύο **ακολουθίες** (sequences), οπότε έχουν τους ίδιους τελεστές. Με `fruits = ["apple", "orange"]`, `fib = [3, 5, 8, 13, 21]` και `powers = [2, 4, 8, 16]`:

| Γράφεις                | Αποτέλεσμα                       | Τι κάνει                                             |
| ---------------------- | -------------------------------- | ---------------------------------------------------- |
| `len(fruits)`          | `2`                              | το πλήθος των στοιχείων                              |
| `"apple" in fruits`    | `True`                           | ελέγχει αν το στοιχείο υπάρχει στη λίστα             |
| `"kiwi" not in fruits` | `True`                           | ελέγχει αν το στοιχείο **δεν** υπάρχει               |
| `fib + powers`         | `[3, 5, 8, 13, 21, 2, 4, 8, 16]` | συνενώνει δύο λίστες σε μια νέα                      |
| `list("abc")`          | `['a', 'b', 'c']`                | φτιάχνει λίστα με τους χαρακτήρες μιας συμβολοσειράς |
| `fib[1:3]`             | `[5, 8]`                         | φέτα, όπως στις συμβολοσειρές                        |

## Προσθήκη και αφαίρεση στοιχείων

Ένα στοιχείο μπαίνει στο τέλος με `L = L + [x]` και στην αρχή με `L = [x] + L`. Αυτές οι εντολές όμως δεν αλλάζουν την υπάρχουσα λίστα: φτιάχνουν μια **νέα** κάθε φορά, και αυτό έχει υπολογιστικό κόστος. Για το τέλος, το βιβλίο προτιμά το `L += [x]`, που προσθέτει στην ίδια λίστα.

Το βιβλίο χρησιμοποιεί τρεις **μεθόδους** των λιστών. Μια μέθοδος γράφεται με τελεία μετά το όνομα της λίστας, και αλλάζει την ίδια τη λίστα:

| Μέθοδος          | Τι κάνει                                                                                         |
| ---------------- | ------------------------------------------------------------------------------------------------ |
| `L.append(x)`    | προσθέτει το `x` στο τέλος της `L`                                                               |
| `L.insert(i, x)` | προσθέτει το `x` στη θέση `i`· τα στοιχεία από τη θέση `i` και μετά μετακινούνται μία θέση δεξιά |
| `L.pop(i)`       | αφαιρεί το στοιχείο της θέσης `i` και το **επιστρέφει**· χωρίς δείκτη, αφαιρεί το τελευταίο      |

Στα προγράμματα που τρέχουν εδώ, το `print(...)` έχει πάντα ένα όρισμα: έτσι δουλεύει ίδια και στις δύο εκδόσεις.

*Διαδραστικό στη σελίδα: append, insert, pop*

Μια `pop` σε κενή λίστα, ή με δείκτη που δεν υπάρχει, σταματά το πρόγραμμα με `IndexError`.

> **Πρόσεχε**
>
> **Οι μέθοδοι `append` και `insert` δεν επιστρέφουν τη λίστα.** Αλλάζουν τη λίστα επιτόπου και επιστρέφουν `None`. Το `L = L.append(4)` προσθέτει πρώτα το $4$ και μετά δίνει στην `L` την τιμή `None`: η λίστα χάθηκε. Γράφεις σκέτο `L.append(4)`. Η `pop` είναι η μόνη από τις τρεις που επιστρέφει κάτι, το στοιχείο που έβγαλε.

## Διάσχιση λίστας

Τα στοιχεία μιας λίστας τα επεξεργάζεσαι ένα-ένα με τη `for`, με δύο τρόπους:

```python
L = [6, 28, 496, 8128]
for item in L:            # η item παίρνει κάθε στοιχείο
    print item
for i in range(len(L)):   # η i παίρνει κάθε δείκτη, 0 ως 3
    print L[i]
```

Και οι δύο εμφανίζουν τα ίδια. Ο δεύτερος χρειάζεται όταν σε ενδιαφέρει η **θέση** ή όταν θέλεις να **αλλάξεις** στοιχεία. Η `range(4)` επιστρέφει τη λίστα `[0, 1, 2, 3]`, και η `for` περνά απλώς από αυτή τη λίστα δεικτών: το ίδιο θα έκανε το `for i in [0, 1, 2, 3]:`.

Ο **μέσος όρος** θέλει αθροιστή και διαίρεση με τη `len`. Το **μέγιστο** ξεκινά από το πρώτο στοιχείο, `L[0]`, και συγκρίνεται με κάθε στοιχείο:

*Διαδραστικό στη σελίδα: Μέσος όρος και μέγιστο λίστας*

Ο αθροιστής ξεκινά από `0.0`, όπως στο βιβλίο. Ανάμεσα σε δύο ακέραιους, ο `/` της 2.7 κόβει τα δεκαδικά: με `total = 0` το `68 / 5` θα έδινε `13`. Με `0.0` το άθροισμα είναι πραγματικός, και η διαίρεση δίνει `13.6`. Το βιβλίο ονομάζει τον αθροιστή `sum`· εδώ λέγεται `total`, γιατί το `sum` είναι όνομα ενσωματωμένης συνάρτησης.

> **Πρόσεχε**
>
> **Η `for item in L` δεν αλλάζει τα στοιχεία της λίστας.** Στο `for x in L: x = x * 2` διπλασιάζεται η μεταβλητή `x`, όχι το στοιχείο της `L`. Για να αλλάξεις τη λίστα χρειάζεσαι τον δείκτη: `for i in range(len(L)): L[i] = L[i] * 2`.

Μια τυπική επεξεργασία είναι ο **διαχωρισμός** μιας λίστας σε δύο, με βάση ένα κριτήριο. Η αρχική λίστα μένει ανέπαφη· οι νέες ξεκινούν κενές και γεμίζουν με `append`:

```python
numbers = [4, -2, 7, -9, 1]
positives = []
negatives = []
for number in numbers:
    if number > 0:
        positives.append(number)
    else:
        negatives.append(number)
print positives, negatives    # [4, 7, 1] [-2, -9]
```

## Αντίγραφο ή δεύτερο όνομα

Η εντολή `a = fib` **δεν** αντιγράφει τη λίστα. Δίνει ένα δεύτερο όνομα στην **ίδια** λίστα, και ό,τι αλλάζει μέσω της `a` αλλάζει και στη `fib`. Ένα πραγματικό αντίγραφο φτιάχνεται με τον τελεστή διαμέρισης, `fib = fibonacci[:]`.

*Διαδραστικό στη σελίδα: Αντίγραφο και δεύτερο όνομα*

> **Κλειδί**
>
> **Η εκχώρηση δίνει όνομα σε μια λίστα· δεν φτιάχνει νέα.** Μετά το `a = fib` υπάρχει μία λίστα με δύο ονόματα, και μια `pop` από οποιοδήποτε όνομα τη μικραίνει και για τα δύο. Αντίγραφο φτιάχνει μόνο το `fib[:]`.
>
> Το ίδιο ισχύει όταν δίνεις μια λίστα σε συνάρτηση: η παράμετρος είναι άλλο ένα όνομα της ίδιας λίστας, και ό,τι κάνει η συνάρτηση με `append` ή `pop` φαίνεται και έξω. Στη συμβολοσειρά το ζήτημα δεν τίθεται, γιατί δεν αλλάζει ποτέ.

## Λίστες μέσα σε λίστες

Ένα στοιχείο λίστας μπορεί να είναι κι αυτό λίστα. Με `x = [21, 23, 25, 27]`, `y = [5, 6, 7, 8]` και `a = [x, y]`, η `a` έχει **δύο** στοιχεία, τις δύο λίστες. Το `a[1]` είναι η `y`, και το `a[1][2]` είναι το 3ο στοιχείο της `y`, το $7$. Έτσι μια λίστα λιστών παίζει τον ρόλο ενός πίνακα με γραμμές και στήλες: το `a[i][j]` είναι το στοιχείο της γραμμής `i` και της στήλης `j`.

## Παραδείγματα

### Παράδειγμα 1: Να γράψετε πρόγραμμα σε Python για μια ταμειακή μηχανή. Το πρόγραμμα διαβάζει το κόστος των αγορών και το ποσό που έδωσε ο πελάτης, σε ακέραια ευρώ, και εμφανίζει το ελάχιστο πλήθος κερμάτων και χαρτονομισμάτων για τα ρέστα. Υπάρχουν κομμάτια των 100, 50, 20, 10, 5, 2 και 1 ευρώ.

1. **Η ιδέα:** δίνεις όσο περισσότερα γίνεται από το μεγαλύτερο κομμάτι, και ό,τι μένει το καλύπτεις με τα μικρότερα. Γι' αυτό τα κομμάτια μπαίνουν σε λίστα με **φθίνουσα** σειρά, `values = [100, 50, 20, 10, 5, 2, 1]`, και η `for` τα περνά με αυτή τη σειρά.
2. **Για κάθε κομμάτι:** το `change / value`, ανάμεσα σε ακέραιους, δίνει το ακέραιο πηλίκο, δηλαδή πόσα κομμάτια αυτής της αξίας χωρούν στα ρέστα. Το `change % value` είναι ό,τι περισσεύει για τα επόμενα. Τα ποσά είναι αριθμοί, οπότε διαβάζονται με `input`.
3. ```python
   values = [100, 50, 20, 10, 5, 2, 1]
   cost = input("Δώσε το κόστος των αγορών: ")
   payment = input("Δώσε το ποσό της πληρωμής: ")
   change = payment - cost
   counter = 0
   for value in values:
       counter = counter + change / value
       change = change % value
   print counter
   ```
4. Στον runner, που είναι Python 3, ο `/` γράφεται `//` και το `input` γράφεται `int(input(...))`. Έτσι η έξοδος είναι ίδια και στις δύο εκδόσεις.
5. *Διαδραστικό στη σελίδα: Ρέστα με τα λιγότερα κομμάτια*
6. **Έλεγχος:** $73 = 50 + 20 + 2 + 1$, δηλαδή $4$ κομμάτια. Τα $100$, $10$ και $5$ δεν χρησιμοποιούνται, γιατί όταν έρχεται η σειρά τους τα ρέστα που μένουν είναι μικρότερα από αυτά.

### Παράδειγμα 2: Να γράψετε συνάρτηση merge(A, B) η οποία δέχεται δύο λίστες ταξινομημένες σε αύξουσα σειρά και επιστρέφει μια νέα λίστα με όλα τα στοιχεία τους, επίσης σε αύξουσα σειρά, χωρίς να την ταξινομήσει από την αρχή.

1. **Η ιδέα της συγχώνευσης:** αφού και οι δύο λίστες είναι ταξινομημένες, το μικρότερο στοιχείο απ' όλα είναι το μικρότερο από τα `A[0]` και `B[0]`. Το βγάζεις με `pop(0)` από τη λίστα του και το βάζεις με `append` στο τέλος της νέας λίστας `L`.
2. **Πότε σταματάς:** η επανάληψη συνεχίζει όσο **και οι δύο** λίστες έχουν στοιχεία, `while A != [] and B != []`. Κάποια στιγμή η μία αδειάζει, και η άλλη έχει ακόμα στοιχεία, όλα μεγαλύτερα από όσα πέρασαν στην `L`.
3. **Τα υπόλοιπα:** αντί για `if` που ελέγχει ποια άδειασε, γράφεις `return L + A + B`. Η άδεια λίστα δεν προσθέτει τίποτα, οπότε το αποτέλεσμα είναι σωστό σε κάθε περίπτωση.
4. *Διαδραστικό στη σελίδα: Συγχώνευση ταξινομημένων λιστών*
5. **Προσοχή:** η `merge` αδειάζει, εν μέρει ή ολόκληρες, τις λίστες που της δίνεις, γιατί οι `A` και `B` είναι ονόματα των ίδιων λιστών. Αν τις χρειάζεσαι μετά, δίνεις αντίγραφα: `merge(X[:], Y[:])`.

Για το τρίτο παράδειγμα δίνεται το τμήμα:

```python
L = []
for x in [3, 7, 1]:
    L.insert(0, x)
print L
L.append(L[0] + L[-1])
print L
print L.pop(1), L
print len(L), 7 in L
```

### Παράδειγμα 3: Τι θα εμφανίσει το παραπάνω τμήμα προγράμματος;

1. **Ο βρόχος:** κάθε `insert(0, x)` βάζει το νέο στοιχείο **μπροστά** από τα προηγούμενα. Η `L` γίνεται `[3]`, μετά `[7, 3]`, μετά `[1, 7, 3]`. Η πρώτη γραμμή είναι `[1, 7, 3]`.
2. **Η append:** `L[0] + L[-1]` είναι $1 + 3 = 4$, και μπαίνει στο τέλος: `[1, 7, 3, 4]`.
3. **Η pop(1):** βγάζει το στοιχείο της θέσης $1$, το $7$, και το επιστρέφει. Η `print` υπολογίζει τις τιμές της από αριστερά προς τα δεξιά, και το κόμμα βάζει ένα κενό ανάμεσα: `7 [1, 3, 4]`.
4. **Το τέλος:** η `L` έχει πια $3$ στοιχεία, και το $7$ δεν είναι ανάμεσά τους: `3 False`.
5. *Διαδραστικό στη σελίδα: insert, append, pop*

> **Θυμήσου**
>
> - Η λίστα είναι **μεταβαλλόμενη**: το `L[i] = x` επιτρέπεται, ενώ στη συμβολοσειρά όχι.
> - `in`, `not in`, `len`, `+` και φέτες δουλεύουν όπως στις συμβολοσειρές· η `list("abc")` φτιάχνει λίστα χαρακτήρων.
> - `append(x)` στο τέλος, `insert(i, x)` στη θέση `i`, `pop(i)` αφαιρεί και επιστρέφει· χωρίς δείκτη, το τελευταίο.
> - Το `L = L + [x]` φτιάχνει νέα λίστα· το `L.append(x)` αλλάζει την ίδια.
> - Το `a = L` δίνει δεύτερο όνομα· αντίγραφο είναι το `L[:]`.
> - Το `a[i][j]` είναι το στοιχείο `j` της λίστας `a[i]`.

## Ερωτήσεις

1. Με L = [3, 5, 8, 13, 21, 34], τι δίνει το L[len(L) - 1];
   - 34
   - 21
   - σφάλμα IndexError
   - 6
2. Με L = [10, 20, 30], πώς γίνεται η L μετά την L.insert(1, 99);
   - [10, 99, 20, 30]
   - [99, 10, 20, 30]
   - [10, 99, 30]
   - [10, 20, 30, 99]
3. Σωστό ή λάθος; «Οι λίστες, όπως και οι συμβολοσειρές, είναι μη μεταβαλλόμενες δομές της Python.»
   - Λάθος: η λίστα αλλάζει, η συμβολοσειρά όχι
   - Σωστό: καμία από τις δύο δεν αλλάζει
   - Λάθος: μόνο η συμβολοσειρά αλλάζει
   - Λάθος: αλλάζουν και οι δύο
4. Τι εμφανίζει το τμήμα: L = [5, 8, 13], x = L.pop(), print x, L;
   - 13 [5, 8]
   - 5 [8, 13]
   - 13 [5, 8, 13]
   - None [5, 8]
5. Τι εμφανίζει το τμήμα: a = [1, 2, 3], b = a, b.append(4), print a;
   - [1, 2, 3, 4]
   - [1, 2, 3]
   - [4]
   - None
6. Ποια εντολή κάνει τη b πραγματικό αντίγραφο της λίστας a, ώστε οι αλλαγές στη b να μην επηρεάζουν την a;
   - b = a[:]
   - b = a
   - b = [a]
   - b = a[0]
7. Τι εμφανίζει το τμήμα: L = [4, 7, 2], L = L.append(5), print L;
   - None
   - [4, 7, 2, 5]
   - [5]
   - σφάλμα TypeError
8. Με a = [[1, 2, 3], [4, 5, 6]], τι δίνει το a[1][0];
   - 4
   - 2
   - [4, 5, 6]
   - 1
9. Τι εμφανίζει το τμήμα: L = [4, 6, 9], total = 0, for x in L: total = total + x, και μετά print total / len(L);
   - 6
   - 6.33333333333
   - 19
   - 6.0
10. Σωστό ή λάθος; «Μετά τον βρόχο for x in L: x = x * 2, κάθε στοιχείο της L έχει διπλασιαστεί.»
   - Λάθος: αλλάζει μόνο η x
   - Σωστό: η x είναι το ίδιο το στοιχείο
   - Λάθος: ο βρόχος σταματά με σφάλμα
   - Σωστό, αλλά μόνο για ακέραιους

## Ασκήσεις

1. Με L = [3, 5, 8, 13, 21, 34], ποιο στοιχείο είναι το L[2] και ποιο το L[-2];
2. Η L είναι [5, 8, 13, 21, 34]. Εκτελούνται με τη σειρά οι L.pop(1), L.append(55) και L.insert(0, 2). Πώς είναι η L στο τέλος;
3. Τι εμφανίζει το τμήμα: L = [], και μετά for c in "ABC": L = [c] + L, και στο τέλος print L;
4. Τι εμφανίζει το τμήμα: a = [1, 2, 3], b = a, c = a[:], b.append(4), c.pop(0), και στο τέλος print a, c;
5. Η συνάρτηση merge(A, B) του λυμένου παραδείγματος 2 καλείται με X = [1, 4, 9] και Y = [2, 3], ως C = merge(X, Y).
   α) Πόσες φορές εκτελείται το μπλοκ της while;
   β) Τι περιέχει η C;
   γ) Τι περιέχουν οι X και Y μετά την κλήση;
6. Στο πρόγραμμα των ρέστων του λυμένου παραδείγματος 1, ο counter αυξάνεται κατά change / value και η change γίνεται change % value, για κάθε value της λίστας values.
   α) Αν κάποιος γράψει τη λίστα σε αύξουσα σειρά, values = [1, 2, 5, 10, 20, 50, 100], τι εμφανίζει το πρόγραμμα για ρέστα 73 €;
   β) Με τη σωστή, φθίνουσα λίστα, ποιο είναι το μεγαλύτερο πλήθος κομματιών που μπορεί να εμφανίσει για ρέστα από 1 ως 99 €;

---

Οι απαντήσεις, τα διαδραστικά και τα παιχνίδια είναι στη σελίδα της ενότητας: https://www.akademio.gr/el/epal-c/programming/lists
