Python 列表（list）是 Python 中非常常用的數據結構之一。它們的底層實現基于動態數組，具體來說，是一個可以動態調整大小的數組。這使得列表在操作和使用上非常靈活。以下是 Python 列表底層實現的主要原理：

動態數組

Python 列表是通過動態數組實現的，這意味著列表在需要時可以自動調整其大小。初始分配一個固定大小的數組，當元素數量超過當前容量時，會分配一個更大的新數組，并將舊數組的元素復制到新數組中。

動態調整大小

當列表需要擴展時，Python 不只是簡單地增加一個新元素，而是通常會按一定比例擴展列表的容量。常見的增長策略是將當前容量擴大為原來的 1.125 倍到 2 倍之間（具體策略取決于 Python 的實現版本）。這避免了每次添加新元素時都需要重新分配和復制數組，從而提高了性能。

內存分配策略

Python 使用分配器管理內存，以減少因頻繁分配和釋放內存導致的碎片化。當需要擴展列表容量時，會預先分配更多的空間，以容納未來可能添加的元素。這種策略被稱為“緩沖增長”，在減少內存操作次數的同時，提供了較好的性能。

時間復雜度

• 索引和更新操作：由于列表底層是數組，這些操作的時間復雜度為 (O(1))。
• 添加元素：如果沒有達到當前容量，添加操作（append）的時間復雜度為 (O(1))。如果需要擴展容量，時間復雜度為攤銷的 (O(1))。
• 刪除元素：刪除操作（pop）的時間復雜度為 (O(1))，如果刪除的是最后一個元素。如果是刪除中間元素，則時間復雜度為 (O(n))，因為需要移動后續元素。

優缺點

• 優點：
  • 支持隨機訪問，時間復雜度為 (O(1))。
  • 動態調整大小，使用方便。
• 缺點：
  • 由于需要預留額外空間，可能會浪費一些內存。
  • 在需要頻繁擴展容量時，會有一定的性能開銷。

其他特性

• 異質性：列表可以存儲不同類型的對象。
• 嵌套：列表可以包含其他列表（嵌套列表）。
• 切片：支持切片操作，可以方便地訪問部分列表。

實現細節

在 CPython 實現中，列表的底層結構如下所示：

typedef struct {PyObject_VAR_HEADPyObject **ob_item;Py_ssize_t allocated;
} PyListObject;

• ob_item 是一個指向元素數組的指針。
• allocated 表示已分配的數組容量。

總結起來，Python 列表的底層實現基于動態數組，結合了高效的隨機訪問和動態擴展的優點，但也帶來了內存管理和擴展時的性能開銷。了解這些細節可以幫助我們在使用列表時做出更優化的選擇。

數據結構時間復雜度是什么