How does Python's list.remove(value) determine what value to remove?

Question

If I have list of objects:

l = [a, b, c]

Then I remove one of those objects:

l.remove(a)

How is python determining which item in the list to remove (under the hood)?

Is it using the memory location of a? (which you can view with hex(id(a)))

There’s no way to guess an item’s position in the list just from the value. The position completely depends on where you put the item in the first place. A set on the other hand uses a hash to determine item membership—but it will give you neither an order nor the possibilty to have multiple occurrences of the same item. — poke, Dec 20 '13 at 02:35

thefourtheye · Accepted Answer · 2013-12-20T04:44:21.583

It iterates through the list, compares every item with the item to be removed and if it finds a match, it just removes that. It works in O(N). Source: https://wiki.python.org/moin/TimeComplexity
It removes only the first matched item and returns immediately.
If the item to be removed is not there, it fails with ValueError

This is the listremove function which removes the item from a list and it uses PyObject_RichCompareBool to check if the items are the same. And PyObject_RichCompareBool is implemented like this

/* Quick result when objects are the same.
   Guarantees that identity implies equality. */
if (v == w) {
    if (op == Py_EQ)
        return 1;
    else if (op == Py_NE)
        return 0;
}

res = PyObject_RichCompare(v, w, op);

If the identity of the objects are the same (if both the objects are the same), then return 1 otherwise compare the values and return the result.

score 4 · Answer 2 · answered Dec 20 '13 at 02:02

4

Python uses the equality test ==. The remove method is similar to the following function:

def list_remove(a, el):
    for i in range(len(a)):
        if a[i] == el:
            del a[i]
            return
    raise ValueError("item not found")

answered Dec 20 '13 at 02:02

Greg Hewgill

951,095
183
1,149
1,285

2

Actually, I think it compares identity first, falling back on `__eq__` if that test turns our False ... – mgilson Dec 20 '13 at 03:03
1

@mgilson: I think you're right. `nan = float("nan"); a = [nan]; a.remove(nan)` works even though `nan != nan`. – DSM Dec 20 '13 at 03:06
@DSM -- Yeah. The real unfortunate thing is that `float('nan')` isn't a singleton. I used a class with `__eq__ = lambda self, other: False`, but it's the same idea. – mgilson Dec 20 '13 at 05:23

score 1 · Answer 3 · answered Dec 20 '13 at 02:29

if the class of the member object in the list defines the __eq__() method or the __cmp__() method, it will invoke this method to compare.
if not customize the comparison method, then Non-identical instances of a class normally compare as non-equal. it means the object address is used to compare.

How does Python's list.remove(value) determine what value to remove?

3 Answers3