IK
А почему в питоне добавление в конец списка за О(1), добавить элемент начало за О(n)?
Потому что по любому надо будет сдвигать все вправо
Size: a a a
2020 November 29
V
Значит 1 указатель на начало?
IK
Значит 1 указатель на начало?
Чо
IK
Потому что по любому надо будет сдвигать все вправо
Хотя и добавление в список иногда может быть также медленным
A
А почему в питоне добавление в конец списка за О(1), добавить элемент начало за О(n)?
О(1) - это время, О(n) - зависит от кол-ва элементов в списке
IK
Когда запас кончается
V
Можно 2 указателя использовать, на начало и конец
V
Я знаю про О большое
A
по умолчанию в конец списка добавление идет и программе не нужно проходить весь список, чтобы добавить элемент
A
при раскладе когда в начало добавляешь, считай, что у всех элементов индекс меняется на +1
V
А где гарантия что следующие элементы памяти не забиты? Механизм резервации памяти значит присутствует
A
автоматическое расширение иде
V
Можно длину менять и среднею точку
IK
А где гарантия что следующие элементы памяти не забиты? Механизм резервации памяти значит присутствует
Если запас кончается происходит realloc
V
То есть питон выделяет сразу размер до пересчета памяти? А когда кончилась выделяет ещё остравок памяти？
A
ну типа да, зачем для 1-2 файлов выделять большой объем памяти сразу?)
V
да это я о том, что можно просто сразу выделить 2 остравка для положительных индексов и отрицательных. То есть кончились положительные, значит добавить место положительному индексу. Кончились отрицательные, добавить им тоже остравок
V
Это позволит за О(1) в обе стороны
A
ниче не понял
V
А все же, список это стек？