разница list и array

Можно ли говорить об общих различиях между типами данных list и array независимо от языка программирования? В частности, по способу доступа к элементам? В Python что является "истинным" списком -- list или tuple? Какая из этих структур требует больше памяти и при каких условиях?

Ответ

Строго говоря, связный список и массив - это различные структуры данных, которые не привязаны к конкретному языку программирования.
Массив
Массив - это совокупность однотипных данных, расположенных непрерывно в памяти. Доступ к элементу осуществляется по индексу за O(1) - мы обращаемся непосредственно к нужному участку памяти.
Связанный список
Доступ к элементу в связном списке в среднем занимает O(N) путем перебора элементов в поисках нужного. Способы доступа к элементам отличаются по реализации и от языка программирования. Например, на Java в стандартном классе LinkedList в зависимости от ситуации проход элементов может начинаться как с начала, так и с конца списка. И поиск элемента может осуществляться как по индексу, так и по сравнению элементов.
Связный список требует больших расходов памяти при прочих равных условиях за счет хранения указателей на следующий/предыдущий элементы и особенностей внутренней реализации.
Что касается Python: согласно документации
Internally, a list is represented as an array; the largest costs come from growing beyond the current allocation size (because everything must move), or from inserting or deleting somewhere near the beginning (because everything after that must move).
Как видим, внутренне list представляет собой массив, для tuple - аналогично.