Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is removing an element from the front of a list cheap in Python?

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 A's address is at 4000, so element 0 is at 4000 and element 1 is at 4001.

Would deleting element 0 then just make the compiler put list A's address at 4001, or would it shift element 1 at 4001 to the location at 4000, and shift all other elements down by 1?

like image 432
Abid Rizvi Avatar asked Feb 02 '17 22:02

Abid Rizvi


People also ask

What happens when we remove an element from a list in Python?

The remove() Method Removes the First Occurrence of an Item in a List. A thing to keep in mind when using the remove() method is that it will search for and will remove only the first instance of an item.

How do you remove items from the front of a list in Python?

The remove() method removes the first matching element (which is passed as an argument) from the list. The pop() method removes an element at a given index, and will also return the removed item. You can also use the del keyword in Python to remove an element or slice from a list.

Can you remove elements from a list in Python?

In Python, use list methods clear() , pop() , and remove() to remove items (elements) from a list. It is also possible to delete items using del statement by specifying a position or range with an index or slice.

What is the difference between del () and remove () methods of list?

Remove() deletes the matching element from the list whereas the del and pop removes the element present at specified index. Difference between pop and del is that pop returns the deleted value whereas del does not.


2 Answers

No, it isn't cheap. Removing an element from the front of the list (using list.pop(0), for example) is an O(N) operation and should be avoided. Similarly, inserting elements at the beginning (using list.insert(0, <value>)) is equally inefficient.

This is because, after the list is resized, it's elements must be shifted. For CPython, in the l.pop(0) case, this is done with memmove while for l.insert(0, <value>), the shifting is implemented with a loop through the items stored.

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 deque from the collections module (as @ayhan suggested in a comment). The docs on deque also highlight how list objects 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 pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

(Emphasis mine)

The deque data structure offers O(1) complexity for both sides (beginning and end) with appendleft/popleft and append/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 lists.

like image 160
Dimitris Fasarakis Hilliard Avatar answered Sep 17 '22 00:09

Dimitris Fasarakis Hilliard


Removing elements from the front of a list in Python is O(n), while removing elements from the ends of a collections.deque is only O(1). A deque would be great for your purpose as a result, however it should be noted that accessing or adding/removing from the middle of a deque is more costly than for a list.

The O(n) cost for removal is because a list in CPython is simply implemented as an array of pointers, thus your intuition regarding the shifting cost for each element is correct.

This can be seen in the Python TimeComplexity page on the Wiki.

like image 39
miradulo Avatar answered Sep 18 '22 00:09

miradulo