Я новичок в Javascript и замечаю, что вам не нужно указывать размер массива и часто видеть, как люди динамически создают массивы по одному элементу во времени. Это будет огромной проблемой производительности на других языках, так как вам будет необходимо перераспределять память для массива по мере увеличения размера.
Это не проблема в JavaScript? Если да, то есть ли структура списка?
Скорее всего, это зависит от того, какой механизм JavaScript вы используете.
Internet Explorer использует сочетание разреженных массивов и плотных массивов, чтобы сделать эту работу. Некоторые из более подробных подробностей объясняются здесь: http://blogs.msdn.com/b/jscript/archive/2008/04/08/performance-optimization-of-arrays-part-ii.aspx.
Маски Javascript обычно реализуются как hashmaps (как и объекты Javascript) с одной добавленной особенностью: есть атрибут length, который на один выше максимального положительного целого числа, которое использовалось в качестве ключа. Ничто не мешает вам использовать строки, числа с плавающей запятой, даже отрицательные числа в качестве ключей. Ничего, кроме здравого смысла.
Что касается динамических языков, то они динамичны. Так же, как ArrayList в Java или массивы в Perl, PHP и Python, Array в JavaScript выделяет определенный объем памяти, а когда он становится слишком большим, язык автоматически добавляется к объекту. Является ли он столь же эффективным, как С++ или даже Java? Нет (С++ может запускать круги вокруг даже лучших реализаций JS), но люди не строят Quake в JS (пока).
На самом деле лучше думать о них как о HashMaps с некоторыми специализированными методами тоже в любом случае - в конце концов, это действительно: var a = []; a['cat']='meow';.
Нет.
Какие массивы JavaScript есть и нет, определяется спецификацией конкретного языка 15.4. Array определяется в терминах операций, которые он предоставляет не в деталях реализации макета памяти какой-либо конкретной структуры данных.
Может ли Array быть реализован поверх связанного списка? Да. Это может сделать определенные операции быстрее, такие как shift и unshift эффективными, но Array также часто обращается к индексу, который неэффективен со связанными списками.
Также можно получить лучшее из обоих миров без связанных списков. Контекстные структуры данных памяти, такие как круговые очереди имеют как эффективную вставку/удаление из фронта, так и эффективный произвольный доступ.
На практике большинство интерпретаторов оптимизируют плотные массивы, используя структуру данных, основанную на масштабируемом или перераспределяемом массиве, похожем на С++ vector или Java ArrayList.
Они больше похожи на пользовательские объекты, которые используют свойства в качестве индексов. Пример:
var a = { "1": 1, "2": 2};
a.length = 2;
for(var i=0;i<a.length;i++)
console.log(a[i]);
a будет вести себя почти как массив, и вы также можете вызывать функции из массива Array.prototype на нем.
Массивы Javascript не являются истинными массивами, как на языках C/С++ или других языках. Поэтому они не так эффективны, но они, возможно, проще в использовании и не выходят за пределы исключений.