В этом задании необходимо написать класс узел - Node, который будет представлять собой объект с тремя полями: value, prev, next. Этот класс должен содержать конструктор, принимающий в себя переменную value и записывает в его в соответствующее поле value в класса.
После этого реализовать класс LinkedList, который должен содержать в себе поля head ( “голова”, или первый элемент списка) и tail ( “хвост”, или последний элемент списка), а также должен реализовывать соответствующие методы:
push (value) - добавить новый узел со значением value в конец списка
pop () - удалить последний узел из списка и вернуть его значения; если список пуст - так и оставить его пустым
unshift (value) - добавить новый узел со значением value в начало списка
shift () - удалить первый узел с начала списка и вернуть его значения; если список пуст - так и оставить его пустым
insert (index, value) - добавить новый узел со значением value на место index в списке, элемент, который был на месте index, теперь в списке пойдет после только добавленного значения; если длина списка меньше, чем index - добавить новый узел со значением value в конец списка.
find (v) - найти и вернуть первый объект класса Node, value которого равна v; если такого нет, вернуть None
get (index) - вернуть элемент на позиции index от головы, считая, что индекс головы = 0
size () - вернуть размер списка
print () - выводит элементы списка на экран поочередно от головы до хвоста
Input Format
На первой строке входа дано число N - количество элементов, которые надо будет добавить в список. На второй строчке - собственно N элементов типа int, разделенные пробелом. Третья строка содержит число M - количество операций, которые должны быть выполнены со списком, они будут заданы по сделке на строку - M строк с операциями. Должна быть поддержка следующих операций:
push A, где A - число типа float
pop
unshift A, где A - число типа float
shift
insert A B, где A - индекс, куда вставить элемент, B - число типа float
Constraints
0 <= N <1000000 0 <= M <1000000
Output Format
На выходе программа должна вывести две строки: элементы списка от хвоста к голове после выполнения всех операций, заданных во входном файле, и элементы списка от головы до хвоста при аналогичных условиях.
Sample Input 0
5 1 2 3 4 5 5 push 1 shift push 10 pop unshift -10
Sample Output 0
1.0 5.0 4.0 3.0 2.0 -10.0 -10.0 2.0 3.0 4.0 5.0 1.0