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):
        ...

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)

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

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

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 LinkedListin 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.

Palautettava tiedosto