I am writing a program, that does a lot of deletions at either the front or back of a list of data, never the middle.
I understand that deletion of the last element is cheap, but how about deletion of the first element? For example let's say list
No, it isn't cheap. Removing an element from the front of the list (using
list.pop(0) for example) is
O(N) and should be avoided. Similarly, inserting elements at the beginning (using
list.insert(0, <value>) is equally inefficient. Lists are built for fast random access and
O(1) operations on their end.
Since you're doing this operation commonly, though, you should consider using a
collections as @ayhan suggested in a comment. The docs on
deque also highlight how lists aren't suitable for these operations:
Though list objects support similar operations, they are optimized for fast fixed-length operations and incur
O(n)memory movement costs for
insert(0, v)operations which change both the size and position of the underlying data representation.
deque data structure offers
O(1) complexity for both sides (beginning and end) with
pop methods for the beginning and end respectively.
Of course, with small sizes this incurs some extra space requirements (due to the structure of the
deque) which should generally be of no concern (and as @juanpa noted in a comment, doesn't always hold) as the sizes of the lists grow. Finally, as @ShadowRanger's insightful comment notes, with really small sequence sizes the problem of popping or inserting from the front is trivialized to the point that it becomes of really no concern.
So, in short, for lists with many items, use
deque if you need fast appends/pops from both sides, else, if you're randomly accessing and appending to the end, use