2. Lista

Lista (list) on monikäyttöinen tietorakenne, joka on Python-kielen perustietorakenne. Lista soveltuu usein ohjelmassa käsiteltävän tiedon tallentamiseen, mutta toisaalta on tilanteita, joissa listan sijasta kannattaa käyttää muita tietorakenteita.

Tutustumme tässä luvussa Pythonin listan toteutukseen ja ominaisuuksiin. Kiinnitämme erityisesti huomiota listan operaatioiden aikavaativuuteen: mitkä listan operaatiot ovat tehokkaita ja milloin listaa kannattaa käyttää.

Lista muistissa

Tietokoneen muisti muodostuu peräkkäisistä muistipaikoista, joihin voidaan tallentaa tietoa. Jokaisella muistipaikalla on osoite, jolla siihen voidaan viitata. Muistiin tallennetaan tiedot, joita ohjelma käsittelee suorituksensa aikana.

Tarkastellaan esimerkkinä seuraavaa Python-ohjelmaa:

a = 7
b = -3
c = [1, 2, 3, 1, 2]
d = 99

Oletetaan, että ohjelmassa määritellyt muuttujat ja lista on tallennettu muistiin osoitteesta 100 alkaen. Seuraavassa on yksinkertaistettu esitys siitä, miltä muistin sisältö voisi näyttää tässä tilanteessa:

Tässä muuttujan a sisältö on muistipaikassa 100 ja muuttujan b sisältö on muistipaikassa 101. Listalle c on varattu muistipaikat 102–109, joista tällä hetkellä on käytössä muistipaikat 101–106, koska listalla on 5 alkiota. Muuttujan d sisältö on puolestaan muistipaikassa 110.

Listan alkiot on tallennettu peräkkäisiin muistipaikkoihin, minkä ansiosta on helppoa selvittää, missä kohdassa muistia tietty listan alkio sijaitsee. Tämä saadaan laskettua kaavalla base + i, missä base on listan ensimmäisen alkion osoite ja i on halutun alkion indeksi. Tässä tapauksessa esimerkiksi listan kohdassa 2 oleva alkio on osoitteessa 102 + 2 = 104.

Huomaa, että listalle on varattu enemmän muistia kuin olisi tällä hetkellä tarvetta. Tämän ideana on varautua siihen, että listan alkioiden määrä saattaa kasvaa myöhemmin. Listaan liittyy siis kaksi kokoa: listan todellinen koko (tässä 5) sekä listalle muistista varatun alueen koko (tässä 8).

Listan operaatiot

Pythonissa on monia valmiita operaatioita, joiden avulla voidaan käsitellä listoja. Tarkastellaan seuraavaksi näiden operaatioiden tehokkuutta aikavaativuuksien näkökulmasta olettaen, että listalla on \(n\) alkiota.

Listan operaatioiden aikavaativuuksien tunteminen on tärkeää algoritmien suunnittelussa, koska niistä voi päätellä, mitä operaatioita voi käyttää tehokkaan algoritmin osana. Yleisimmät aikavaativuudet ovat:

• \(O(1)\): operaatio toimii aina tehokkaasti riippumatta listan koosta
• \(O(n)\): operaation tehokkuus riippuu listan koosta ja operaatio voi olla hidas, jos listan koko on suuri

Indeksointi

Listan alkioita voidaan hakea tai muuttaa indeksin perusteella []-syntaksilla.

numbers = [4, 3, 7, 3, 2]
print(numbers[2]) # 7
numbers[2] = 5
print(numbers[2]) # 5

Alkion hakeminen tai muuttaminen vie aikaa \(O(1)\), koska alkiot ovat peräkkäin muistissa ja tietyn alkion muistiosoite voidaan laskea tehokkaasti.

Listan koko

Funktio len kertoo, montako alkiota listalla on:

numbers = [4, 3, 7, 3, 2]
print(len(numbers)) # 5

Funktio vie aikaa \(O(1)\), koska listan yhteyteen muistissa on tallennettu sen koko.

Etsiminen

Operaattori in kertoo, onko alkio listalla. Metodi index antaa ensimmäisen indeksin, jossa alkio esiintyy listalla. Metodi count laskee, montako kertaa alkio esiintyy listalla.

numbers = [4, 3, 7, 3, 2]

print(3 in numbers) # True
print(8 in numbers) # False

print(numbers.index(3)) # 1
print(numbers.count(3)) # 2

Kaikki nämä operaatiot vievät aikaa \(O(n)\), koska niiden täytyy käydä läpi listan alkiot. Esimerkiksi metodi count vastaa logiikaltaan seuraavaa funktiota, joka käy läpi listan alkiot silmukan avulla:

