Queue O(1) not as fast append or pop in python

Question

I made a Queue O(1) using Nodes where Queue class contain "Head and Tail" and Node Contain "Next and Back" but when I Compared "enqueue and dequeue" to " append and pop " through "timeit" I found out that " append and pop " are way faster than "enqueue and dequeue" I made. Am I doing something wrong with Node or Queue or my O(1) will not be as fast as append or pop ?

Answer 1

An "arraylist" (which is the data structure behind Python's list) has an amortized cost of O(1) as well, so in terms of big oh, the two are equivalent. Indeed, the list has O(n) to append worst case, but this happens not very often. Typically the list has an initial capacity, and when the list is full, then it doubles the capacity. This means that if we want to make a list with n elements, and n is quite big, then the the list will be resized to capacities:

1, 2, 4, 8, 16, …, n

It each time takes the length of the original list in time to make a copy in the larger array, so that means that the total amount spent copying is the sum of these numbers, which is 2×n-1, and this O(n), this thus means that n append, take in total O(n), time, and thus the amortized cost of an append in a list is O(1).

But there are other reasons why your linked list will be less efficient. Each time you construct a new node, it will look for a memory slot, often allocating memory takes some time. Furthermore Python's lists are typically implemented in the interpreter, for CPython [GitHub] for example, likely the interpreter you are using, it works with a PyListObject [GitHub], this is often more efficient than implementing something in Python itself, since that is interpreted.