Arhn - архитектура программирования

Массив Javascript в связанный список и понимание памяти

У меня есть следующий код для преобразования массива в связанный список:

function arrayToList(array) {
  var list = null;
  for (var i = array.length - 1; i >= 0; i--)
    list = {value: array[i], rest: list};
  return list;
}

Этот код был дан мне, поэтому я пытаюсь его понять. Я получаю базовую интуицию/суть этого (я работал со связанными списками, уже взял класс структур данных на Java, понял основы указателей на C) и т. д.

Однако что-то не щелкает, и я хочу убедиться, что вижу, что происходит. Итак, давайте представим, что мы создали переменную list, ссылающуюся на область памяти, значение которой объявлено как null. Предположим, что этот «адрес памяти» равен 0001:

0001: [null] список

Так что же происходит после первой итерации нашего цикла? Это моя интерпретация. список теперь относится к новому фрагменту пространства. То есть, переопределив list в строке:

list = {value: array[i], rest: list};

мы создали «новый» объект, занимающий новое пространство. Итак, теперь у нас может быть:

0001: [null]
0002: [массив[i]] list.value
0003: [null] list.rest

(Я не совсем уверен, куда именно «указывает» list сейчас, предполагая, что 0002, хотя концептуально я думаю, что это спорный вопрос в Javascript)

Верно ли это понимание? Я привык думать о структурах данных а-ля Java, где такой объект, как list, имеет уже определенные блоки пространства каждый раз, когда создается экземпляр. Я работал с Python, но раньше не создавал с ним связанные списки. Исходя из этого, я предполагаю, что такой язык, как Javascript, является гибким в том смысле, что вы можете просто иметь переменную равной нулю, затем ссылаться на хеш, затем, когда вы устанавливаете ее как другой хеш, он создает «новый» хэш и т. д.

Спасибо!

javascript memory linked-list
20.09.2014

Ответы:


1

Во-первых, в JavaScript нет собственной структуры данных, которая представляет собой связанный список, у нас есть объекты и у нас есть массивы (которые, как ни странно, являются частными случаями Objects).

Показанный здесь код создает объекты, используя литералы объектов.

Кажется, это больше вопрос об использовании одного и того же идентификатора с обеих сторон =

Переменная в правой части элемента = будет указывать на объект до того, как она изменится в левой части.

// say we have
var foo = {};

// Then
foo = {"fizz": foo};

эквивалентно наличию

var foo = {};

var t = foo;
foo = {"fizz": t}; // `foo` becomes a new object in a different memory location
// that points to `t`s target, meaning that `t` is referencable through `foo` and so
// won't be GC'd if the identifier `t` is cleaned up from namespace

Вы можете найти это нелогичным из-за обычного порядка выполнения слева направо, но если подумать, вы не можете "установить", пока не знаете, что установить, поэтому пока RHS не завершится, вы не сможете обновить идентификатор из LHS

Итак, если вы зациклите это, вы можете получить такую ​​​​структуру, как

foo;           // Object @ e.g. 0x30
foo.fizz;      // Object @ e.g. 0x20
foo.fizz.fizz; // Object @ e.g. 0x10
foo.fizz.fizz.fizz; // undefined

Где каждый Объект имеет свою собственную хеш-карту, которая указывает на предыдущую (при поиске fizz), пока не закончатся Объекты, и ни одна из памяти не получает GCd, потому что каждая из них по-прежнему доступна. Как среда на самом деле реализует это, не указано в спецификации, поэтому это не требование, чтобы местоположение объекта в памяти никогда не перемещалось, но его расположение в памяти это не то, что вы можете видеть или с чем взаимодействовать (все это делается за кулисами). Следовательно, для всех целей в среде вы можете думать о ячейках памяти как о статических.

20.09.2014
  • Я думаю, что OP обсуждает, как связанный список хранится в памяти в JavaScript, а не как объекты устанавливаются в этом абстрактном слое. 20.09.2014
  • Вы говорите, что код OP на самом деле создает linked list? 20.09.2014
    • Новые материалы
    Коллекции публикаций по глубокому обучению
    Последние пару месяцев я создавал коллекции последних академических публикаций по различным подполям глубокого обучения в моем блоге https://amundtveit.com - эта публикация дает обзор 25..
    Представляем: Pepita
    Фреймворк JavaScript с открытым исходным кодом Я знаю, что недостатка в фреймворках JavaScript нет. Но я просто не мог остановиться. Я хотел написать что-то сам, со своими собственными..
    Советы по коду Laravel #2
    1-) Найти // You can specify the columns you need // in when you use the find method on a model User::find(‘id’, [‘email’,’name’]); // You can increment or decrement // a field in..
    Работа с временными рядами спутниковых изображений, часть 3 (аналитика данных)
    Анализ временных рядов спутниковых изображений для данных наблюдений за большой Землей (arXiv) Автор: Рольф Симоэс , Жильберто Камара , Жильберто Кейрос , Фелипе Соуза , Педро Р. Андраде ,..
    3 способа решить квадратное уравнение (3-й мой любимый) -
    1. Методом факторизации — 2. Используя квадратичную формулу — 3. Заполнив квадрат — Давайте поймем это, решив это простое уравнение: Мы пытаемся сделать LHS,..
    Создание VR-миров с A-Frame
    Виртуальная реальность (и дополненная реальность) стали главными модными терминами в образовательных технологиях. С недорогими VR-гарнитурами, такими как Google Cardboard , и использованием..
    Демистификация рекурсии
    КОДЕКС Демистификация рекурсии Упрощенная концепция ошеломляющей О чем весь этот шум? Рекурсия, кажется, единственная тема, от которой у каждого начинающего студента-информатика..
    © 2024 arhn.ru, Arhn - архитектура программирования