def count(items, target):
    result = 0
    for item in items:
        if item == target:
            result += 1
    return result

Huomaa, että operaatiot saattavat toimia tehokkaasti tietyissä tapauksissa. Esimerkiksi jos etsittävä alkio on listan alussa, operaattori in toimii nopeasti, koska se voi lopettaa listan läpikäynnin heti alkion löydyttyä. Kuitenkin pahimmassa tapauksessa alkio ei esiinny listalla ja koko lista täytyy käydä läpi.

Alkion lisääminen

Metodi append lisää alkion listan loppuun, ja metodi insert lisää alkion annettuun kohtaan listalla.

numbers = [1, 2, 3, 4]

numbers.append(5)
print(numbers) # [1, 2, 3, 4, 5]

numbers.insert(1, 6)
print(numbers) # [1, 6, 2, 3, 4, 5]

Näiden metodien aikavaativuuteen vaikuttaa listan tallennustapa muistissa. Listan ensimmäinen alkio on tallennettu tiettyyn kohtaan muistia, ja kaikki muut alkiot on tallennettu peräkkäin sen jälkeen. Esimerkiksi yllä olevan koodin alussa muistin sisältö voi näyttää seuraavalta ennen lisäyksiä:

Metodi append toimii ajassa \(O(1)\), koska alkion lisääminen listan loppuun ei aiheuta muutoksia muiden alkioiden paikkoihin. Esimerkissä alkio 5 voidaan lisätä tallentamalla se muistipaikkaan 104:

Jos listalle varatulla muistialueella ei ole tilaa uudelle alkiolle, listalle täytyy varata uusi suurempi muistialue ja siirtää listan sisältö sinne. Kuitenkin sopivalla toteutuksella tämä tilanne esiintyy harvoin ja metodi append toimii keskimäärin ajassa \(O(1)\).

Metodi insert toimii ajassa \(O(n)\), koska kun alkio lisätään muualle kuin listan loppuun, kaikkia sen jälkeisiä alkioita tulee siirtää eteenpäin. Esimerkiksi kun alkio 6 lisätään listalle kohtaan 1, alkioita täytyy siirtää muistissa näin:

Huomaa, että metodi insert on kuitenkin tehokas, jos alkio lisätään listan loppuosaan ja siirrettävien alkioiden määrä on pieni.

Alkion poistaminen

Metodi pop poistaa alkion listasta. Jos metodia kutsutaan ilman parametria, se poistaa listan viimeisen alkion. Jos metodille annetaan parametri, se poistaa alkion parametrin mukaisesta indeksistä.

numbers = [1, 2, 3, 4, 5, 6]

numbers.pop()
print(numbers) # [1, 2, 3, 4, 5]

numbers.pop(1)
print(numbers) # [1, 3, 4, 5]

Tarkastellaan taas, miten alkion poistaminen vaikuttaa muistin sisältöön. Koodin alussa muistin sisältö voi näyttää seuraavalta:

Kuten lisäämisessä, alkion poistaminen listan lopusta vie aikaa \(O(1)\), koska tämä ei vaikuta muihin alkioihin. Alkion 6 poistaminen muuttaa muistin sisältöä näin:

Alkion poistaminen listan keskeltä puolestaan vie aikaa \(O(n)\), koska poistetun alkion jälkeisiä alkioita täytyy siirtää taaksepäin. Alkion 2 poistaminen muuttaa muistin sisältöä näin:

Listalla on myös metodi remove, joka poistaa annetun alkion ensimmäisen esiintymän listasta:

numbers = [1, 2, 3, 1, 2, 3]

numbers.remove(3)
print(numbers) # [1, 2, 1, 2, 3]

Metodin aikavaativuus on \(O(n)\), koska metodin täytyy ensin etsiä poistettava alkio listalta (samaan tapaan kuin metodissa index) ja sen jälkeen poistaa alkio ja siirtää sen jälkeen listassa tulevat alkiot.

Yhteenveto

Seuraava taulukko näyttää yhteenvedon tässä käsiteltyjen listan operaatioiden tehokkuudesta:

Listan tehokkaita operaatioita ovat siis alkioiden indeksointi, alkioiden määrän laskeminen sekä alkion lisääminen ja poistaminen listan lopussa. Lista soveltuu erityisesti käytettäväksi algoritmeissa, joissa tehdään enimmäkseen näitä tehokkaita operaatioita ja vähän muita operaatioita.

Viittaukset ja kopiointi

Pythonissa listoja ja muita tietorakenteita käsitellään viittausten kautta, ja listan sijoittaminen muuttujaan kopioi vain viittauksen:

a = [1, 2, 3, 4]
b = a
a.append(5)

print(a) # [1, 2, 3, 4, 5]
print(b) # [1, 2, 3, 4, 5]

