3.4. Tehtävä: Linkitetty lista (170 p)
Tästä sivusta:
Mitä käsitellään? Linkitettyä listaa, rekursiota, testausta.
Mitä tehdään? Tutustutaan yksinkertaiseen tietorakenteeseen ja kirjoitetaan sille pari rekursiivista metodia. Lisäksi kirjoitetaan testejä.
Suuntaa antava vaativuusarvio: Keskivaikea lähinnä uusien asioiden vuoksi. Itse tehtävä ei lopulta ole kovin haastava.
Suuntaa antava työläysarvio: 3 tuntia
Pistearvo: 170 pistettä
Linkitetty lista
Linkitetty lista on yksi perinteisimpiä tietorakenteita. Linkitetty lista koostuu soluista (Cell
), jotka sisältävät yhden arvon ja viittauksen
listan seuraavaan soluun tai erityiseen tyhjään elementtiin (Empty
). Kuvassa näkyy, miten listat muodostuvat soluista ja voivat jakaa
rakennetta keskenään. Nuolilla yhdistetyt laatikot ovat olioita ja erilliset kirjaimet a, b, ..., g muuttujia, jotka viittaavat
linkitettyihin listoihin.
![../../_images/LinkedList.png](../../_images/LinkedList.png)
Esimerkiksi a viittaa listaan, joka sisältää arvot None, True, 10
, ja b listaan, joka sisältää vain arvon 10
. Listat
a ja b jakavat rakennetta. Koska luokan Empty
ilmentymät eivät sisällä mitään dataa, teemme siitä vain yhden ilmentymän, ja se on
kaikkien listojen lopussa.
Hyvä tietää: Mikä on linkitetyn listan suhde Pythonin luokkaan list
?
Pythonin lista vastaa perinteisessä tietoteknisessä käsitteistössä yksiulotteista kiinteämittaista taulukkoa. Kun list
-olio kasvaa,
varaa Python uuden taulukon ja kopioi kaikki alkiot vanhasta taulukosta uuteen. Tämä on hidasta. Sen sijaan list
-olion alkioiden
indeksointi on nopeaa; se tapahtuu käytännössä vakioajassa, kun sen sijaan linkitetyssä listassa aikaa kuluu suhteessa listan pituuteen.
Eli molemmilla tietorakenteilla on hyvät ja huonot puolensa.
Luokka LinkedList
Määritämme linkitetyn listan kolmen luokan avulla: luokka LinkedList
sekä sen
alaluokat Empty
ja Cell
. Katsotaan näistä ensimmäistä.
class LinkedList:
'''
A linked list is either empty or a list cell, which
has a value and a link to another linked list, the 'tail' of the list.
This is an abstract class; you cannot make any direct
instances of it. Use Cell or Empty instead.
Most of the methods are implemented in subclasses.
'''
def is_empty(self):
'''Return true, if the list has no elements, otherwise false'''
pass
def length(self):
'''The length of a LinkedList.'''
pass
def nth(self, n):
'''The nth value in a LinkedList, counting from zero. Raises exception LinkedListException, if self is empty.'''
pass
def index(self, x, result=0):
'''The first index i in the linked list, where x is found, or None if x is not found.'''
pass
Luokassa määritetään neljä metodia, joille ei tässä määritetä toteutuksia; ne kuuluvat alaluokkiin Empty
ja Cell
. Emme määritä
__init__
-metodia, koska luokasta LinkedList
ei suoraan luoda ilmentymiä, eikä sen tarvitse myöskään tallettaa mitään dataa.
Luokka Empty
Katsotaan seuraavaksi alaluokkaa Empty
. Empty
esittää siis tyhjää listaa, jossa ei ole yhtään arvoa tallennettuna. Emme tarpeettomasti
halua luoda ylimääräisiä Empty
-olioita. Yksi ja sama riittää esittämään kaikkia tyhjiä listoja, koska mitään dataa ei tyhjässä listassa
ole. Miten saamme tämän aikaan?
class Empty(LinkedList):
'''A singleton representing the empty list'''
__instance = None
def __new__(cls):
'''Creates a new singleton, if there is none. Returns the singleton.'''
if cls.__instance is None:
cls.__instance = object.__new__(cls)
cls.__instance.name = "Empty"
return cls.__instance
def is_empty(self):
return True
def length(self):
return 0
def nth(self, n):
...
def index(self, x, result=0):
...
def __repr__(self):
...
__init__
). Metodi saa parametrin cls
, joka
on luokka (tässä tapauksessa Empty
itse). Metodin koodi pitää huolta, että luodaan vain yksi Empty
-olio ja seuraavilla kutsuilla
palautetaan tämä sama olio.__instance
.Empty
on tyhjä.Empty
n pituus on nolla.nth
ja index
koodia. Palaamme siihen myöhemmin tehtävien yhteydessä.Luokka Cell
Määritetään viellä luokka Cell
, joka kuvaa ei-tyhjää listan solua. Solussa on aina tallessa yksi arvo ja viittaus listan 'häntään', eli
seuraavan Cell
olioon tai Empty
olioon, mikäli tämä oli listan viimeinen solu.
class Cell(LinkedList):
def __init__(self, value, tail):
if not isinstance(tail, LinkedList):
raise LinkedListException('Cannot construct a Cell using {} as the tail'.format(tail))
self.value = value
self.tail = tail
def is_empty(self):
return False
def length(self):
return 1 + self.tail.length()
def nth(self, n):
...
def index(self, x, result=0):
...
def __repr__(self):
return 'Cell({}, {})'.format(self.value, self.tail)
value
on talletettava arvo.tail
viittää listan 'häntään', eli seuraavaa LinkedList
-olion.LinkedList
. Poikkeusluokka LinkedListException
on taas määritetty, jotta saamme informatiivisempia poikkeuksia.Cell
ei ole tyhjä lista.Cell
in pituus saadaan rekursiivisesti hännän pituuden avulla. Tässä kutsutaan metodia length
listan hännälle ja tähän lisätään yksi.Tehtävä 1 (50p)
Annetut tiedostot
Saat valmiina koodina tiedoston linked_list.py. Tiedostossa on
määritetty luokat LinkedList
, Empty
ja Cell
, joista jälkimmäisistä puuttuu koodia. Lisäksi tiedostossa on määritetty poikkeusluokka
LinkedListException
.
Mitä pitää tehdä?
Kopioi tiedostoon linked_list.py
metodit nth
luokissa Empty
ja Cell
. Metodi on määritetty seuraavasti:
'''The nth value in a LinkedList, counting from zero. Raises exception LinkedListException, if self is empty.'''
Käytä rekursiota. Kannattaa ottaa mallia luokissa Empty
ja Cell
toteutetusta metodista length
. Huomioi, miten työ jakautuu luokkien
kesken ja miten metodia Cell.length
kutsutaan listan hännälle. Jos rekursio hämmentää, voi siihen perehtyä esimerkiksi täällä.
Poikkeusluokka LinkedListException
on määritetty tiedostossa linked_list.py
.
Palautettava tiedosto
Tehtävä 2 (50p)
Annetut tiedostot
Voit käyttää edellisen kohdan vastaustasi tai tiedostoa linked_list.py.
Mitä pitää tehdä?
Toteuta luokkaan linked_list.py
metodi index
luokissa Empty
ja Cell
. Metodi on määritetty seuraavasti:
'''The first index i in the linked list, where x is found, or None if x is not found.'''
Käytä rekursiota.
Palautettava tiedosto
Hyvä tietää: Rekursion tehokkuus Pythonissa
Monien ohjelmointikielten toteutukset osaavat toteuttaa ns. häntärekursiiviset funktiot hyvin tehokkaasti, mutta Pythonin (perus-) toteutus ei
valitettavasti ole rekursion osalta tehokas. Jokaista sisäkkäistä rekursiivista funktiokutsua varten varataan tilaa suorituspinosta ja
tämä tila vapautuu vasta, kun funktiot palaavat. Eli Pythonissa kannattaa olla varovainen syvän rekursion kanssa. Huomaa, että linkitetyn
listan operaatiot olisi voinut toteuttaa myös ns. iteratiivisesti, eli käyttämällä while
-silmukkaa. Tässä tapauksessa toteutukset
olisi jopa voinut sisällyttää suoraan yläluokkaan LinkedList
.
Tehtävä 3 (70p)
Annetut tiedostot
Saat valmiina koodina tiedoston test_is_empty_and_length.py. Tarvitset myös tiedostoa
linkedlist.py
, jonka saat kopioimalla tiedoston linked_list.py.
Mitä pitää tehdä?
Tiedostossa test_is_empty_and_length.py
on tyhjä luokka TestIsEmptyAndLength
. Laadi luokkaan testimetodit LinkedList
in metodeille
is_empty
ja length
. Oleta, että metodien toteutuksissa voi olla virheitä (itse asiassa tehtävien tarkastin lisää niitä)! Testien pitää
siis epäonnistua, jos toteutus onkin väärä.
Huom! Laadi neljä testimetodia. Näistä kaksi testaa is_empty
-metodia syötteen ollessa Empty
tai Cell
ja vastaavasti kaksi testaa
length
-metodia syötteen ollessa Empty
tai Cell
.
LinkedList
ei tehdä suoraan ilmentymiä vaan ne tehdään alaluokista.