Ответ 1
Python использует линейный макет списка в памяти, так что индексирование выполняется быстро (O (1)).
Использует ли Python связанные списки для списков? Почему вставить медленно?
Просто изучать Python. Чтение официальных учебных пособий. Я натолкнулся на это:
В то время как добавления и всплывающие окна с конца списка бывают быстрыми, выполнение вставок или всплывающих окон с начала списка происходит медленно (потому что все остальные элементы должны быть сдвинуты на один).
Я бы предположил, что зрелый язык, такой как Python, будет иметь всевозможные оптимизации, поэтому почему Python [кажется] использует связанные списки, чтобы вставки могли быть быстрыми?
Ответы
Ответ 2
Как уже указывал Грег Хьюджилл, списки python используют непрерывные блоки памяти для быстрой индексации. Вы можете использовать deque, если хотите характеристики производительности связанного списка. Но ваша первоначальная предпосылка кажется мне неправильной. Индексированная вставка в середину (стандартного) связанного списка также медленная.
Ответ 3
Что Python называет "списками", на самом деле не связаны списками; они больше похожи на массивы. См. Запись из глоссария Python, а также Как вы создаете массив в Python? из Python FAQ.
Ответ 4
list реализуется как аррайалист. Если вы хотите вставить часто, вы можете использовать deque (но обратите внимание, что обход середины дорог).
В качестве альтернативы вы можете использовать кучу. Это все, если вы нашли время посмотреть документы.
Ответ 5
Списки Python реализуются с использованием массива ссылок с изменяемыми размерами для других объектов. Это обеспечивает O (1) поиск по сравнению с O (n) поиском реализации связанного списка.
Как вы упомянули, эта реализация делает вставки в начало или середину списка Python медленными, потому что каждый элемент в массиве справа от точки вставки должен быть смещен над одним элементом. Кроме того, иногда массив должен быть изменен для размещения большего количества элементов. Для вставки в связанный список вам все равно потребуется время O (n), чтобы найти место, в которое вы будете вставлять, но сама фактическая вставка будет O (1), так как вам нужно немедленно изменить ссылки в узлах до и после точки вставки (предполагая двусвязный список).
Поэтому решение сделать списки Python использует динамические массивы, а не связанные списки не имеет ничего общего с "зрелостью" реализации языка. Существуют просто компромиссы между различными структурами данных, и разработчики Python решили, что динамические массивы являются наилучшим вариантом в целом. Возможно, они предположили, что индексирование списка является более распространенным, чем вставка данных в него, что позволяет сделать динамические массивы лучшим выбором в этом случае.
См. следующую таблицу в статье wikipedia Dynamic Array для сравнения различных характеристик производительности структуры данных: