How is Python’s List Implemented?

by

The C code is pretty simple, actually. Expanding one macro and pruning some irrelevant comments, the basic structure is in listobject.h, which defines a list as:

typedef struct {
    PyObject_HEAD
    Py_ssize_t ob_size;

    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     */
    Py_ssize_t allocated;
} PyListObject;

PyObject_HEAD contains a reference count and a type identifier. So, it’s a vector/array that overallocates. The code for resizing such an array when it’s full is in listobject.c. It doesn’t actually double the array, but grows by allocating

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
new_allocated += newsize;

to the capacity each time, where newsize is the requested size (not necessarily allocated + 1 because you can extend by an arbitrary number of elements instead of append‘ing them one by one).

See also the Python FAQ.

More Related Contents:

  1. I have a list of file names and I need to be able to count how many of the same file gets repeated for each file name [closed]
  2. What are the advantages of NumPy over regular Python lists?
  3. Python List vs. Array – when to use?
  4. How to read a text file into a list or an array with Python
  5. Are tuples more efficient than lists in Python?
  6. Why can tuples contain mutable items?
  7. Flatten list of lists [duplicate]
  8. Can I create a “view” on a Python list?
  9. list() uses slightly more memory than list comprehension
  10. Find nearest indices for one array against all values in another array – Python / NumPy
  11. Accessing the list while being sorted
  12. Sort multidimensional array based on 2nd element of the subarray
  13. Tuple or list when using ‘in’ in an ‘if’ clause?
  14. Initializing a list to a known number of elements in Python [duplicate]
  15. How to read an array of integers from single line of input in python3
  16. Implement list-like index access in Python
  17. List to array conversion to use ravel() function
  18. Numpy individual element access slower than for lists
  19. How to group elements in python by n elements [duplicate]
  20. Why do two identical lists have a different memory footprint?
  21. Identify duplicate values in a list in Python
  22. Why does list ask about __len__?
  23. How to access a column in a list of lists in python
  24. How to sort multidimensional array by column?
  25. Python list([]) and []
  26. Python recursive function to display all subsets of given set
  27. Why does creating a list from a list make it larger?
  28. Python: Elegant and efficient ways to mask a list
  29. How does str(list) work?
  30. Optimal method to find the max of sublist items within list

Leave a Comment