Pikalista

Tehtäväsi on toteuttaa oma tehokas lista-tietorakenne, joka tarjoaa seuraavat toiminnot:

• Poista listalta listan $k$ ensimmäistä alkiota ja siirrä ne samassa järjestyksessä listan loppuun
• Ilmoita, mikä alkio listalta löytyy indeksiltä $i$

Tietorakenteen jokaisen operaation tulee olla $O(1)$-aikainen. Voit olettaa, että jokainen alkio on kokonaisluku väliltä $1 \dots 10^9$.

Toteuta tiedostoon quicklist.py luokka QuickList seuraavan mallin mukaisesti.

class QuickList:
    def __init__(self, t):
        # TODO

    def move(self, k):
        # TODO

    def get(self, i):
        # TODO

if __name__ == "__main__":
    q = QuickList([1,2,3,4,5,6,7,8,9,10])
    print(q.get(4)) # 5
    q.move(3)
    print(q.get(4)) # 8
    q.move(3)
    print(q.get(4)) # 1
    q.move(10)
    print(q.get(4)) # 1
    q.move(7)
    q.move(5)
    print(q.get(0)) # 9

Selitys Listan sisältö käyttäytyy koodipohjassa näin:

• $[1,2,3,4,5,6,7,8,9,10]$
• move(3) $\rightarrow$ $[4,5,6,7,8,9,10,1,2,3]$
• move(3) $\rightarrow$ $[7,8,9,10,1,2,3,4,5,6]$
• move(10) $\rightarrow$ $[7,8,9,10,1,2,3,4,5,6]$
• move(7) $\rightarrow$ $[4,5,6,7,8,9,10,1,2,3]$
• move(5) $\rightarrow$ $[9,10,1,2,3,4,5,6,7,8]$