CODEWITHSUNDEEP
pythonlistmemorypython-internals
zzz
zzz

Reputation: 2634

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

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)))

Upvotes: 10

Views: 2908

Answers (3)

thefourtheye
thefourtheye

Reputation: 239603

  1. 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

  2. It removes only the first matched item and returns immediately.

  3. 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.

Upvotes: 7

Wubao Li
Wubao Li

Reputation: 1748

  1. 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.

  2. 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.

Upvotes: 1

Greg Hewgill
Greg Hewgill

Reputation: 994131

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")

Upvotes: 4

Related Questions