Python 목록의 기본 데이터 구조는 무엇입니까?

Python 목록의 기본 데이터 구조는 무엇입니까?

---

Python의 내장 목록 데이터 유형을 구현하는 데 사용되는 일반적인 기본 데이터 구조는 무엇입니까?

---

목록 객체는 배열로 구현됩니다. 빠른 고정 길이 작업에 최적화되어 있으며 기본 데이터 표현의 크기와 위치를 모두 변경하는 pop (0) 및 insert (0, v) 작업에 대해 O (n) 메모리 이동 비용이 발생합니다.

참조 : http://docs.python.org/library/collections.html#collections.deque

Btw, 데이터 구조에 대한 Python 자습서에서 pop (0)을 사용하여 대기열을 시뮬레이션 할 것을 권장하지만 O (n) 또는 deque 옵션을 언급하지 않는 것이 흥미 롭습니다.

http://docs.python.org/tutorial/datastructures.html#using-lists-as-queues

---

CPython :

typedef struct {
    PyObject_VAR_HEAD
    /* 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
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

다음 줄에서 볼 수 있듯이 목록은에 대한 포인터 배열로 선언됩니다 PyObjects.

PyObject **ob_item;

---

에서 자이 썬 구현 , 그것은이다 ArrayList<PyObject>.

참고 URL : https://stackoverflow.com/questions/914233/what-is-the-underlying-data-structure-for-python-lists