8 распространенных структур данных на примере JavaScript
Звучит ли это знакомо: «Я начал заниматься веб разработкой после прохождения курсов»?
Возможно, вы хотите улучшить свои знания основ информатики в части структур данных и алгоритмов. Сегодня мы поговорим о некоторых наиболее распространенных структурах данных на примере JS.
1. Стек (вызовов) (Stack)
Стек следует принципу LIFO (Last In First Out — последним вошел, первым вышел). Если вы сложили книги друг на друга, и захотели взять самую нижнюю книгу, то сначала возьмете верхнюю, затем следующую и т.д. Кнопка «Назад» в браузере позволяет перейти (вернуться) на предыдущую страницу.
Стек имеет следующие методы:
- push: добавить новый элемент
- pop: удалить верхний элемент, вернуть его
- peek: вернуть верхний элемент
- length: вернуть количество элементов в стеке
function Stack() < this.count = 0 this.storage = <>this.push = function(value) < this.storage[this.count] = value this.count++ >this.pop = function() < if (this.count === 0) return undefined this.count-- let result = this.storage[this.count] delete this.storage[this.count] return result >this.peek = function() < return this.storage[this.count - 1] >this.size = function() < return this.count >> 2. Очередь (кью) (Queue)
Очередь напоминает стек. Разница состоит в том, что очередь следует принципу FIFO (First In First Out — первым вошел, первым вышел). Когда вы стоите в очереди, первый в ней всегда будет первым.
Очередь имеет следующие методы:
- enqueue: войти в очередь, добавить элемент в конец
- dequeue: покинуть очередь, удалить первый элемент и вернуть его
- front: получить первый элемент
- isEmpty: проверить, пуста ли очередь
- size: получить количество элементов в очереди
function Queue() < let collection = [] this.print = function() < console.log(collection) >this.enqueue = function(element) < collection.push(element) >this.dequeue = function() < return collection.shift() >this.front = function() < return collection[0] >this.isEmpty = function() < return collection.length === 0 >this.size = function() < return collection.length >> Порядок очередности (приоритет)
Очередь имеет продвинутую версию. Присвойте каждому элементу приоритет, и элементы будут отсортированы соответствующим образом:
function PriorityQueue() < . this.enqueue = function(element) < if (this.isEmpty()) < collection.push(element) >else < let added = false for (let i = 0; i < collection.length; i++) < if (element[1] < collection[i][1]) < collection.splice(i, 0, element) added = true break; >> if (!added) < collection.push(element) >> > > let pQ = new PriorityQueue() pQ.enqueue([gannicus, 3]) pQ.enqueue([spartacus, 1]) pQ.enqueue([crixus, 2]) pQ.enqueue([oenomaus, 4]) pQ.print() [ [spartacus, 1], [crixus, 2], [gannicus, 3], [oenomaus, 4] ] 3. Связный список (связанный, список узлов и ссылок или указателей) (Linked List)
Буквально, связный список — это цепочечная структура данных, где каждый узел состоит из двух частей: данных узла и указателя на следующий узел. Связный список и условный массив являются линейными структурами данных с сериализованным хранилищем. Отличия состоят в следующем:
| Критерий | Массив | Список |
|---|---|---|
| Выделение памяти | Статическое, происходит последовательно во время компиляции | Динамическое, происходит асинхронно во время запуска (выполнения) |
| Получение элементов | Поиск по индексу, высокая скорость | Поиск по всем узлам очереди, скорость менее высокая |
| Добавление/удаление элементов | В связи с последовательным и статическим распределением памяти скорость ниже | В связи с динамическим распределением памяти скорость выше |
| Структура | Одно или несколько направлений | Однонаправленный, двунаправленный или циклический |
Односвязный список имеет следующие методы:
- size: вернуть количество узлов
- head: вернуть первый элемент (head — голова)
- add: добавить элемент в конец (tail — хвост)
- remove: удалить несколько узлов
- indexOf: вернуть индекс узла
- elementAt: вернуть узел по индексу
- addAt: вставить узел в определенное место (по индексу)
- removeAt: удалить определенный узел (по индексу)
// узел function Node(element) < // данные this.element = element // указатель на следующий узел this.next = null >function LinkedList() < let length = 0 let head = null this.size = function() < return length >this.head = function() < return head >this.add = function(element) < let node = new Node(element) if (head === null) < head = node >else < let currentNode = head while (currentNode.next) < currentNode = currentNode.next >currentNode.next = node > length++ > this.remove = function(element) < let currentNode = head let previousNode if (currentNode.element !== element) < head = currentNode.next >else < while (currentNode.element !== element) < previousNode = currentNode currentNode = currentNode.next >previousNode.next = currentNode.next > length-- > this.isEmpty = function() < return length === 0 >this.indexOf = function(element) < let currentNode = head let index = -1 while (currentNode) < index++ if (currentNode.element === element) < return index >currentNode = currentNode.next > return -1 > this.elementAt = function(index) < let currentNode = head let count = 0 while (count < index) < count++ currentNode = currentNode.next >return currentNode.element > this.addAt = function(index, element) < let node = new Node(element) let currentNode = head let previousNode let currentIndex = 0 if (index >length) return false if (index === 0) < node.next = currentNode head = node >else < while (currentIndex < index) < currentIndex++ previousNode = currentNode currentNode = currentNode.next >node.next = currentNode previousNode.next = node > length++ > this.removeAt = function(index) < let currentNode = head let previousNode let currentIndex = 0 if (index < 0 || index >= length) return null if (index === 0) < head = currentIndex.next >else < while (currentIndex < index) < currentIndex++ previousNode = currentNode currentNode = currentNode.next >previousNode.next = currentNode.next > length-- return currentNode.element > > 4. Коллекция (значений) (Set)
Коллекция (множество) — одна из основных концепций математики: набор хорошо определенных и обособленных объектов. ES6 представил коллекцию, которая имеет некоторое сходство с массивом. Тем не менее, коллекция не допускает включения повторяющихся элементов и не содержит индексов.
Стандартная коллекция имеет следующие методы:
- values: вернуть все элементы в коллекции
- size: вернуть количество элементов
- has: проверить, имеется ли элемент в коллекции
- add: добавить элемент
- remove: удалить элемент
- union: вернуть область пересечения двух коллекций
- difference: вернуть отличия двух коллекций
- subset: проверить, является ли одна коллекция подмножеством другой
// дистанцируемся от Set в JS function MySet() < let collection = [] this.has = function(element) < return (collection.indexOf(element) !== -1) >this.values = function() < return collection >this.size = function() < return collection.length >this.add = function(element) < if (!this.has(element)) < collection.push(element) return true >return false > this.remove = function(element) < if (this.has(element)) < index = collection.indexOf(element) collection.splice(index, 1) return true >return false > this.union = function(otherSet) < let unionSet = new MySet() let firstSet = this.values() let secondSet = otherSet.values() firstSet.forEach(i =>unionSet.add(i)) secondSet.forEach(i => unionSet.add(i)) > this.intersection = function(otherSet) < let intersectionSet = new MySet() let firstSet = this.values() firstSet.forEach(function(e) < if (otherSet.has(e)) < intersectionSet.add(e) >>) return intersectionSet > this.difference = function(otherSet) < let differenceSet = new MySet() let firstSet = this.values() firstSet.forEach(function(e) < if (!otherSet.has(e)) < differenceSet.add(e) >>) return differenceSet > this.subset = function(otherSet) < lat firstSet = this.values() return firstSet.every(value =>otherSet.has(value)) > > 5. Хеш-таблица (таблица кэширования) (Hash Table)
Хеш-таблица — это структура данных, которая строится по принципу ключ-значение. Из-за высокой скорости поиска значений по ключам, она используется в таких структурах, как Map, Dictionary и Object. Как показано на рисунке, хеш-таблица имеет hash function, преобразующую ключи в список номеров, которые используются как имена (значения) ключей. Время поиска значения по ключу может достигать O(1). Одинаковые ключи должны возвращать одинаковые значения — в этом суть функции хэширования.
Хеш-таблица имеет следующие методы:
- add: добавить пару ключ/значение
- remove: удалить пару
- lookup: найти значение по ключу
function hash(string, max) < let hash = 0 for (let i = 0; i < string.length; i++) < hash += string.charCodeAt(i) >return hash % max > function HashTable() < let storage = [] const storageLimit = 4 this.add = function(key, value) < let index = hash(key, storageLimit) if (storage[index] === undefined) < storage[index] = [ [key, value] ] >else < let inserted = false for (let i = 0; i < storage[index].len; i++) < if (storage[index][i][0] === key) < storage[index][i][1] = value inserted = true >> if (inserted === false) < storage[index].push([key, value]) >> > this.remove = function(key) < let index = hash(key, storageLimit) if (storage[index].length === 1 && storage[index][0][0] === key) < delete storage[index] >else < for (let i = 0; i < storage[index]; i++) < if (storage[index][i][0] === key) < delete storage[index][i] >> > > this.lookup = function(key) < let index = hash(key, storageLimit) if (storage[index] === undefined) < return undefined >else < for (let i = 0; i < storage[index].length; i++) < if (storage[index][i][0] === key) < return storage[index][i][1] >> > > > 6. Дерево (Tree)
Древовидная структура — это многослойная (многоуровневая) структура. Это также нелинейная структура, в отличие от массива, стека и очереди. Данная структура очень эффективна в части добавления и поиска элементов. Вот некоторые концепции древовидной структуры:
- root: корневой элемент, не имеет «родителя»
- parent node: прямой узел верхнего слоя (уровня), может быть только одним
- child node: прямой узел (узлы) нижнего уровня, может быть несколько
- siblings: дочерние элементы одного родительского узла
- leaf: узел без «детей»
- Edge: ветка или ссылка (связь) между узлами
- Path: путь (совокупность ссылок) от начального узла до целевого элемента
- Height of Tree (высота дерева): количество ссылок самого длинного пути от определенного элемента до узла, не имеющего потомков
- Depth of Node (глубина узла): количество ссылок от корневого узла до определенного элемента
- Degree of Node: количество потомков
Методами данного дерева являются следующие:
- add: добавить узел
- findMin: получить минимальный узел
- findMax: получить максимальный узел
- find: найти определенный узел
- isPresent: проверить наличие определенного узла
- remove: удалить узел
class Node < constructor(data, left = null, right = null) < this.data = data this.left = left this.right = right >> class BST < constructor() < this.root = null >add(data) < const node = this.root if (node === null) < this.root = new Node(data) return >else < const searchTree = function(node) < if (data < node.data) < if (node.left === null) < node.left = new Node(data) return >else if (node.left !== null) < return searchTree(node.left) >> else if (data > node.data) < if (node.right === null) < node.right = new Node(data) return >else if (node.right !== null) < return searchTree(node.right) >> else < return null >> return searchTree(node) > > findMin() < let current = this.root while (current.left !== null) < current = current.left >return current.data > findMax() < let current = this.root while (current.right !== null) < current = current.right >return current.data > find(data) < let current = this.root while (current.data !== data) < if (data < current.data) < current = current.left >else < current = current.right >if (current === null) < return null >> return current > isPresent(data) < let current = this.root while (current) < if (data === current.data) < return true >data < current.data ? current = current.left : current = current.right >return false > remove(data) < const removeNode = function(node, data) < if (node === null) return null if (data === node.data) < // потомки отсутствуют if (node.left === null && node.right === null) return null // отсутствует левый узел if (node.left === null) return node.right // отсутствует правый узел if (node.right === null) return node.left // имеется два узла let tempNode = node.right while (tempNode.left !== null) < tempNode = tempNode.left >node.data = tempNode.data node.right = removeNode(node.right, tempNode.data) return node > else if (data < node.data) < node.left = removeNode(node.right, data) return node >else < node.right = removeNode(node.right, data) return node >> this.root = removeNode(this.root, data) > > const bst = new BST() bst.add(4) bst.add(2) bst.add(6) bst.add(1) bst.add(3) bst.add(5) bst.add(7) bst.remove(4) console.log(bst.findMin()) console.log(bst.findMax()) bst.remove(7) console.log(bst.findMax()) console.log(bst.isPresent(4)) 1 7 6 false 7. Нагруженное (префиксное) дерево (Trie, читается как «try»)
Префиксное дерево — это разновидность поискового дерева. Данные в нем сохраняются последовательно (шаг за шагом) — каждый узел дерева представляет собой один шаг. Префиксное дерево используется в словарях, поскольку существенно ускоряет поиск.
Каждый узел дерева — буква алфавита, следование по ветке приводит к формированию слова. Оно также содержит «булевый индикатор» для определения того, что текущий узел является последней буквой.
Префиксное дерево имеет следующие методы:
- add: добавить слово в словарь
- isWord: проверить наличие слова
- print: вернуть все слова
// узел дерева function Node() < this.keys = new Map() this.end = false this.setEnd = function() < this.end = true >this.isEnd = function() < return this.end >> function Trie() < this.root = new Node() this.add = function(input, node = this.root) < if (input.length === 0) < node.setEnd() return >else if (!node.keys.has(input[0])) < node.keys.set(input[0], new Node()) return this.add(input.substr(1), node.key.get(input[0])) >else < return this.add(input.substr(1), node.keys.get(input[0])) >> this.isWord = function(word) < let node = this.root while (word.length >1) < if (node.keys.has(word[0])) < return false >else < node = node.keys.get(word[0]) word = word.substr(1) >> return (node.keys.has(word) && node.keys.get(word).isEnd()) ? true : false > this.print = function() < let words = new Array() let search = function(node = this.root, string) < if (node.keys.size !== 0) < for (let letter of node.keys.keys()) < search(node.keys.get(letter), string.concat(letter)) >if (node.isEnd()) < words.push(string) >> else < string.length >0 ? words.push(string) : undefined return > > search(this.root, new String()) return words.length > 0 ? words : null > > 8. Граф (график) (Graph)
Граф, также известный как сеть (Network), представляет собой коллекцию связанных между собой узлов. Бывает два вида графов — ориентированный и неориентированный, в зависимости от того, имеют ли ссылки направление. Графы используются повсеместно, например, для расчета наилучшего маршрута в навигационных приложениях или для формирования списка рекомендаций в социальных сетях.
Графы могут быть представлены в виде списка или матрицы.
Список
В данном случае все родительские узлы располагаются слева, а их дочерние элементы справа.
Матрица
В данном случае узлы распределяются по строкам и столбцам, пересечение строки и столбца показывает отношение между узлами: 0 означает, что узлы не связаны между собой, 1 — узлы связаны.
Поиск по графу осуществляется двумя методами — поиск в ширину (Breath-First-Search, BFS) и поиск в глубину (Depth-First-Search, DFS).
function bfs(graph, root) < let nodesLen = <>for (let i = 0; i < graph.length; i++) < nodesLen[i] = Infinity >nodesLen[root] = 0 let queue = [root] let current while (queue.length !== 0) < current = queue.shift() let curConnected = graph[current] let neighborIdx = [] let idx = curConnected.indexOf(1) while (idx !== -1) < neighborIdx.push(idx) idx = curConnected.indexOf(1, idx + 1) >for (let i = 0; i < neighborIdx.length; i++) < if (nodesLen[neighborIdx[i]] === Infinity) < nodesLen[neighborIdx[i]] = nodesLen[current] + 1 queue.push(neighborIdx[i]) >> > return nodesLen > let graph = [ [0, 1, 1, 1, 0], [0, 0, 1, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 1, 0], [0, 1, 0, 0, 0] ] console.log(bfs(graph, 1)) Вставка элемента в массив на определенной позиции в JavaScript
В работе с JavaScript часто возникают ситуации, когда нужно вставить элемент в массив на определенную позицию. Представим, что есть массив цветов:
let colors = ['красный', 'синий', 'зеленый'];
И требуется вставить цвет ‘желтый’ на второе место. Для решения этой задачи можно использовать метод splice() , который умеет как удалять, так и добавлять элементы в массив.
Метод splice()
Метод splice() изменяет содержимое массива, удаляя или заменяя существующие элементы и/или добавляя новые элементы.
array.splice(start[, deleteCount[, item1[, item2[, . ]]]])
- start : Индекс, по которому начинает изменять массив.
- deleteCount (необязательный): Количество элементов, которые нужно удалить.
- item1, item2, . (необязательные): Элементы, которые нужно добавить в массив.
Пример использования
Вернемся к нашему примеру с массивом цветов. Чтобы вставить ‘желтый’ на второе место, нужно вызвать splice() следующим образом:
colors.splice(1, 0, 'желтый');
Теперь массив colors выглядит так:
['красный', 'желтый', 'синий', 'зеленый']
Таким образом, метод splice() – это мощный инструмент для работы с массивами в JavaScript, который позволяет вставлять, удалять и заменять элементы массива.
Основы программирования. Начальный уровень
Экзамен «Основы программирования. Начальный уровень» для пользователей и системных администраторов.
- Основы программирования
- Операторы и функции
- Базовые понятия
- Постановка задачи и алгоритмирование
- Описание
- Подробнее о товаре
- Отзывы (0)
- Вопросы теста
- Обратная связь
Форма сдачи теста: Экстерн
Количество вопросов: 20
Время: 20 минут.
Проходной балл: 70%
Срок действия сертификата: неограничен
Сертификат появляется в Вашем профиле ресурса GeekBrains, и Вы можете его распечатать.
По наличию 11438 шт.
Внимание !
Вопросы к тесту выложены исключительно в ознакомительных целях: количество вопросов может не совпадать с действительным, актуальность не поддерживается,- за решением теста Welcome to the cashier!
Выберите недопустимое использование команды prompt в языке JavaScript:
prompt («this»,»1″);
prompt(«this» 1);
prompt(«thisText»,1);
В какой из «библиотек» в языке JavaScript: находятся математические функции?
Выберите операции языка JavaScript, возвращающие логический результат:
Какое значение будет храниться в переменной res , в результате выполнения операторов var res = «str «+ 2 + 2; в языке JavaScript?
str 4
«str 2 + 2»
«str 22»
Выберите команду в языке JavaScript, при помощи которой пользователь может выводить данные на экран в диалоговом окне:
Выберите правильную запись присвоения целочисленного значения переменной в языке JavaScript:
var temp = «1»;
var temp = 1.0;
var temp = 1;
Что увидит пользователь в случае отсутствия проверки деления на ноль в языке JavaScript?
Ошибку
надпись «Infinity»
программа не запустится
Что называют входными данными?
данные, которые программа возвращает в результате работы
данные, которые программа получает для выполнения последующего вычисления
данные, которые временно хранятся в специально отведённом месте памяти (кеш)
Закончите утверждение: функция в контексте программирования — это
оператор, заменяющий вложенные циклы
самостоятельный элемент кода программы, который позволяет решать выделенную подзадачу
самостоятельный элемент кода программы основной целью которого является оптимизация времени выполнения программы
Какой метод в языке JavaScript добавляет элемент в «хвост» массива?
С какого ключевого слова начинается объявление переменной в языке JavaScript?
Закончите утверждение:в языке javaScript идентификатор (имя) переменной не может начинаться с .
символа нижнего подчеркивания «_»
цифры
заглавной латинской буквы
Какое свойство в языке JavaScript показывает количество элементов массива?
count
size
length
Какое значение будет присвоено переменной res в результате выполнения операторов var res = 2.0 == 2; в языке JavaScript?
Ничего не будет присвоено. Запись ошибочна
true
false
Выберите правильную запись присвоения логического значения переменной в языке JavaScript:
var flag = «true»;
var flag = 1;
var flag = true;
Закончите утверждение: пустой массив в языке JavaScript инициализируется:
var arr = [];
var arr = <>;
var arr = ();
Каковы основные свойства алгоритма?
массовость, результативность, конечность
функциональность, вложенность, ясность
общность, многогранность, конечность
Какова общая цель написания программы?
вычисление заранее известного выражения
ускорение работы операционной системы
получение результата вычисления
Что такое ветвление?
управляющая конструкция, вызывающая сама себя с целью выполнения определённого набора команд
управляющая конструкция, предназначенная для организации многократного исполнения набора инструкций
управляющая конструкция, позволяющая выполнить определённый набор команд, в случае истинности логического выражения
Где обычно хранится программа до запуска?
на жёстком диске или внешнем накопителе
в оперативной памяти
в центральном процессоре
Выберите команду в языке JavaScript, при помощи которой пользователь может вводить данные в программу:
Что такое алгоритм?
набор инструкций, описывающих порядок действий исполнителя для получения результата вычисления
последовательность данных и инструкций, предназначенная для вычислительного устройства
процесс вычисления как последовательное выполнение простых шагов
Что означает константа NaN при выполнении арифметических операций в языке JavaScript?
результат вычисления не является числом
это простой текст не несущий никакой смысловой нагрузки
результат вычисления произведён успешно
Закончите утверждение: все данные, с точки зрения программы, можно разделить на:
простые и составные
двоичные и шестнадцатеричные
входные и выходные
Что такое переменная?
инструкция, описывающая порядок действий для доступа к данным
адрес, который хранит в себе ссылку на данные
именованная область памяти, адрес которой можно использовать для осуществления доступа к данным
Закончите утверждение: бит может принимать значения.
1 и -1
0 и произвольное число от 1 до 9
0 и 1
Какое значение будет присвоено переменной res в результате выполнения операторов var res = true || true && false; в языке JavaScript?
Ничего не будет присвоено. Запись ошибочна
False
true
Как записывается операция вычисления остатка от деления в целых числах в языке JavaScript?
Какой тип данных используется в качестве условия в конструкции ветвления?
логический
строковый
числовой
Закончите утверждение: индексация элементов массива в языке JavaScript начинается с .
Нуля
Единицы
Программист сам задает индексацию
Как выглядит оператор декремента в языке JavaScript?
Закончите утверждение: языки программирования можно разделить на
низкоуровневые и высокоуровневые
C-подобные и Java-подобные
языки программирования не имеют никакого разделения
Как выглядит функция преобразования текста в вещественное число в языке JavaScript?
parseInt
parseFloat
parse
Закончите утверждение: в качестве исполнителя программы выступает .
двоичный код
компьютер
память
Какое значение будет присвоено переменной res в результате выполнения операторов var res = 1 > 2 ? 1 : 2; в языке JavaScript?
1
2
Ничего не будет присвоено. Запись ошибочна
Где программа хранит свои данные после запуска?
на жёстком диске или внешнем накопителе
в оперативной памяти
в центральном процессоре
Закончите утверждение: программа это –
последовательность данных и инструкций, предназначенная для вычислительного устройства
часть памяти компьютера
фрагмент кода, к которому можно обратиться из другого места
Необходимо выбрать недопустимое использование команды alert в языке JavaScript:
alert(«this»;»Text»);
alert(«this»+»Text»);
alert(«thisText»);
Укажите неверное утверждение
оператор return возвращает результат вычисления функции
оператор return обязательно должен быть использован при описании функции
оператор return может возвращать массив
Как называется базовая единица хранения информации?
Закончите утверждение: курс «Основы программирования» даёт базовые понятия из области.
Программирования
формирования запросов к удалённой системе
верстки сайтов
Сколько уникальных значений может принимать 1 байт?
Закончите утверждение: все данные в компьютере представлены .
в виде десятичного кода
в виде двоичного кода
в виде восьмеричного кода
Вы можете обратится к нам напрямую, через:
По Skype: molodoyberkut
По Telegram: @MolodoyBerkut
По ICQ: 657089516
Или через форму обратной связи на нашем сайте
Получите наши последние новости и специальные предложения
Какой метод в языке javascript добавляет элемент в хвост массива
Отличие от массива
Список – более гибкая структура, чем массив. Он позволяет быстрее и удобнее добавлять и удалять элементы в любом месте структуры.
В ряде языков программирования необходимо указывать размер массива при его создании, и потом его нельзя изменить. Связные списки помогают решить эту проблему для создания динамических коллекций. В JavaScript такого нет, но, тем не менее, знать об этом полезно, так как на более низких уровнях абстракции (более близких к машинном коду) все работает примерно одинаково.
Недостатком списка (в сравнении с массивами) является невозможность прямого доступа к конкретному элементу.
Отсюда вытекает разное практическое использование этих структур данных. Массивы полезны, если приходится чаще получать данные, а связные списки, если чаще нужно добавлять/удалять элементы.
Сложность базовых операций
| Массив | Связный список | |
| Получение элемента | 1 (константное время, не зависит от кол-ва элементов) | n (нужно перебрать все предыдущие элементы) |
| Вставка в конец | 1 | 1 |
| Вставка в начало | n | 1 |
| Удаление из конца | 1 | 1 |
| Удаление из начала | n | 1 |
Реализация в JavaScript
Реализуем связный список в виде класса с методами для основных операций:
- prepend – добавление нового элемента в начало списка;
- append – добавление нового элемента в конец списка;
- delete – удаление всех элементов с указанным значением.
Кольцевой связный список
Односвязный и двусвязный список может быть замкнутым (циклическим). При этом хвост содержит указатель на голову, а голова – на хвост (если список двусвязный).
Зачем в JavaScript использовать списки, если есть массивы?
Если речь идет о производительности, то принципиального смысла в этом нет. Массивы – это встроенный модуль, напичканный всевозможными оптимизациями, поэтому преимущества написанного вручную связного списка уже не кажутся существенными.
Однако, интерфейс этой структуры представляет интерес. Например, может быть удобно получать ссылки на предыдущий ( prev ) и следующий ( next ) элементы коллекции прямо из узла, чтобы не привязываться к их индексам.
• Обсуждение на StackOverflow: Вы когда-нибудь писали связные списки на JavaScript?
Стек
Стек – это коллекция элементов, организованная по принципу LIFO (последним пришел – первым вышел). В реальном мире примером стека является стопка тарелок: новые мы кладем наверх стопки и сверху же начинаем забирать.
Элемент, пришедший последним и первый на выход, обычно называется головным, то есть голова у стека фактически находится в хвосте.
У стеков есть три основные операции:
- добавление нового элемента ( push );
- удаление головного элемента ( pop );
- чтение головного элемента без удаления ( peek ).
Реализация в JavaScript
Стек может быть реализован на базе массива или однонаправленного списка.
В JavaScript массивы фактически являются стеками, так как уже предоставляют методы push и pop , поэтому нет необходимости реализовывать стек вручную. Но мы все же попробуем для интереса создать класс Stack на основе написанного в прошлом разделе класса LinkedList (Связный список).
Основные операции очереди:
- добавление нового элемента в конец очереди ( enqueue );
- удаление элемента из начала очереди ( dequeue );
- чтение элемента из начала очереди без удаления ( peek ).
Реализация в JavaScript
Как и стек, очередь может быть реализована как на базе массива, так и на базе связного списка. И опять же, массивы в JavaScript фактически могут работать как очереди, благодаря встроенным методам Array.prototype.push и Array.prototype.unshift .
Реализуем очередь на основе связного списка:
class Queue < constructor() < this.linkedList = new LinkedList(); >isEmpty() < return !this.linkedList.head; >peek() < if (!this.linkedList.head) < return null; >return this.linkedList.head.value; > enqueue(value) < this.linkedList.append(value); >dequeue() < const removedHead = this.linkedList.deleteHead(); return removedHead ? removedHead.value : null; >> Очередь очень похожа по реализации на стек за исключением того, что новые элементы добавляются в хвост связного списка (в стеке добавление происходит со стороны головы).
Примеры использования
Применение для очереди в JavaScript найти нетрудно. Сам язык использует очередь для обработки поступающих событий. Мы можем по аналогии выстраивать в очередь различные коллбэки для обработки данных.
Очередь с приоритетом
Это разновидность очереди, в которой некоторые элементы обладают VIP-статусом.
Каждый элемент в такой очереди имеет приоритет. Первыми будут обрабатываться элементы с высоким приоритетом, независимо от того, когда они были добавлены.
У такой очереди две основные операции:
- добавить новый элемент в конец;
- извлечь элемент с максимальным приоритетом.
Очередь с приоритетом – это более сложная структура, чем обычная очередь, и реализуется обычно по-другому – на основе структуры данных куча , о которой мы поговорим в следующей статье цикла.
Сложность базовых операций в стеках и очередях
Очевидно, что сложность операций зависит от того, на базе какой структуры реализованы стек или очередь. В массивах проще получить доступ к элементу, а в связных списках изменять количество.
| Получение | Добавление | Удаление | |
| Стек на основе массива | 1 | 1 (Array.push) | 1 (Array.pop) |
| Стек на основе списка | n | 1 (LinkedList.prepend) | 1 (LinkedList.deleteHead) |
| Очередь на основе массива | 1 | 1 (Array.push) | n (Array.unshift) |
| Очередь на основе списка | n | 1 (LinkedList.append) | 1 (LinkedList.deleteHead) |
Заключение
Сначала мы изучили основы, а сегодня сравнили четыре очень похожих линейных структуры данных: массивы, связные списки, стеки и очереди. Какую из них выбрать выбрать, зависит от конкретной задачи. Учитывайте размер коллекции, с которой работаете, специфику добавления и удаления элементов, а также частоту обращения к случайным элементам внутри коллекции. Выбирая, обращайте внимание как на эффективность структуры данных, так и на удобство ее интерфейса.
В следующей части мы подробно разберем очень интересную структуру данных – дерево, а также рассмотрим связанные с этой структурой алгоритмы.