Является ли список массивом?

Question

[zlodiak]

Скажите пожалуйста правильно ли я понимаю суть массивов и связных списков. Если можно прокомментируйте кратко мои мысли:

1. в python встроенный тип list является массивом. Это значит, что в памяти ячейки списка располагаются подряд

2. с таким типом расположения связаны некоторые неудобства. Например, если список станет увеличится, то, возможно, системе придётся вместо добавления очередного элемента выбрать новую свободную область в памяти и перестроить в неё весь список

3. чтобы реализовать связный список нужно писать код самому. Например такой.

4. чтобы реализовать двусвязный список нужно тоже писать код самому.

5. встроенных аналогов списков из пунктов 3 и 4 нет.

6. в стандартной библиотеке аналогов списков из пунктов 3 и 4 нет.

Answer 1

[devalone]

В питоне в списке хранятся ссылки на элементы, т.е. создание нового куска памяти не так затратно

Comments

[zlodiak]

devalone
Я правильно понимаю, что список в python похож на словарь? Роль ключей выполняют ссылки, про которые вы написали, а роль значений - элементы списка.

И, вероятно, в основе такой модели лежит хеш-таблица

[Roman K]

zlodiak, в списке питона под капотом массив указателей на PyObject. Массив — это значит, что элементы находятся последовательно в ОЗУ один за другим, без пробелов. Хэш-таблица — это тоже массив, но разреженный. Элементы массива (если они не пусты) — структуры, где есть ключ и указатель на PyObject. В целом, наверное, можно сказать, что они похожи. В конечном этоге из ключа генерируется индекс в массиве (хэш-таблице).

[devalone]

zlodiak, нет, там не хеш таблица, а обычный массив указателей, хеш таблица используется для словаря(dict)

Answer 2

[CrazyElf]

Конечно же есть стандартный модуль с такими свойствами: https://docs.python.org/3/library/collections.html...

Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

Comments

[zlodiak]

CrazyElf
но это же очередь. Разве она имеет что-то общее в связными и двусвязными списками?

[Roman K]

zlodiak, ты не поверишь, но двунаправленная очередь — это и есть двусвязный список.

[CrazyElf]

zlodiak, Вопрос в том, что ты хочешь от связного списка. Судя по вопросам, тебя беспокоили затраты на добавление в него элементов. deque предназначена именно для быстрого добавления и удаления элементов с любого её конца.