In fact it can't be O(1) .
We require that only the operations listed in bullets will take O(1) time.
It is possible if you maintain a string representation, modifying it with every operation.
Class Node's "next" method is invalid. You can't assign the same name to the method and the attribute, Python doesn't handle this overloading:
>>> n = Node(1) >>> n.next >>> n.next() Traceback (most recent call last): File "<pyshell#88>", line 1, in <module> n.next() TypeError: 'NoneType' object is not callable
You are correct. Please change the field name to a different name and keep the name of the method next()
Is this a mandatory change? Personally, I haven't used the next() method at all and just accessed the next node using the next field. Yes, it may be bad practice, but each case to itself.
In object oriented programming it is recommended to use a "getter" function in order to get a value of a certain field (that may be private). It is not mandatory here though.
In addition to the above question: I've written the code without the Node class methods addNext, next, is_last, val.
I've used only init and repr and added an extra variable to init.
Is it ok this way or should we use these methods?
i mean- if your tester will use addNext for example, my code won't give a proper list in the end..
should any of the methods we are implementing return anything? is it o.k for them to return "self"?
head_insert, tail_insert, head_remove, tail_remove - should all not return any value (not even "self") - you can look at the Linked_list code for reference.
head, tail - should return something - according to the given definitions.
what is the complixity of reverse function that we see in the recitation?
If i did function with conditions, can I call in one of them to another function (with O(1)) and the complexity still be O(1) to the first one?
If in tail_remove I called to head_remove, which is O(1), does it mean that tail_remove is still O(1)?
Should head() and tail() return a node object, or the value of the node?
I would expect it to return the node object. Similarly to get_item method in Linked_list class that you saw in the recitation.
In fact , according to the code given in test() you must return a node object:
if (dq.head() != None and dq.head().val() != Node(2).val()): print("error in Deque")
what should happen if i try to remove node from empty deque?
None or error??
what should be displayed if deque is empty?
an empty string or None?