ilyachalov (ilyachalov) wrote,
ilyachalov
ilyachalov

Categories:

Учебник по JavaScript: структуры данных

Обычно учебники по языкам программирования касаются структур данных и алгоритмов работы со структурами данных только косвенно, чтобы показать, что язык умеет работать со структурами данных. Из учебника по языку программирования читатель обычно может узнать лишь о базовых приемах создания и работы с простейшими структурами данных.

Поэтому существует отдельная научная дисциплина, не завязанная на какой-то конкретный язык программирования, которая называется «Структуры данных и алгоритмы» или «Алгоритмы и структуры данных» или еще как-то похоже. Под «алгоритмами» в данном случае подразумеваются алгоритмы работы со структурами данных (алгоритмы создания и удаления элементов, поиска, обхода структуры данных и тому подобное).

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

В языке JavaScript, как я понимаю, кроме примитивных типов данных (типа строки или числа) всё остальное реализовано через объекты. Например, функции и массивы тоже являются объектами.

Структуры данных, в частности, делятся на линейные (их можно представить в виде одной линии) и нелинейные (ветвящиеся). Линейные — это, например, одномерные массивы или линейные односвязные списки. Нелинейные — это, например, деревья.

Особенность массивов (и не только одномерных) в том, что в них, как я понимаю, элементы с данными хранятся в памяти рядом друг с другом, впритык, поэтому в массивах нет необходимости в связях между элементами. Это одна из самых простых для понимания структур данных, поэтому массивы подробно разбираются в учебниках по языкам программирования. В обсуждаемом учебнике о массивах можно подробно прочесть в разделе «Типы данных» первой части.


Массивы разных размерностей

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

Для реализации односвязных списков уже требуется как-то реализовать «связи» между элементами данных, потому что элементы данных списка могут храниться в памяти в разных местах, не рядом друг с другом, не впритык. Узел односвязного списка обычно состоит из двух частей: элемента данных (или просто «данных») и связи со следующим узлом в списке.


Линейный односвязный список

На этой иллюстрации изображен линейный односвязный список из пяти элементов. Каждый элемент состоит из двух частей: «д» — данные, «с» — ссылка на следующий в списке элемент. Ссылку на первый элемент (на схеме она обозначена словом «начало») в программе можно сохранить в переменную list (что по-русски значит «список»), она будет представлять список. Ссылка из последнего элемента хранит значение null, то есть никуда не указывает.

Массивы и односвязные списки взаимно дополняют друг друга. У каждой из этих структур данных есть свои плюсы и минусы, при этом то, в чем, например, массив силён, в этом односвязный список слаб и наоборот. Например, для массива операция вставки элемента данных в начало или середину очень затратна по времени (потому что приходится сдвигать часть элементов, чтобы вставить новый); для односвязного списка же вставка нового элемента данных в начало или середину списка не требует сдвига других элементов, достаточно изменить две связи — от предыдущего элемента к вставляемому, и от вставляемого элемента — к следующему. Обратный пример: в массиве получение данных из элемента, находящегося в середине массива (также, как и любого другого) — это быстрая операция, а в односвязном списке для получения данных из элемента, находящегося в середине списка, требуется сначала перейти к этому элементу по связям от начального узла списка, что занимает сравнительно много времени.

Как реализуются связи между элементами данных в структурах данных? В языке программирования C++, например, для этого используются указатели (по-английски «pointer») или ссылки (по-английски «reference»). Разница между этими понятиями для данного поста несущественна, кому интересно, можно приобщиться к разбору этой разницы по следующим ссылкам на статьи в википедии:

https://ru.wikipedia.org/wiki/Ссылка_(программирование)
https://en.wikipedia.org/wiki/Reference_(computer_science)
https://ru.wikipedia.org/wiki/Указатель_(тип_данных)
https://en.wikipedia.org/wiki/Pointer_(computer_programming)

Суть в том, как я понимаю, что указатель (или ссылка) — это переменная, которая содержит адрес в памяти. Таким образом, в языке C++ узел списка содержит элемент данных и ссылку (указатель) на следующий узел в списке. Наличие связи между элементами позволяет хранить узлы одного и того же односвязного списка в разных местах памяти.

А как односвязный список реализован в языке JavaScript, если в нем нет такого типа данных, как «указатель»? На самом деле, такого типа нет явно, но он есть косвенно. Например:
let elem = 3;      // примитивный тип данных
let elem2 = elem;  // копирование значения
elem2 = 5;
console.log(elem); // 3

let arr = [ ];     // массив
let arr2 = arr;    // копирование ссылки
arr2.push(5);
console.log(arr);  // [5]

let obj = { };     // объект
let obj2 = obj;    // копирование ссылки
obj2.num = 5;
console.log(obj);  // {num: 5}

В этом коде рассмотрено три случая: случай с примитивным типом данных (числом), случай с массивом и случай с объектом. В принципе, массив в языке JavaScript — это тоже объект.

Как видно из этого примера, в случае примитивных типов данных в языке JavaScript при копировании одной переменной elem в другую elem2 копируется значение переменной. В случае же массива или объекта при копировании одной переменной в другую копируется не значение (сам массив или сам объект), а лишь ссылка на массив или объект.

В результате в случае примитивных типов данных мы получили две самостоятельные переменные, изменение одной из которых не влияет на состояние другой. В случае массива или объекта изменение одной переменной приводит к изменению другой, потому что обе переменные ссылаются на один и тот же массив (или объект). Об этом подробно рассказано в подразделе 4.2 «Копирование объектов и ссылки» учебника.

Во второй части подраздела 6.1 «Рекурсия и стек» учебника было показано, как в языке JavaScript можно с помощью объектов реализовать линейный односвязный список. Например:
let list = {
    data: 1,
    next: {
        data: 2,
        next: {
            data: 3,
            next: {
                data: 4,
                next: null
            }
        }
    }
};

В этом линейном односвязном списке содержится четыре узла. Каждый узел состоит из двух частей: данных (в этом случае данные представляют собой число) и ссылки на следующий узел. Как можно понять из изложенного ранее, в переменной list содержится ссылка на объект, а не сам объект. То же самое верно для каждого свойства next каждого из объектов. Каждое свойство next тоже содержит ссылку на объект, а не сам объект.
Tags: Образование, Программирование
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments