Структуры данных и алгоритмы
К настоящему времени мы привыкли к массивам; мы знаем, где они быстрые, а где медленные. Теперь мы углубимся в их внутреннюю работу и научимся ее строить.
Изучение того, как создать массив, является важной основой, если мы хотим понимать вещи на фундаментальном уровне.
Мы будем использовать синтаксис класса в javascript для его создания, хотя обычно с javascript мы можем просто создайте массив, как показано ниже:
const a = [];
Но давайте посмотрим, сможем ли мы построить свои собственные.
Что мы знаем о структурах данных?
Мы знаем, что это вещи, которые мы можем построить с нуля; это означает, что мы можем создать любую структуру данных, какую захотим.
Наиболее широко используемые структуры данных хорошо известны и уже реализованы, потому что они очень полезны. Но вы можете построить любую структуру данных с нуля, и большинство структур данных построено поверх других структур данных.
Строим наш массив
Массивы в javascript - это просто объекты с ключами на основе целых чисел, которые действуют как индексы, и это то, что мы собираемся создать.
Массивы в javascript - это просто объекты с ключами на основе целых чисел, которые действуют как индексы.
Итак, мы собираемся начать с создания класса, который мы назовем MyArray. Внутри MyArray у нас будет конструктор, который является начальной функцией, которая будет запускаться при создании MyArray. Этот конструктор будет иметь две точки данных:
1. Свойство length - с помощью массивов мы можем определять длину массива. У нас будет начальная длина, равная нулю, показывающая, сколько элементов имеет массив.
2. Данные - это будет пустой объект.
Метод get ()
Доступ к данным - самое важное действие в массиве. Итак, давайте создадим метод get (). Метод get () принимает индекс для извлечения данных из памяти.
Итак, мы просто return this.data в требуемом индексе.
this.data просто ссылаемся на данные, которые мы создали в конструкторе.
Посмотрим, как это будет работать. Чтобы создать новый MyArray, все, что нам нужно сделать, это сказать const newArray = new MyArray . Мы используем ключевое слово new в JavaScript для создания экземпляра этого или создания копии класса.
Итак, теперь, если я do console.log(newArray) , я получаю myArray, у которого свойство length равно 0, а данные пусты.
Если я сделаю console.log(newArray.get(0)), я получу undefined. Ну, потому что в этом объекте ничего нет - у нас нет предметов. Javascript автоматически имеет тип undefined, пока ничего нет.
Метод push ()
Давайте добавим наш следующий метод - push (). Метод push () добавляет что-то в конец массива.
Требуется элемент, который мы ему дадим, и мы просто добавим этот элемент к объекту данных; он добавит его к длине нашего предмета.
Поскольку у нас нет элементов, а длина равна 0, это добавит данные в индекс 0. Индекс 0 теперь содержит элемент, и, поскольку мы хотим продолжать добавлять элементы, мы скажем this.length ++. Теперь наш массив имеет длину 1 вместо 0.
Итак, в следующий раз, когда мы запустим метод push (), this.length будет 1, а новый элемент будет добавлен с индексом 1. И давайте просто вернемся. this.length на данный момент, потому что типичный метод push () в javascript обычно возвращает длину массива. Давайте запустим это и посмотрим, что произойдет. Давайте push(‘hi’) .
Мы видим, что у меня есть M yArray с длиной 1, а data имеет свойство 0 hi.
Что, если мы добавим еще что-нибудь - займемся newArray.push(‘there’) . Если я запустил это, у меня будет длина 2. Теперь при индексе 0 это hi, а при индексе 1 там.
Команда pop ()
Команда pop () удаляет последний элемент из массива. Этот метод ничего не получает - нам не нужно передавать ему параметр. Все, что нам нужно сделать, это удалить последний элемент в массиве.
Мы можем просто иметь переменную lastItem. Допустим, наш lastItem захватывает последний элемент в нашем объекте данных. Так что это будет просто this.data[this.index-1] . Затем мы можем использовать ключевое слово delete в javascript и сказать delete this.data[this.length-1]
… Чтобы просто удалить последний элемент, и нам нужно уменьшить длину нашего массива на единицу. Итак this.length-- . И, наконец, мы можем просто вернуть удаленный элемент.
Итак, теперь, если я запустил новый Array.pop ();
Мы видим, что там был удален! Теперь у нас есть длина 1, всего hi. Если я снова запустил pop ()
Я вижу, что у меня длина 0; привет тоже был удален!
Метод delete ()
Метод delete () покажет нам, почему некоторые операции с массивами выполняются O (n). Требуется индекс элемента, который мы хотим удалить.
Здесь нам нужно будет создать элемент const. Итак, мы собираемся создать ссылку на this.data[index] как ссылку на элемент, который мы хотим удалить.
Но как мы собираемся удалить это? Помните, что в массиве нам нужно удалить элемент, а затем сдвинуть индекс всех других типов данных на 1.
Итак, давайте добавим еще одну функцию, которая выполняет перенос данных за нас. Я собираюсь создать новый метод, и мы сделаем это в javascript, используя ключевое слово this. Итак this.shiftItems(index) ; этот метод принимает индекс, который мы получили при удалении.
Теперь с помощью метода shiftItems нам нужно будет перебрать элементы, которые должны сигнализировать о том, что это операция O (n). Мы собираемся переместить элементы - не все, а только там, где начинается указатель. Мы видим, что наш i должен быть меньше this.length-1. И мы собираемся увеличивать i на единицу каждый раз в этом цикле.
В этом цикле все, что мы собираемся сделать, это сказать, что this.data[i] будет равно this.data[i+1] . Мы говорим, что начинаем с индекса, с которого хотим начать, и удаляем, и перебираем его до конца. И в этом цикле я хочу, чтобы вы взяли каждый элемент данных, которые у нас есть, и вместо того, что было раньше, сдвиньте его на 1. Итак, мы смещаем элементы влево на 1.
Теперь здесь есть проблема, потому что теперь будет существовать самый последний элемент в массиве, равный this.data[this.length-1] . Мы переставили все по одному, но так и не коснулись самого последнего элемента. Мы остановились, когда i меньше this.length-1.
Я получаю привет. там удаляется. Но тогда у меня есть friend с индексом 2. Итак, смещение работает, но у нас все еще есть friend, потому что мы никогда его не удаляли. Мы переместили все еще раз, но так и не коснулись последнего индекса.
Итак, все, что нам нужно сделать, чтобы избавиться от этого, - это использовать ключевое слово delete для удаления последнего элемента и, очевидно, уменьшить нашу длину, потому что мы просто удаляем элемент. Мы можем сделать this.length-- .
К настоящему времени мы должны понимать, как работают массивы и как они реализованы. У нас есть простые команды O (1), которые работают быстро. Но как только нам нужно начать смещение индексов и что-то изменить, мы должны перебрать вещи, которые сделают это O (n) или линейным временем.
