Which sequence operations does Python’s list support and how are they implemented?

Overview

Python lists inherit a rich set of sequence‑type methods in addition to their custom methods. These operations are implemented in the CPython runtime via method groups (tp_as_number, tp_as_sequence, tp_as_mapping), each mapping to numerous C functions that correspond to Python magic methods and operators.

Method groups for sequence objects

tp_as_number – numeric object methods

tp_as_sequence – sequence object methods (e.g., concatenation, repetition, indexing, slicing)

tp_as_mapping – mapping object methods

Each group contains many C functions; for lists, the relevant functions are bound to magic methods such as __add__ (tp_as_sequence.sq_concat) and __sub__ (tp_as_number.nb_subtract).

List concatenation ( + )

Using the + operator on two lists triggers tp_as_sequence.sq_concat, which points to the list_concat function.

static PyObject *
list_concat(PyListObject *a, PyObject *bb)
{
    Py_ssize_t size;
    Py_ssize_t i;
    PyObject **src, **dest;
    PyListObject *np;
    if (!PyList_Check(bb)) {
        PyErr_Format(PyExc_TypeError,
                     "can only concatenate list (not \"%.200s\") to list",
                     Py_TYPE(bb)->tp_name);
        return NULL;
    }
    #define b ((PyListObject *)bb)
    assert((size_t)Py_SIZE(a) + (size_t)Py_SIZE(b) < PY_SSIZE_T_MAX);
    size = Py_SIZE(a) + Py_SIZE(b);
    if (size == 0) {
        return PyList_New(0);
    }
    np = (PyListObject *) list_new_prealloc(size);
    if (np == NULL) {
        return NULL;
    }
    src = a->ob_item;
    dest = np->ob_item;
    for (i = 0; i < Py_SIZE(a); i++) {
        PyObject *v = src[i];
        dest[i] = Py_NewRef(v);
    }
    src = b->ob_item;
    dest = np->ob_item + Py_SIZE(a);
    for (i = 0; i < Py_SIZE(b); i++) {
        PyObject *v = src[i];
        dest[i] = Py_NewRef(v);
    }
    Py_SET_SIZE(np, size);
    return (PyObject *)np;
}

The logic creates a new list of combined length, copies elements from both operands with reference‑count adjustments, and returns the new list.

List repetition ( * )

Multiplying a list by an integer invokes tp_as_sequence.sq_repeat, which maps to list_repeat.

static PyObject *
list_repeat(PyListObject *a, Py_ssize_t n)
{
    const Py_ssize_t input_size = Py_SIZE(a);
    if (input_size == 0 || n <= 0)
        return PyList_New(0);
    assert(n > 0);
    if (input_size > PY_SSIZE_T_MAX / n)
        return PyErr_NoMemory();
    Py_ssize_t output_size = input_size * n;
    PyListObject *np = (PyListObject *)list_new_prealloc(output_size);
    if (np == NULL)
        return NULL;
    PyObject **dest = np->ob_item;
    if (input_size == 1) {
        PyObject *elem = a->ob_item[0];
        _Py_RefcntAdd(elem, n);
        PyObject **dest_end = dest + output_size;
        while (dest < dest_end) {
            *dest++ = elem;
        }
    } else {
        PyObject **src = a->ob_item;
        PyObject **src_end = src + input_size;
        while (src < src_end) {
            _Py_RefcntAdd(*src, n);
            *dest++ = *src++;
        }
        _Py_memory_repeat((char *)np->ob_item,
                         sizeof(PyObject *)*output_size,
                         sizeof(PyObject *)*input_size);
    }
    Py_SET_SIZE(np, output_size);
    return (PyObject *)np;
}

The function handles edge cases (empty list or non‑positive multiplier), allocates space, and either replicates a single element efficiently or copies the original elements and repeats the memory block.

Indexing and slicing retrieval

Accessing elements via index or slice uses tp_as_mapping.mp_subscript, which points to list_subscript.

static PyObject *
list_subscript(PyListObject* self, PyObject* item)
{
    if (_PyIndex_Check(item)) {
        Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
        if (i == -1 && PyErr_Occurred())
            return NULL;
        if (i < 0)
            i += PyList_GET_SIZE(self);
        return list_item(self, i);
    }
    else if (PySlice_Check(item)) {
        Py_ssize_t start, stop, step, slicelength, i;
        size_t cur;
        PyObject *result;
        PyObject *it;
        PyObject **src, **dest;
        if (PySlice_Unpack(item, &start, &stop, &step) < 0)
            return NULL;
        slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop, step);
        if (slicelength <= 0)
            return PyList_New(0);
        if (step == 1) {
            return list_slice(self, start, stop);
        } else {
            result = list_new_prealloc(slicelength);
            if (!result) return NULL;
            src = self->ob_item;
            dest = ((PyListObject *)result)->ob_item;
            for (cur = start, i = 0; i < slicelength; cur += (size_t)step, i++) {
                it = Py_NewRef(src[cur]);
                dest[i] = it;
            }
            Py_SET_SIZE(result, slicelength);
            return result;
        }
    }
    else {
        PyErr_Format(PyExc_TypeError,
                     "list indices must be integers or slices, not %.200s",
                     Py_TYPE(item)->tp_name);
        return NULL;
    }
}

The function distinguishes between integer indices and slice objects, adjusts negative indices, and either returns a single element via list_item or constructs a new list for the slice.

Indexing and slicing assignment

Modifying elements uses tp_as_mapping.mp_ass_subscript, which maps to list_ass_subscript. The function handles both index and slice assignments, including deletions (assigning an empty iterable) and extended‑slice constraints (step must be 1 for bulk assignment).

Key points:

Index assignment calls list_ass_item.

Slice assignment calls list_ass_slice. Deleting an element is performed by assigning an empty sequence to the slice.

When the slice step is not 1, the right‑hand iterable must match the number of elements selected; otherwise a ValueError is raised.

Conclusion

The article details how Python’s list, as a mutable sequence type, implements its core operations at the C level. Understanding the underlying slots and functions— list_concat, list_repeat, list_subscript, and list_ass_subscript —clarifies the behavior of the high‑level +, *, indexing, slicing, and assignment syntax.