Вновь о питоновском аналоге массива
Из темы http://python.su/forum/viewtopic.php?id=1792 я вынес точку зрения, что аналогом массива считается список (list).
Но просветите, пожалуйста, кто-нибудь, как организован этот самый list внутри?
Как связный список с последовательным доступом, или как красно-чёрное дерево, или на самом деле список именно как массив и организован, и т.д.?
Какова ассимпотическая оценка операции “квадратные скобки”? Например, чтобы фрагмент кода с при i==17127 нашёл этот самый элемент №17127, будут просматриваться все предыдущие 17126, или без каких-либо просмотров будет выбран сразу нужный, или просмотр будет, но речь идёт не о десятках тысяч узлов, а о просто десятках?
Какова ассимптотическая оценка операции del a, т.е “удалить несколько элементов из НАЧАЛА списка”? То есть, будут просто переброшены несколько указателей, или весь хвост списка будет реально перемещаться из одного участка памяти в другой, или произойдёт максимум несколько поворотов дерева?
Особо интересует ситуация, когда действие del a придётся выполнять многократно, для изначально очень большого списка и относительно мАлых i.
Я новичок в python, но ВОВСЕ НЕ новичок в программировании вообще (особенно алгоритмике). Прошу отвечать, исходя из этого – не грузить сложными узко-питоновскими заморочками, но и не тратить время на элементарные вещи, общие для всех языков программирования.