Tässä rivi b = a saa aikaan, että muuttujat a ja b viittaavat samaan listaan muistissa. Kun listalle a lisätään uusi alkio, tämä heijastuu myös listaan b.

Jos halutaan kopioida viittauksen sijasta listan sisältö, voidaan käyttää metodia copy seuraavasti:

a = [1, 2, 3, 4]
b = a.copy()
a.append(5)

print(a) # [1, 2, 3, 4, 5]
print(b) # [1, 2, 3, 4]

Tämän seurauksena muuttujat a ja b viittaavat eri listoihin muistissa eikä alkion lisääminen listalle a vaikuta listan b sisältöön.

Äskeisten koodien tehokkuudessa on merkittävä ero: viittauksen kopiointi vie aikaa \(O(1)\), kun taas sisällön kopiointi vie aikaa \(O(n)\). Niinpä rivi b = a vie aikaa \(O(1)\), kun taas rivi b = a.copy() vie aikaa \(O(n)\).

Funktion sivuvaikutukset

Kun funktion parametriksi annetaan tietorakenne, myös tässä tapauksessa kopioidaan vain viittaus. Tällöin funktio voi aiheuttaa sivuvaikutuksia, jos se muuttaa tietorakenteen sisältöä.

Tarkastellaan esimerkkinä seuraavaa funktiota double, joka palauttaa listan, jossa jokainen annetun listan luku on kaksinkertainen:

def double(numbers):
    result = numbers
    for i in range(len(result)):
        result[i] *= 2
    return result

Koska vain listan viittaus kopioidaan, funktion sivuvaikutuksena on, että se muuttaa parametrina annettua listaa:

numbers = [1, 2, 3, 4]
print(double(numbers)) # [2, 4, 6, 8]
print(numbers) # [2, 4, 6, 8]

Tämä ei ole hyvä tilanne, koska funktion tulisi palauttaa uusi lista eikä tehdä muutosta annettuun listaan. Voimme korjata asian esimerkiksi metodin copy avulla:

def double(numbers):
    result = numbers.copy()
    for i in range(len(result)):
        result[i] *= 2
    return result

Tämän jälkeen funktio ei enää muuta alkuperäisen listan sisältöä:

numbers = [1, 2, 3, 4]
print(double(numbers)) # [2, 4, 6, 8]
print(numbers) # [1, 2, 3, 4]

Listan ositus ja yhdistäminen

Pythonin slice-operaattori (syntaksi [:]) luo olemassa olevan listan pohjalta uuden listan, joka sisältää halutun listan välin:

numbers = [1, 2, 3, 4, 5, 6, 7, 8]
print(numbers[2:6]) # [3, 4, 5, 6]

Tämä operaattori vie aikaa \(O(n)\), koska operaattori kopioi uuteen listaan vanhan listan sisällön annetulta väliltä.

Koska slice-operaattori kopioi listan välin, sen avulla voidaan myös tehdä kopio koko listasta. Seuraavat kaksi riviä tarkoittavat samaa:

numbers = numbers.copy()
numbers = numbers[:]

Operaattorin + avulla voidaan yhdistää listoja:

first = [1, 2, 3, 4]
second = [5, 6, 7, 8]
print(first + second) # [1, 2, 3, 4, 5, 6, 7, 8]

Tämä vie myös aikaa \(O(n)\), koska operaattori kopioi uuteen listaan alkiot yhdistettäviltä listoilta.

Listat muissa kielissä

Tässä luvussa käsitelty listan toteutus tunnetaan yleisemmin nimellä taulukkolista (array list) tai dynaaminen taulukko (dynamic array).

Matalan tason kielissä (kuten C++ ja Java) perustietorakenne on yleensä taulukko (array). Listan tavoin taulukko sisältää peräkkäisiä alkioita, joita voidaan indeksoida. Kuitenkin taulukolle varataan kiinteä muistialue luontihetkellä, eikä taulukon kokoa voi muuttaa myöhemmin. Taulukon lisäksi kielissä on kuitenkin saatavilla listoja, joiden kokoa pystyy muuttamaan.

C++:ssa tietorakenne std::vector toteuttaa listan:

std::vector<int> numbers;

numbers.push_back(1);
numbers.push_back(2);
numbers.push_back(3);

Javassa puolestaan tietorakenne ArrayList toteuttaa listan:

ArrayList<Integer> numbers = new ArrayList<>();

numbers.add(1);
numbers.add(2);
numbers.add(3);

JavaScriptin perustietorakenne on nimeltään taulukko (Array), mutta se on todellisuudessa lista, koska sen kokoa pystyy muuttamaan:

numbers = [];

numbers.push(1);
numbers.push(2);
numbers.push(3);