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

• Lisää alkio listan loppuun
• Palauta ja poista alkio listan lopusta
• Lisää alkio listan alkuun
• Palauta ja poista alkio listan alusta
• Käännä listan sisältö

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

Python

Toteuta tiedostoon fliplist.py luokka FlipList seuraavan mallin mukaisesti.

class FlipList:
    def push_last(self,x):
        # TODO

    def push_first(self,x):
        # TODO

    def pop_last(self):
        # TODO

    def pop_first(self):
        # TODO

    def flip(self):
        # TODO

if __name__ == "__main__":
    f = FlipList()
    f.push_last(1)
    f.push_last(2)
    f.push_last(3)
    print(f.pop_first()) # 1
    f.flip()
    print(f.pop_first()) # 3

Java

Toteuta tiedostoon FlipList.java luokka FlipList seuraavan mallin mukaisesti.

public class FlipList {
    public void pushLast(int x) {
        // TODO
    }

    public void pushFirst(int x) {
        // TODO
    }

    public int popLast() {
        // TODO
    }

    public int popFirst() {
        // TODO
    }

    public void flip() {
        // TODO
    }

    public static void main(String[] args) {
        FlipList f = new FlipList();
        f.pushLast(1);
        f.pushLast(2);
        f.pushLast(3);
        System.out.println(f.popFirst()); // 1
        f.flip();
        System.out.println(f.popFirst()); // 3
    }
}