разница list и array

#массивы #list #memory #data_structures

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

    

Ответы

Ответ 1

Строго говоря, связный список и массив - это различные структуры данных, которые
не привязаны к конкретному языку программирования.

Массив

Массив - это совокупность однотипных данных, расположенных непрерывно в памяти. Доступ
к элементу осуществляется по индексу за 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 - аналогично.


Ответ 2

Нельзя сказать что есть какая-то разница независимо от языка программирования, так
как автор каждого языка может определить эти слова так, как хочет.

Тем не менее, как мне кажется, разница между коллекциями список (list), массив (array)
и кортеж (tuple) заключается в следующих характеристиках:


Фиксированность размера - если размер коллекции фиксирован, то нельзя добавить или
удалить элементы динамическим образом:

int[] x = new int[2];
x[0] = 50;
x[1] = 45;
x[2] = 40; // скорее всего тут будет ошибка или неопределённое поведение


А если размер не фиксирован, можно добавить элементы динамическим образом:

List x = new List();
x.add(50);
x.add(45);
x.add(40);

Изменчивость данных - если коллекция изменяемая, то можно изменить данные после создания,
а если неизменяемая, то нет.


Конкретная разница:


Размер фиксирован, изменяемый: массив (array)
Размер фиксирован, неизменяемый: кортеж (tuple)
Размер не фиксирован, изменяемый: список (list)
Размер не фиксирован, неизменяемый: неизменяемый список (immutable list)


По поводу памяти и скорости: это точно зависит от языка и конкретного структура.
Например, сложность доступа к элементу по индексу в списке может быть O(1) (например
C# List), O(log(n)) (например куча), или O(n) (например связный список).