Поколение Python 🐍

Друзья, в этом посте расскажу о том, как реализован встроенный тип list (список).



Массив — это фундаментальная структура данных в информатике. В массиве хранятся элементы одинакового размера, которые расположены в памяти друг за другом, без пропусков. А раз элементы имеют одинаковый размер и идут подряд, то получить элемент массива по определенному индексу совсем несложно: достаточно знать адрес самого первого элемента массива и сдвиг, то есть индекс нужного элемента. Важно также понимать, что длина массива всегда фиксирована.



Списки (тип list) в Python реализованы на базе массива, хранящего ссылки на объекты. По сути, список (тип list) — это динамический массив, или вектор, как его еще называют в других языках программирования.



Использование в качестве опорной структуры данных массива позволяет быстро, то есть за константное время O(1), обращаться к элементам списка по их индексу. При этом обратная задача — поиск индекса элемента по его значению (списочный метод index()) — выполняется за линейное время O(n), где n — длина списка. Если данных много и по ним нужно часто осуществлять поиск, то список — не самая подходящая структура данных.



Итог. Списки в Python (тип list) — это динамические массивы, то есть массивы переменной длины. Python сам решает, когда и насколько необходимо изменить размер массива, лежащего в основе списка. Кратко о реализации типа list можно почитать в официальной документации по ссылке.



Важно! Не путайте списки в Python (тип list) и структуру данных "связный список". Несмотря на одинаковое название, это совсем разные вещи.



Реализация типа list на языке С доступна по ссылке.



#полезныйматериал #python #список #list #массив