Is Python\'s List Implemented as a Linked List or an Array?

Python List Implementation Unveiled

Is it a Linked List or an Array?

In the realm of Python's list operations, the underlying implementation remains a mystery to many. Speculations abound, but concrete answers have eluded the curious. To shed light on this enigma, we delve into the C code, unmasking the true nature of Python's list structure.

A Vector of Pointers

Contrary to guesses of a linked list, Python's list is built upon an array-like structure. Examining the listobject.h header reveals the core definition of a list: a type called PyListObject. This structure comprises three essential elements:

• ob_size: The number of elements currently used.
• ob_item: An array of Python object pointers, representing the list items.
• allocated: The maximum capacity of the array.

Dynamic Allocation and Overallocation

The array ob_item provides direct access to list elements, akin to an array in C. However, Python adopts a strategy of overallocation to optimize efficiency. When the ob_item array is filled to capacity, a new larger array is allocated. The new capacity is computed using the formula:

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

where newsize is the requested size. This formula ensures adequate space for future insertions while avoiding excessive allocation overheads.

In Conclusion

Behind Python's list interface lies a vector-based implementation. Each list item is represented by a pointer to an object, and the vector itself is dynamically allocated and overallocated to enhance performance. This approach strikes a balance between efficient storage and flexible growth, enabling the seamless operation of Python's essential list data structure.

The above is the detailed content of Is Python\'s List Implemented as a Linked List or an Array?. For more information, please follow other related articles on the PHP Chinese website!