Javascript структуры данных: 8 распространенных структур данных на примере JavaScript / Хабр

Содержание

8 распространенных структур данных на примере JavaScript / Хабр

Звучит ли это знакомо: «Я начал заниматься веб разработкой после прохождения курсов»?

Возможно, вы хотите улучшить свои знания основ информатики в части структур данных и алгоритмов. Сегодня мы поговорим о некоторых наиболее распространенных структурах данных на примере JS.

1. Стек (вызовов) (Stack)


Стек следует принципу LIFO (Last In First Out — последним вошел, первым вышел). Если вы сложили книги друг на друга, и захотели взять самую нижнюю книгу, то сначала возьмете верхнюю, затем следующую и т.д. Кнопка «Назад» в браузере позволяет перейти (вернуться) на предыдущую страницу.

Стек имеет следующие методы:

  • push: добавить новый элемент
  • pop: удалить верхний элемент, вернуть его
  • peek: вернуть верхний элемент
  • length: вернуть количество элементов в стеке

Массив в JS имеет атрибуты стека, но мы построим его с нуля с помощью function Stack():
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: получить количество элементов в очереди

Массив в JS имеет некоторые атрибуты очереди, поэтому мы можем использовать его для демонстрации:
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: количество потомков

Вот пример двоичного дерева поиска (Binary Search Tree, BST). Каждый узел имеет только двоих потомков, левый (дочерний) узел меньше текущего (родительского), правый — больше:

Методами данного дерева являются следующие:

  • 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).

Рассмотрим BFS:

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))

Результат:
{
    0: 2,
    1: 0,
    2: 1,
    3: 3,
    4: Infinity
}

На этом у меня все. Надеюсь, вы нашли для себя что-то полезное. Счастливого кодинга!

JavaScript Essentials: Типы и структура данных | by Evgeny Vladimirovich | NOP::Nuances of Programming

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

Здесь, я не буду углубляться в детали, вместо этого мы пробежимся по списку основных тем, с которыми вы со временем столкнётесь в JS. Я дам список ресурсов для обучения. Другими словами, лучше разобраться с этим сейчас, чем откладывать на потом.

Уровень подготовки

Для этой темы особой подготовки не нужно. Это основы любого языка, но в JavaScript всё немного запутанно.

Далее мы будем использовать оператор typeof, чтобы разобраться с типами.

Есть ли типы в JS?

Кто-то может сказать, что JS не типизированный язык или что его типы нельзя назвать системными типами. От вас не требуется объявлять тип при создании переменной, как в других строго типизированных языках, например int x = 10. Я же (как и JS специалисты) заявляю, что в JS есть типы.

JS можно назвать и динамически типизированным и слабо типизированным.

Статическая типизация

JS не является статически типизированным языком, если только вы не используете такие инструменты как Typescript или Flow, которые компилируют в JS код. Мы коснёмся этой темы для примера.

Статическая типизация подразумевает принудительное присвоение типа, который не так просто изменить. Все переменные должны объявляться с типом.

int x = 5
string y = 'abc'

Динамическая типизация

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

var a = 1 // int
b = 'test' // string
// etc

Слабая типизация

Слабо типизированные языки допускают изменение типа. Например: 1 + '2' // '12' . JS видит, что вы пытаетесь сложить число и строку (недопустимая операция), в результате он преобразует число в строку и возвращает ‘12’.

Примитивы

Эти шесть типов задуманы как примитивы. Они не являются объектами и не имеют собственных методов. Все примитивы неизменны.

  • Boolean — true or false
  • Null — нет значения
  • Undefined — объявленная переменная, но без значения
  • Number — целочисленные, с плавающей точкой и т.д.
  • String —строка
  • Symbol — уникальное значение, которое не совпадает с другими

Всё остальное это объекты.

Основы примитивов

Объекты

Приведу несколько стандартных объектов. Обратите внимание, некоторые из них были в списке примитивов, не спутайте их. Эти ведут себя как конструкторы, например Boolean('a') // true .

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

Есть ещё множество объектов, вот некоторые из них:

  • Function
  • Boolean
  • Symbol
  • Error
  • Number
  • String
  • RegExp
  • Math
  • Set
Основы объектов

Так, где же здесь подвох?

Неразбериха начинается, когда отличающиеся типы смешиваются. JavaScript преобразует типы на своё усмотрение. Этому посвящена целая статья:

Далее, я расскажу о других непонятных моментах и хитростях.

Важные принципы

  • Все значения примитивов ― неизменны
  • Осторожно с приведением типов
  • Здесь нет места статической типизации т.е. int num = 5
  • Движок JavaScript сам определяет типы

Странности

В JavaScript много странностей. Подробней здесь: Wtf JS?

Почему Null это объект?

Документация причисляет Null к примитивам, тем не менее оператор typeof возвращает значение ‘object’ .

По сути, это баг, который не исправили, потому что существующий код перестанет работать. Этот баг присутствовал ещё с первой версии JavaScript, он пришёл из функции typeof в исходниках JS. Я покажу это с помощью псевдокода:

Псевдокод

Улавливаете? Они не проверили null

Подробней о причинах отказа исправлять баг, читайте здесь. А здесь, та часть исходника JS о которой я говорил.

Почему не number стало number?

typeof NaN // 'number' WTF!?

Если коротко, то NaN определён как числовой тип, но это не настоящее число. NaN ― это результат неких математических операций, который не может считаться числом.

Или ещё короче, потому что эксперты так сказали.

Двойное равно vs Тройное равно

На CodeBurst есть статья на эту тему:

Если сомневаетесь, всегда используйте тройное равно.

Примитив не является объектом и не имеет собственных методов

Если примитивы не имеют методов, тогда почему работает 'abc'.length ?

Я не ошибся, так сказано в документации.

Примитивы — это данные (значения, типы данных), которые не являются объектами и не имеют методов. В JavaScript есть 6 примитивов: string, number, boolean, null, undefined, symbol (новые из ECMAScript 2015).

Во-первых, не путайте конструкторы и примитивы. Каждый примитив имеет конструктор или родительский объект. JS понимает, когда вы пытаетесь применить метод к примитиву и самостоятельно использует конструктор, чтобы создать объект из вашего примитива. После того как метод запущен, этот объект удаляется из памяти.

Вот пример:

Строка — это примитив

По факту, строки являются примитивами, как упоминалось в статье, а не полноценными объектами. JS понимает, когда вы пытаетесь применить метод на объект String и преобразует ваш примитив в строковый объект. Когда дело сделано, временный объект удаляется и всё становится на свои места.

конструктор строки

Способы использовать типы в своих интересах.

Пользуйтесь этим с осторожностью. В большинстве случаев, используйте Number(str) parseInt(x) String(num) и т.д. Это на всякий случай, если вдруг встретите подобное в чужом коде, чтобы знать зачем этот код. Или если вы играете в Code golf ⛳️

преобразование типа, значение по умолчанию, короткое if

Перевод статьи CodeDraken : JavaScript Essentials: Types & Data Structures

10 структур данных, которые вы должны знать (+видео и задания)

Бо Карнс – разработчик и преподаватель расскажет о наиболее часто используемых и общих структурах данных. Специально для вас мы перевели его статью.

«Плохие программисты беспокоятся о коде. Хорошие программисты беспокоятся о структурах данных и их отношениях ». - Линус Торвальдс, создатель Linux

Структуры данных являются важной частью разработки программного обеспечения и одной из наиболее распространенных тем для вопросов на собеседованиях с разработчиками.
Хорошая новость в том, что они в основном являются просто специализированными форматами для организации и хранения данных.
Из этой статьи вы узнаете о 10 наиболее распространенных структурах данных. Также сюда добавлены видеоролики (на английском языке) по каждой из структур, и код их реализации на JS. А чтобы вы немного попрактиковались, я добавил сюда задачи из бесплатной учебной программы freeCodeCamp.
Обратите внимание, что некоторые из этих структур данных включают временную сложность в нотации Big O. Это не относится ко всем из них, поскольку временная сложность иногда основана на реализации. Если вы хотите узнать больше о нотации Big O, посмотрите видео от Briana Marie .
Несмотря на то, что для каждой структуры я привожу код реализации на JavaScript, вам вероятно, никогда не придется делать этого самостоятельно, только если вы не будете использовать низкоуровневый язык вроде С. JavaScript (как и большинство языков высокого уровня) имеет встроенные реализации многих из этих структур данных.
Тем не менее, знание того, как реализовать эти структуры данных, даст вам огромное преимущество в поиске работы и может пригодиться, когда вы попытаетесь написать высокопроизводительный код.

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

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

Временная сложность связного списка 
╔═══════════╦═════════╦══════════════╗
║ Алгоритм  ║В среднем║Худший случай ║
╠═══════════╬═════════╬══════════════╣
║ Space     ║ O(n)    ║ O(n)         ║
║ Search    ║ O(n)    ║ O(n)         ║
║ Insert    ║ O(1)    ║ O(1)         ║
║ Delete    ║ O(1)    ║ O(1)         ║
╚═══════════╩═════════╩══════════════╝

Задания с freeCodeCamp:

Стек - это базовая структура данных, в которой вы можете только вставлять или удалять элементы в начале стека. Он напоминает стопку книг. Если вы хотите взглянуть на книгу в середине стека, вы сначала должны взять книги, лежащие сверху.
Стек считается LIFO (Last In First Out) - это означает, что последний элемент, который добавлен в стек, - это первый элемент, который из него выходит.

Существует три основных операции, которые могут выполняться в стеках: вставка элемента в стек (называемый «push»), удаление элемента из стека (называемое «pop») и отображение содержимого стека (иногда называемого «pip»).

Реализация на JavaScript

Временная сложность стека 
╔═══════════╦═════════╦══════════════╗
║ Алгоритм  ║В среднем║Худший случай ║
╠═══════════╬═════════╬══════════════╣
║ Space     ║ O(n)    ║ O(n)         ║
║ Search    ║ O(n)    ║ O(n)         ║
║ Insert    ║ O(1)    ║ O(1)         ║
║ Delete    ║ O(1)    ║ O(1)         ║
╚═══════════╩═════════╩══════════════╝

Задания с freeCodeCamp:

Вы можете думать об этой структуре, как об очереди людей в продуктовом магазине. Стоящий первым будет обслужен первым. Также как очередь.

Если рассматривать очередь с точки доступа к данным, то она является FIFO (First In First Out). Это означает, что после добавления нового элемента все элементы, которые были добавлены до этого, должны быть удалены до того, как новый элемент будет удален.
В очереди есть только две основные операции: enqueue и dequeue. Enqueue означает вставить элемент в конец очереди, а dequeue означает удаление переднего элемента.

Реализация на JavaScript

Временная сложность очереди 
╔═══════════╦═════════╦══════════════╗
║ Алгоритм  ║В среднем║Худший случай ║
╠═══════════╬═════════╬══════════════╣
║ Space     ║ O(n)    ║ O(n)         ║
║ Search    ║ O(n)    ║ O(n)         ║
║ Insert    ║ O(1)    ║ O(1)         ║
║ Delete    ║ O(1)    ║ O(1)         ║
╚═══════════╩═════════╩══════════════╝

Задания с freeCodeCamp:


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

  • Union (Объединение). Объединяет все элементы из двух разных множеств и возвращает результат, как новый набор (без дубликатов).
  • Intersection (Пересечение). Если заданы два множества, эта функция вернет другое множество, содержащее элементы, которые имеются и в первом и во втором множестве.
  • Difference  (Разница). Вернет список элементов, которые находятся в одном множестве, но НЕ повторяются в другом.
  • Subset(Подмножество) - возвращает булево значение, показывающее, содержит ли одно множество все элементы другого множества.

Реализация на JavaScript

Задания с freeCodeCamp:

Map - это структура данных, которая хранит данные в парах ключ / значение, где каждый ключ уникален. Map иногда называется ассоциативным массивом или словарем. Она часто используется для быстрого поиска данных. Map’ы позволяют сделать следующее:

  • Добавление пары в коллекцию
  • Удаление пары из коллекции
  • Изменение существующей пары
  • Поиск значения, связанного с определенным ключом

Реализация на JavaScript

Задания с freeCodeCamp:

Хэш-таблица - это структура данных, реализующая интерфейс map, который позволяет хранить пары ключ / значение. Она использует хеш-функцию для вычисления индекса в массиве, по которым можно найти желаемое значение.
Хеш-функция обычно принимает строку и возвращает числовое значение. Хеш-функция всегда должна возвращать одинаковое число для одного и того же ввода. Когда два ввода хешируются с одним и тем же цифровым выходом, это коллизия. Суть в том, чтобы их было как можно меньше.
Поэтому, когда вы вводите пару ключ / значение в хеш-таблице, ключ проходит через хеш-функцию и превращается в число. Это числовое значение затем используется в качестве фактического ключа, в котором значение хранится. Когда вы снова попытаетесь получить доступ к тому же ключу, хеширующая функция обработает ключ и вернет тот же числовой результат. Затем число будет использовано для поиска связанного значения. Это обеспечивает очень эффективное время поиска O (1) в среднем.

Реализация на JavaScript

Временная сложность хэш-таблицы 
╔═══════════╦═════════╦═══════════════╗
║ Алгоритм  ║В среднем║Худший случай  ║
╠═══════════╬═════════╬═══════════════╣
║ Space     ║ O(n)    ║ O(n)          ║
║ Search    ║ O(1)    ║ O(n)          ║
║ Insert    ║ O(1)    ║ O(n)          ║
║ Delete    ║ O(1)    ║ O(n)          ║
╚═══════════╩═════════╩═══════════════╝

Задания с freeCodeCamp:

Дерево - это структура данных, состоящая из узлов. Она имеет следующие характеристики:

  1. Каждое дерево имеет корневой узел (вверху).
  2. Корневой узел имеет ноль или более дочерних узлов.
  3. Каждый дочерний узел имеет ноль или более дочерних узлов и т. д.

Двоичное дерево поиска имеет + две характеристики:

  1. Каждый узел имеет до двух детей(потомков).
  2. Для каждого узла его левые потомки меньше текущего узла, что меньше, чем у правых потомков.

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

Реализация на JavaScript

Временная сложность двоичного поиска
╔═══════════╦══════════╦══════════════╗
║ Алгоритм  ║В среднем ║Худший случай ║
╠═══════════╬══════════╬══════════════╣
║ Space     ║ O(n)     ║ O(n)         ║
║ Search    ║ O(log n) ║ O(n)         ║
║ Insert    ║ O(log n) ║ O(n)         ║
║ Delete    ║ O(log n) ║ O(n)         ║
╚═══════════╩══════════╩══════════════╝

Задания с freeCodeCamp:

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

Каждый узел в префиксном дереве содержит одну букву слова. Вы следуете ветвям дерева, чтобы записать слово, по одной букве за раз. Шаги начинают расходиться, когда порядок букв отличается от других слов в дереве или, когда заканчивается слово. Каждый узел содержит букву (данные) и логическое значение, указывающее, является ли узел последним узлом в слове.
Посмотрите на изображение, и вы можете создавать слова. Всегда начинайте с корневого узла вверху и двигайтесь вниз. Показанное здесь дерево содержит слово ball, bat, doll, do, dork, dorm, send, sense.

Реализация на JavaScript

Задания с freeCodeCamp:


Двоичная куча - это очередное дерево, в каждом узле которого не более двух детей. Кроме того, это полное дерево. Это означает, что все уровни полностью заполнены до последнего уровня, а последний уровень заполняется слева направо.
Двоичная куча может быть либо минимальной, либо максимальной. В максимальной -ключи родительских узлов всегда больше или равны тем, что у детей. В минимальной -ключи родительских узлов меньше или равны ключам дочерних элементов.
Важен порядок между уровнями, но не узлами на одном уровне. На изображении вы можете видеть, что третий уровень минимальной кучи имеет значения 10, 6 и 12. Они расположены не по порядку.

Реализация на JavaScript

Временная сложность двоичной кучи
╔═══════════╦══════════╦═══════════════╗
║ Алгоритм  ║В среднем ║ Худший случай ║
╠═══════════╬══════════╬═══════════════╣
║ Space     ║ O(n)     ║ O(n)          ║
║ Search    ║ O(n)     ║ O(n)          ║
║ Insert    ║ O(1)     ║ O(log n)      ║
║ Delete    ║ O(log n) ║ O(log n)      ║
║ Peek      ║ O(1)     ║ O(1)          ║
╚═══════════╩══════════╩═══════════════╝

Задания с freeCodeCamp:

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

Существует два основных типа графов: ориентированные и неориентированные. Второй тип - это графы без какого-либо направления на ребрах между узлами. Ориентированные графы, напротив, представляют собой графы с направлением на них.
Два частых способа представления графа - это список смежности и матрица смежности.

Список смежности может быть представлен как список, где левая сторона является узлом, а правая - списком всех других узлов, с которыми он соединен.
Матрица смежности представляет собой таблицу чисел, где каждая строка или столбец представляет собой другой узел на графе. На пересечении строки и столбца есть число, которое указывает на отношение. Нули означают, что нет ребер или отношений. Единицы означают, что есть отношения. Числа выше единицы могут использоваться для отображения разных весов.
Алгоритмы обхода - это алгоритмы для перемещения или посещения узлов в графе. Основными типами алгоритмов обхода являются поиск в ширину и поиск в глубину. Одно из применений заключается в определении того, насколько близко узлы расположены по отношению к корневому узлу. Посмотрите, как реализовать поиск по ширине в JavaScript в приведенном ниже видео.

Реализация на JavaScript

Временная сложность списка смежности (граф) 
╔═══════════════╦════════════╗
║   Алгоритм    ║   Время    ║
╠═══════════════╬════════════╣
║ Storage       ║ O(|V|+|E|) ║
║ Add Vertex    ║ O(1)       ║
║ Add Edge      ║ O(1)       ║
║ Remove Vertex ║ O(|V|+|E|) ║
║ Remove Edge   ║ O(|E|)     ║
║ Query         ║ O(|V|)     ║
╚═══════════════╩════════════╝

Задания с freeCodeCamp:

Если хотите узнать больше:

Книга Grokking Algorithms - лучшая книга на эту тему, если вы новичок в структурах данных / алгоритмах и не обладаете базой компьютерных наук. Автор использует простые объяснения и юмор, рисованные иллюстрации (он является ведущим разработчиком в Etsy), чтобы объяснить некоторые структуры данных, представленные в этой статье.

JavaScript алгоритмы и структуры данных Мастер-класс

  • Урок 1. 00:07:44

    Curriculum Walkthrough

  • Урок 2. 00:02:53

    What Order Should You Watch In?

  • Урок 3. 00:03:22

    How I'm Running My Code

  • Урок 4. 00:07:42

    Intro to Big O

  • Урок 5. 00:10:20

    Timing Our Code

  • Урок 6. 00:04:37

    Counting Operations

  • Урок 7. 00:04:26

    Visualizing Time Complexities

  • Урок 8. 00:09:59

    Official Intro to Big O

  • Урок 9. 00:09:33

    Simplifying Big O Expressions

  • Урок 10. 00:06:27

    Space Complexity

  • Урок 11. 00:08:47

    Logs and Section Recap

  • Урок 12. 00:01:43

    Section Introduction

  • Урок 13. 00:05:32

    The BIG O of Objects

  • Урок 14. 00:06:26

    When are Arrays Slow?

  • Урок 15. 00:05:57

    Big O of Array Methods

  • Урок 16. 00:07:09

    Introduction to Problem Solving

  • Урок 17. 00:08:00

    Step 1: Understand The Problem

  • Урок 18. 00:06:20

    Step 2: Concrete Examples

  • Урок 19. 00:07:45

    Step 3: Break It Down

  • Урок 20. 00:10:33

    Step 4: Solve Or Simplify

  • Урок 21. 00:16:58

    Step 5: Look Back and Refactor

  • Урок 22. 00:04:13

    Recap and Interview Strategies

  • Урок 23. 00:02:56

    Intro to Problem Solving Patterns

  • Урок 24. 00:15:12

    Frequency Counter Pattern

  • Урок 25. 00:02:34

    Frequency Counter: Anagram Challenge

  • Урок 26. 00:06:19

    Anagram Challenge Solution

  • Урок 27. 00:09:43

    Multiple Pointers Pattern

  • Урок 28. 00:04:30

    Multiple Pointers: Count Unique Values Challenge

  • Урок 29. 00:06:31

    Count Unique Values Solution

  • Урок 30. 00:13:15

    Sliding Window Pattern

  • Урок 31. 00:07:03

    Divide And Conquer Pattern

  • Урок 32. 00:07:07

    Story Time: Martin & The Dragon

  • Урок 33. 00:05:54

    Why Use Recursion?

  • Урок 34. 00:07:08

    The Call Stack

  • Урок 35. 00:05:12

    Our First Recursive Function

  • Урок 36. 00:07:55

    Our Second Recursive Function

  • Урок 37. 00:02:20

    Writing Factorial Iteratively

  • Урок 38. 00:03:16

    Writing Factorial Recursively

  • Урок 39. 00:05:07

    Common Recursion Pitfalls

  • Урок 40. 00:06:24

    Helper Method Recursion

  • Урок 41. 00:07:46

    Pure Recursion

  • Урок 42. 00:04:05

    Intro to Searching

  • Урок 43. 00:04:48

    Intro to Linear Search

  • Урок 44. 00:05:19

    Linear Search Solution

  • Урок 45. 00:01:56

    Linear Search BIG O

  • Урок 46. 00:05:48

    Intro to Binary Search

  • Урок 47. 00:02:41

    Binary Search PseudoCode

  • Урок 48. 00:16:42

    Binary Search Solution

  • Урок 49. 00:06:10

    Binary Search BIG O

  • Урок 50. 00:04:39

    Naive String Search

  • Урок 51. 00:12:30

    Naive String Search Implementation

  • Урок 52. 00:08:36

    Introduction to Sorting Algorithms

  • Урок 53. 00:04:41

    Built-In JavaScript Sorting

  • Урок 54. 00:07:22

    Bubble Sort: Overview

  • Урок 55. 00:09:59

    Bubble Sort: Implementation

  • Урок 56. 00:04:23

    Bubble Sort: Optimization

  • Урок 57. 00:01:29

    Bubble Sort: BIG O Complexity

  • Урок 58. 00:06:19

    Selection Sort: Introduction

  • Урок 59. 00:11:15

    Selection Sort: Implementation

  • Урок 60. 00:01:41

    Selection Sort: Big O Complexity

  • Урок 61. 00:03:18

    Insertion Sort: Introduction

  • Урок 62. 00:10:43

    Insertion Sort: Implementation

  • Урок 63. 00:02:25

    Insertion Sort: BIG O Complexity

  • Урок 64. 00:05:34

    Comparing Bubble, Selection, and Insertion Sort

  • Урок 65. 00:06:06

    Intro to the "Crazier" Sorts

  • Урок 66. 00:05:26

    Merge Sort: Introduction

  • Урок 67. 00:05:12

    Merging Arrays Intro

  • Урок 68. 00:06:56

    Merging Arrays: Implementation

  • Урок 69. 00:02:22

    Writing Merge Sort Part 1

  • Урок 70. 00:12:38

    Writing Merge Sort Part 2

  • Урок 71. 00:06:23

    Merge Sort BIG O Complexity

  • Урок 72. 00:09:01

    Introduction to Quick Sort

  • Урок 73. 00:08:07

    Pivot Helper Introduction

  • Урок 74. 00:08:09

    Pivot Helper Implementation

  • Урок 75. 00:08:47

    Quick Sort Implementation

  • Урок 76. 00:04:16

    Quick Sort Call Stack Walkthrough

  • Урок 77. 00:04:07

    Quick Sort Big O Complexity

  • Урок 78. 00:09:23

    Radix Sort: Introduction

  • Урок 79. 00:11:10

    Radix Sort: Helper Methods

  • Урок 80. 00:04:19

    Radix Sort: Pseudocode

  • Урок 81. 00:10:25

    Radix Sort: Implementation

  • Урок 82. 00:03:52

    Radix Sort: BIG O Complexity

  • Урок 83. 00:12:39

    Which Data Structure Is The Best?

  • Урок 84. 00:05:15

    ES2015 Class Syntax Overview

  • Урок 85. 00:06:37

    Data Structures: The Class Keyword

  • Урок 86. 00:09:50

    Data Structures: Adding Instance Methods

  • Урок 87. 00:07:12

    Data Structures: Adding Class Methods

  • Урок 88. 00:07:47

    Intro to Singly Linked Lists

  • Урок 89. 00:07:23

    Starter Code and Push Intro

  • Урок 90. 00:04:25

    Singly Linked List: Push Solution

  • Урок 91. 00:06:15

    Singly Linked List: Pop Intro

  • Урок 92. 00:07:36

    Singly Linked List: Pop Solution

  • Урок 93. 00:01:32

    Singly Linked List: Shift Intro

  • Урок 94. 00:03:23

    Singly Linked List: Shift Solution

  • Урок 95. 00:01:35

    Singly Linked List: Unshift Intro

  • Урок 96. 00:05:59

    Singly Linked List: Unshift Solution

  • Урок 97. 00:02:33

    Singly Linked List: Get Intro

  • Урок 98. 00:03:33

    Singly Linked List: Get Solution

  • Урок 99. 00:01:27

    Singly Linked List: Set Intro

  • Урок 100. 00:02:11

    Singly Linked List: Set Solution

  • Урок 101. 00:04:28

    Singly Linked List: Insert Intro

  • Урок 102. 00:07:50

    Singly Linked List: Insert Solution

  • Урок 103. 00:01:57

    Singly Linked List: Remove Intro

  • Урок 104. 00:03:16

    Singly Linked List: Remove Solution

  • Урок 105. 00:04:47

    Singly Linked List: Reverse Intro

  • Урок 106. 00:08:59

    Singly Linked List: Reverse Solution

  • Урок 107. 00:05:42

    Singly Linked List: BIG O Complexity

  • Урок 108. 00:04:44

    Doubly Linked Lists Introduction

  • Урок 109. 00:03:01

    Setting Up Our Node Class

  • Урок 110. 00:02:11

    Push

  • Урок 111. 00:04:05

    Push Solution

  • Урок 112. 00:03:21

    Pop

  • Урок 113. 00:06:24

    Pop Solution

  • Урок 114. 00:02:45

    Shift

  • Урок 115. 00:04:13

    Shift Solution

  • Урок 116. 00:01:37

    Unshift

  • Урок 117. 00:02:20

    Unshift Solution

  • Урок 118. 00:04:03

    Get

  • Урок 119. 00:07:05

    Get Solution

  • Урок 120. 00:01:19

    Set

  • Урок 121. 00:02:09

    Set Solution

  • Урок 122. 00:02:51

    Insert

  • Урок 123. 00:06:49

    Insert Solution

  • Урок 124. 00:02:19

    Remove

  • Урок 125. 00:06:29

    Remove Solution

  • Урок 126. 00:04:33

    Comparing Singly and Doubly Linked Lists

  • Урок 127. 00:06:20

    Intro to Stacks

  • Урок 128. 00:07:06

    Creating a Stack with an Array

  • Урок 129. 00:11:34

    Writing Our Own Stack From Scratch

  • Урок 130. 00:02:15

    BIG O of Stacks

  • Урок 131. 00:04:15

    Intro to Queues

  • Урок 132. 00:03:26

    Creating Queues Using Arrays

  • Урок 133. 00:10:25

    Writing Our Own Queue From Scratch

  • Урок 134. 00:02:31

    BIG O of Queues

  • Урок 135. 00:06:46

    Introduction to Trees

  • Урок 136. 00:06:33

    Uses For Trees

  • Урок 137. 00:05:55

    Intro to Binary Trees

  • Урок 138. 00:01:14

    POP QUIZ!

  • Урок 139. 00:02:56

    Searching A Binary Search Tree

  • Урок 140. 00:02:45

    Our Tree Classes

  • Урок 141. 00:03:51

    BST: Insert

  • Урок 142. 00:11:54

    BST: Insert Solution

  • Урок 143. 00:04:43

    BST: Find

  • Урок 144. 00:05:37

    BST: Find Solution

  • Урок 145. 00:05:59

    Big O of Binary Search Trees

  • Урок 146. 00:04:51

    Intro To Tree Traversal

  • Урок 147. 00:05:52

    Breadth First Search Intro

  • Урок 148. 00:06:21

    Breadth First Search Solution

  • Урок 149. 00:05:38

    Depth First PreOrder Intro

  • Урок 150. 00:06:51

    Depth First PreOrder Solution

  • Урок 151. 00:04:03

    Depth First PostOrder Intro

  • Урок 152. 00:02:39

    Depth First PostOrder Solution

  • Урок 153. 00:02:08

    Depth First InOrder Intro

  • Урок 154. 00:02:33

    Depth First InOrder Solution

  • Урок 155. 00:07:38

    When to Use BFS and DFS

  • Урок 156. 00:07:31

    Intro to Heaps

  • Урок 157. 00:07:06

    Storing Heaps

  • Урок 158. 00:09:15

    Heap: Insert Intro

  • Урок 159. 00:10:52

    Heap: Insert Solution

  • Урок 160. 00:08:29

    Heap: ExtractMax Intro

  • Урок 161. 00:17:57

    Heap: ExtractMax Solution

  • Урок 162. 00:09:00

    Priority Queue Intro

  • Урок 163. 00:03:44

    Priority Queue Pseudocode

  • Урок 164. 00:09:22

    Priority Queue Solution

  • Урок 165. 00:08:55

    BIG O of Binary Heaps

  • Урок 166. 00:05:51

    Intro to Hash Tables

  • Урок 167. 00:04:33

    More About Hash Tables

  • Урок 168. 00:06:12

    Intro to Hash Functions

  • Урок 169. 00:08:28

    Writing Our First Hash Function

  • Урок 170. 00:07:11

    Improving Our Hash Function

  • Урок 171. 00:04:00

    Handling Collisions

  • Урок 172. 00:04:03

    Hash Table Set and Get

  • Урок 173. 00:05:15

    Hash Table Set Solution

  • Урок 174. 00:06:44

    Hash Table Get Solution

  • Урок 175. 00:01:42

    Hash Table Keys and Values

  • Урок 176. 00:08:44

    Hash Table Keys and Values Solution

  • Урок 177. 00:05:42

    Hash Table Big O Complexity

  • Урок 178. 00:03:51

    Intro to Graphs

  • Урок 179. 00:07:58

    Uses for Graphs

  • Урок 180. 00:08:49

    Types of Graphs

  • Урок 181. 00:03:58

    Storing Graphs: Adjacency Matrix

  • Урок 182. 00:02:30

    Storing Graphs: Adjacency List

  • Урок 183. 00:05:52

    Adjacency Matrix Vs. List BIG O

  • Урок 184. 00:02:11

    Add Vertex Intro

  • Урок 185. 00:02:55

    Add Vertex Solution

  • Урок 186. 00:02:33

    Add Edge Intro

  • Урок 187. 00:02:12

    Add Edge Solution

  • Урок 188. 00:01:36

    Remove Edge Intro

  • Урок 189. 00:02:42

    Remove Edge Solution

  • Урок 190. 00:02:36

    Remove Vertex Intro

  • Урок 191. 00:04:35

    Remove Vertex Solution

  • Урок 192. 00:08:39

    Intro to Graph Traversal

  • Урок 193. 00:08:31

    Depth First Graph Traversal

  • Урок 194. 00:07:28

    DFS Recursive Intro

  • Урок 195. 00:12:46

    DFS Recursive Solution

  • Урок 196. 00:03:38

    DFS Iterative Intro

  • Урок 197. 00:08:45

    DFS Iterative Solution

  • Урок 198. 00:03:00

    Breadth First Graph Traversal

  • Урок 199. 00:02:28

    BFS Intro

  • Урок 200. 00:08:10

    BFS Solution

  • Урок 201. 00:02:42

    Intro to Dijkstra's and Prerequisites

  • Урок 202. 00:09:01

    Who was Dijkstra and what is his Algorithm?

  • Урок 203. 00:05:21

    Writing a Weighted Graph

  • Урок 204. 00:16:27

    Walking through the Algorithm

  • Урок 205. 00:03:49

    Introducing Our Simple Priority Queue

  • Урок 206. 00:04:29

    Dijkstra's Pseudo-Code

  • Урок 207. 00:21:19

    Implementing Dijkstra's Algorithm

  • Урок 208. 00:01:53

    Upgrading the Priority Queue

  • Урок 209. 00:05:04

    Intro to Dynamic Programming

  • Урок 210. 00:06:00

    Overlapping Subproblems

  • Урок 211. 00:06:29

    Optimal Substructure

  • Урок 212. 00:06:44

    Writing A Recursive Solution

  • Урок 213. 00:04:12

    Time Complexity of Our Solution

  • Урок 214. 00:03:40

    The Problem With Our Solution

  • Урок 215. 00:09:01

    Enter Memoization!

  • Урок 216. 00:03:28

    Time Complexity of Memoized Solution

  • Урок 217. 00:07:00

    Tabulation: A Bottom Up Approach

  • 10 типов структур данных, которые нужно знать

    Екатерина Малахова, редактор-фрилансер, специально для блога Нетологии адаптировала статью Beau Carnes об основных типах структур данных.

    «Плохие программисты думают о коде. Хорошие программисты думают о структурах данных и их взаимосвязях», — Линус Торвальдс, создатель Linux.

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

    Программа обучения: «Big Data: основы работы с большими массивами данных»

    В этой статье я покажу вам 10 самых распространенных структур данных. Для каждой из них приведены видео и примеры их реализации на JavaScript. Чтобы вы смогли попрактиковаться, я также добавил несколько упражнений из бета-версии новой учебной программы freeCodeCamp.   

    Обратите внимание, что некоторые структуры данных включают временную сложность в нотации «большого О». Это относится не ко всем из них, так как иногда временная сложность зависит от реализации. Если вы хотите узнать больше о нотации «большого О», посмотрите это видео от Briana Marie.

    Офлайн-курс: «Data Scientist»

    В статье я привожу примеры реализации этих структур данных на JavaScript: они также пригодятся, если вы используете низкоуровневый язык вроде С. В многие высокоуровневые языки, включая JavaScript, уже встроены реализации большинства структур данных, о которых пойдет речь. Тем не менее, такие знания станут серьезным преимуществом при поиске работы и пригодятся при написании высокопроизводительного кода.

    Связные списки

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


    Так устроен связный список

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

    Основные операции в связном списке включают добавление, удаление и поиск элемента в списке.

    Пример реализации на JavaScript

    Временная сложность связного списка

    Упражнения от freeCodeCamp

    Стеки

    Стек — это базовая структура данных, которая позволяет добавлять или удалять элементы только в её начале. Она похожа на стопку книг: если вы хотите взглянуть на книгу в середине стека, сперва придется убрать лежащие сверху.

    Стек организован по принципу LIFO (Last In First Out, «последним пришёл — первым вышел») . Это значит, что последний элемент, который вы добавили в стек, первым выйдет из него.

    Так устроен стек

    В стеках можно выполнять три операции: добавление элемента (push), удаление элемента (pop) и отображение содержимого стека (pip).

    Пример реализации на JavaScript

    Временная сложность стека

    Упражнения от freeCodeCamp

    Очереди

    Эту структуру можно представить как очередь в продуктовом магазине. Первым обслуживают того, кто пришёл в самом начале — всё как в жизни.

    Так устроена очередь

    Очередь устроена по принципу FIFO (First In First Out, «первый пришёл — первый вышел»). Это значит, что удалить элемент можно только после того, как были убраны все ранее добавленные элементы.

    Очередь позволяет выполнять две основных операции: добавлять элементы в конец очереди (enqueue) и удалять первый элемент (dequeue).

    Пример реализации на JavaScript

    Временная сложность очереди

    Упражнения от freeCodeCamp

    Множества


    Так выглядит множество

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

    • Объединение комбинирует все элементы из двух разных множеств, превращая их в одно (без дубликатов).  
    • Пересечение анализирует два множества и  создает еще одно из тех элементов, которые присутствуют в обоих изначальных множествах.
    • Разность выводит список элементов, которые есть в одном множестве, но отсутствуют в другом.
    • Подмножество выдает булево значение, которое показывает, включает ли одно множество все элементы другого множества.

    Пример реализации на JavaScript

    Упражнения от freeCodeCamp

    Map

    Map — это структура, которая хранит данные в парах ключ/значение, где каждый ключ уникален. Иногда её также называют ассоциативным массивом или словарём. Map часто используют для быстрого поиска данных. Она позволяет делать следующие вещи:

    • добавлять пары в коллекцию;
    • удалять пары из коллекции;
    • изменять существующей пары;
    • искать значение, связанное с определенным ключом.


    Так устроена структура map

    Пример реализации на JavaScript

    Упражнения от freeCodeCamp

    Хэш-таблицы


    Так работают хэш-таблица и хэш-функция

    Хэш-таблица — это похожая на Map структура, которая содержит пары ключ/значение. Она использует хэш-функцию для вычисления индекса в массиве из блоков данных, чтобы найти желаемое значение.

    Обычно хэш-функция принимает строку символов в качестве вводных данных и выводит числовое значение. Для одного и того же ввода хэш-функция должна возвращать одинаковое число. Если два разных ввода хэшируются с одним и тем же итогом, возникает коллизия. Цель в том, чтобы таких случаев было как можно меньше.  

    Таким образом, когда вы вводите пару ключ/значение в хэш-таблицу, ключ проходит через хэш-функцию и превращается в число. В дальнейшем это число используется как фактический ключ, который соответствует определенному значению. Когда вы снова введёте тот же ключ, хэш-функция обработает его и вернет такой же числовой результат. Затем этот результат будет использован для поиска связанного значения. Такой подход заметно сокращает среднее время поиска.  

    Пример реализации на JavaScript

    Временная сложность хэш-таблицы

    Упражнения от freeCodeCamp

    Двоичное дерево поиска


    Двоичное дерево поиска

    Дерево — это структура данных, состоящая из узлов. Ей присущи следующие свойства:

    1. Каждое дерево имеет корневой узел (вверху).
    2. Корневой узел имеет ноль или более дочерних узлов.
    3. Каждый дочерний узел имеет ноль или более дочерних узлов, и так далее.

    У двоичного дерева поиска есть два дополнительных свойства:

    1. Каждый узел имеет до двух дочерних узлов (потомков).
    2. Каждый узел меньше своих потомков справа, а его потомки слева меньше его самого.

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

    Пример реализации на JavaScript

    Временная сложность двоичного дерева поиска

    Упражнения от freeCodeCamp

    Префиксное дерево

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


    Так устроено префиксное дерево

    Каждый узел в языковом префиксном дереве содержит одну букву слова. Чтобы составить слово, нужно следовать по ветвям дерева, проходя по одной букве за раз. Дерево начинает ветвиться, когда порядок букв отличается от других имеющихся в нем слов или когда слово заканчивается. Каждый узел содержит букву (данные) и булево значение, которое указывает, является ли он последним в слове.

    Посмотрите на иллюстрацию и попробуйте составить слова. Всегда начинайте с корневого узла вверху и спускайтесь вниз. Это дерево содержит следующие слова: ball, bat, doll, do, dork, dorm, send, sense.

    Пример реализации на JavaScript

    Упражнения от freeCodeCamp

    Двоичная куча

    Двоичная куча — ещё одна древовидная структура данных. В ней у каждого узла не более двух потомков. Также она является совершенным деревом: это значит, что в ней полностью заняты данными все уровни, а последний заполнен слева направо. 


    Так устроены минимальная и максимальная кучи

    Двоичная куча может быть минимальной или максимальной. В максимальной куче ключ любого узла всегда больше ключей его потомков или равен им. В минимальной куче всё устроено наоборот: ключ любого узла меньше ключей его потомков или равен им.

    Порядок уровней в двоичной куче важен, в отличие от порядка узлов на одном и том же уровне. На иллюстрации видно, что в минимальной куче на третьем уровне значения идут не по порядку: 10, 6 и 12.

    Пример реализации на JavaScript

    Временная сложность двоичной кучи

    Упражнения от freeCodeCamp

    Граф

    Графы — это совокупности узлов (вершин) и связей между ними (рёбер). Также их называют сетями.

    По такому принципу устроены социальные сети: узлы — это люди, а рёбра — их отношения.

    Графы делятся на два основных типа: ориентированные и неориентированные. У неориентированных графов рёбра между узлами не имеют какого-либо направления, тогда как у рёбер в ориентированных графах оно есть.

    Чаще всего граф изображают в каком-либо из двух видов: это может быть список смежности или матрица смежности. 


    Граф в виде матрицы смежности

    Список смежности можно представить как перечень элементов, где слева находится один узел, а справа — все остальные узлы, с которыми он соединяется.

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

    Существуют специальные алгоритмы для просмотра рёбер и вершин в графах — так называемые алгоритмы обхода. К их основным типам относят поиск в ширину (breadth-first search) и в глубину (depth-first search). Как вариант, с их помощью можно определить, насколько близко к корневому узлу находятся те или иные вершины графа. В видео ниже показано, как на JavaScript выполнить поиск в ширину.

    Пример реализации на JavaScript

    Временная сложность списка смежности (графа)

    Упражнения от freeCodeCamp

    Узнать больше

    Если до этого вы никогда не сталкивались с алгоритмами или структурами данных, и у вас нет какой-либо подготовки в области ИТ, лучше всего подойдет книга Grokking Algorithms. В ней материал подан доступно и с забавными иллюстрациями (их автор — ведущий разработчик в Etsy), в том числе и по некоторым структурам данных, которые мы рассмотрели в этой статье.  

    Читать еще: «Обзор профессии Data Scientist»

    Мнение автора и редакции может не совпадать. Хотите написать колонку для «Нетологии»? Читайте наши условия публикации.

    Структуры данных I: Списки | статьи о программировании mkdev

    Эта статья начинает серию, посвящённую структурам данных, разбираемым через "оптику" JavaScript и функционального программирования.

    Мотивация

    Зачем вообще программисту и, в частности, JS-разработчику данная тема? С моей точки зрения, специалист начального уровня вполне может без неё обойтись. Хотя в серьёзных технических ВУЗах как давали так и дают структуры данных именно первокурсникам.

    Дело в том, что, с определённого момента, вы сами неизбежно выйдете на эту тему. Окажется, что тот же Angular базируется на библиотеке реактивного программирования RxJS, попытка разобраться в исходниках которой инициирует у вас фазу депрессии. Вам будет понятна каждая строчка, но что вообще происходит – будет оставаться загадкой, сколько бы времени вы ни сидели над кодом.

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

    Для того-же RxJS минимальное дерево знаний выглядит так (сверху-вниз):

    Computer Science              Asynchronisity
    ---------------------         -------------------------------
    Вычисления ->
    Ленивые вычисления ->
    Списки ->                     Событийный цикл ->
    Ленивые списки ->             Асинхронное программирование ->
    
                       Reactivity
                       ---------------------------
                       Потоки ->
                       RxJS API ->
                       Реактивное Программирование
    

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

    Структуры данных являются фундаментальной темой. Совершенно необходимой для полноценного понимания потоков. Потоки же и реактивное программирование, очевидно, выходят в мейнстрим как Фронтенд (Angular, React...), так и Бэкенд (GraphQL, NoSQL...) разработок. Поэтому всё более сложно представить себе специалиста, которого бы не касалась тема данной серии. Она требуется в работе, она требуется в обучении, её спрашивают на собеседованиях.

    Стоит различать два формата технических текстов: туториал и гайд. Туториал подразумевают возможность мгновенного "практического" использования: скопипастил, запустил, что там дальше? Гайд же направлен на изучение, требует самостоятельной проработки и интереса к теме. Оба формата имеют право на жизнь. Однако большинство из нас, имеет строгое предпочтение между ними.

    Данная серия статей, как и все прочие тексты автора, пишется в формате гайда. Поэтому здесь и далее, мы будем подразумевать самоценность тематики, не пытаясь промотивировать каждую строчку примером "практического" использования. Также мы не будем стесняться смены направлений, примеров на других языках и т.д. Примеров кода будет очень много. Но их потребуется прорабатывать самостоятельно. Это не серия для копипасты "работающего кода", это не серия для единоразового чтения.

    В процессе чтения серии вы будете находить всё больше ассоциаций излагаемого материала с вашими текущими знаниями и практиками. К концу серии, у тех кто доберётся туда, на вопрос "Зачем это всё?" появятся собственные варианты ответа.

    План действий

    Насколько это возможно, мы будем избегать педантства, связанного с производительностью и прочими микро-оптимизациями. Вместо этого нас будут интересовать структуры, связи, аналогии, альтернативы и прочие интегральные вещи.

    Так, например, мы будем использовать рекурсии, а не циклы, вопреки отсутствию соответствующих оптимизаций в современном V8. Рекурсия является намного более мощным и выразительным инструментом, чем цикл. Что соответствует установкам данной серии статей.

    Мы будем разбираться в теме через реализацию соответствующей структуры данных "с нуля". Без использования библиотек, за исключением библиотек хелперов типа: Lodash / Ramda. Только в таком варианте мы будем уверены, что в наших знаниях не останется пробелов.

    В первых частях серии мы реализуем обычные и ленивые списки. Затем сравним последние с генераторами. После чего будем готовы рассмотреть потоки. Приблизительный план серии выглядит следующим образом:

    1. Списки
    2. Ленивые списки
    3. Генераторы vs Ленивые списки
    4. Push потоки
    5. Pull потоки
    Списки

    Что такое Cписок (Linked List)? Смотрим Википедию.

    In computer science, a linked list is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence.

    Обязательно прочитайте хотя-бы первые параграфы по указанной ссылке. Однако, имейте в виду, что под массивом там имеется в виду C-подобный массив, фиксированного размера. Массив в JS базируется на хеш-таблицах и имеет другие характеристики.

    Ключевое наблюдение, для нашего текущего разговора, состоит в том, что список – это фундаментальная структура данных, заменяющая массивы во многих языках. Заменяющая, в смысле резервации канонического литерала [] под них. Первое преимущество списка проявляется в паттерн-матчинге (в силу структуры его типа). Это неприменимо к базовому JS, но важно и заслуживает упоминания.

    Следующее преимущество списка – простота, включающая, в т.ч. простоту реализации ленивости на их базе. Под "ленивостью" здесь я имею в виду "по-элементную ленивость". Такие ленивые списки можно рассматривать как синхронные pull потоки, подходящие для описания длинных или бесконечных последовательностей: натуральных чисел, чисел фибоначчи и т.д.

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

    Недостатками списков являются: O(n) вставка в конец и O(n) поиск / индексация. См. сравнительную таблицу.

    Впрочем, не будем углубляться в теорию. Справочные данные будут представлять интерес после изучения материала текущей статьи, а не перед ним.

    Поэтому, без дальнейших промедлений, рассмотрим простейший ссылочный список:

    let A3 = null
    let A2 = {value: "a2", next: A3}
    let A1 = {value: "a1", next: A2}
    let A0 = {value: "a0", next: A1}
    
    console.log(A0) // {value: "a0", next: [Object]}
    console.log(A0.next) // {value: "a1", next: [Object]}
    console.log(A0.next.next) // {value: "a2", next: [Object]}
    console.log(A0.next.next.next) // null
    

    Или с другого ракурса:

    let A0 = {
      value: "a0",
      next: {
        value: "a1",
        next: {
          value: "a2",
          next: null
        }
      }
    }
    

    – Нет ли каких-либо ограничений на вложенность? – можете спросить вы. И да и нет. Парсеры часто ограничены каким то числом уровней, например 512-ю. Но вы не будете описывать бесконечные и даже просто длинные последовательности литералами. Вы создадите генеративные функции, и тогда эти "уровни вложенности" окажутся не ограниченными ссылками, что очевидно из первого примера.

    Что касается JSON, то невозможно представить бесконечный поток конечным файлом. Зато можно представить каждый элемент потока отдельным JSON объектом. И полагаться на время, а не пространство для стриминга. Мы вернёмся к этому вопросу позднее.

    Базовая функция для ссылочных списков традиционно называется Cons (от "constructor"). Вы встретите это имя во многих источниках. Почему не List? Не могу говорить за McCarthy, который, вероятно, придумал термин, но Cons описывает один элемент, а список является производной. Выглядит обосновано, как по мне.

    function Cons(value, next) {
      return {value, next}
    }
    

    Несколько улучшает ситуацию:

    let A3 = null
    let A2 = Cons("a2", A3)
    let A1 = Cons("a1", A2)
    let A0 = Cons("a0", A1)
    

    Мы будем использовать null для обозначения пустой cons ячейки (оригинальное имя), для краткости. В языках со статической типизацией это, обычно, отдельный тип-синглтон, называемый, например, Nil. Возможности типизации в базовом JS — ограничены, равно как и представление о ней у среднестатистического JS-разработчика. Пропустим некоторые детали.

    Структура данных определяется через свои поведения. Наша следующая задача состоит в реализации базовых функций над списками. Однако, для верификации их результатов, было бы неплохо иметь парочку доп. утилит. От console.log толку не много. Давайте реализуем toArray:

    let toArray = (xs) => {
      if (xs) {
        return [xs.value].concat(toArray(xs.next))
      } else {
        return []
      }
    }
    
    console.log(toArray(A0)) // ["a0", "a1", "a2"]
    

    и вспомогательную функцию log:

    let logList = (list) => console.log(toArray(list))
    
    logList(A0) // ["a0", "a1", "a2"]
    

    Мы уже имеем prepend под псевдонимом Cons. Что насчёт append? Как мы увидели ранее, это нежелательная операция для списка. Для бесконечных списков добавление в конец вообще невозможно.

    Как бы то ни было, вот append:

    let append = (x, xs) => {
      if (xs) {
        return Cons(xs.value, append(x, xs.next))
      } else {
        return Cons(x, null)
      }
    }
    
    logList(append("a3", A0)) // ["a0", "a1", "a2", "a3"]
    

    Пересобираем список через Cons(xs.value, append(x, xs.next)), а затем создаём новый завершающий элемент через Cons(x, null).

    Теперь concat:

    let concat = (xs, ys) => {
      if (xs) {
        return Cons(xs.value, concat(xs.next, ys))
      } else {
        return ys
      }
    }
    
    logList(concat(A0, A0)) // ["a0", "a1", "a2", "a0", "a1", "a2"]
    

    И, наконец, map:

    let map = (fn, xs) => {
      if (xs) {
        return Cons(fn(xs.value), map(fn, xs.next))
      } else {
        return null
      }
    }
    
    logList(map(x => x + "!", A0)) // ["a0!", "a1!", "a2!"]
    

    В следующей части мы реализуем ленивые версии всего вышеперечисленного.

    P.S.

    Сознаюсь в лёгком читинге. Сначала я как-бы говорю о правильных рекурсиях, а затем реализую map и другие функции в не-хвостовом стиле.

    Реалистичный (не-ленивый) map выглядит более мудрёно:

    let map2 = (fn, xs) => {
      return (function go(acc, xs) {
        if (xs) {
          return go(Cons(fn(xs.value), xs.next))
        } else {
          return acc
        }
      })(null, xs)
    }
    

    Моё оправдание состоит в том, что немногие JS-программисты вообще слышали о хвостовой рекурсии. По этой причине, а также по причине невозможности протестировать эти вещи в данный момент, я опускаю излишнюю сложность. Виды рекурсий совершенно точно тянут на отдельную статью (если не серию).

    Ссылки

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

    mutable и immutable структуры данных

    Как избежать мутаций в JavaScript с помощью неизменных структур данных.

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

    Чтобы продемонстрировать разницу между изменчивостью и неизменностью, представь, что ты пьешь воду из стакана. Если стакан изменчив, то когда ты пьешь, ты сохраняешь тот же стакан, но меняешь количество воды в нем. Однако, если стакан неизменчив, когда ты пьешь, то получаешь совершенно новый, идентичный стакан, содержащий правильное количество оставшейся воды. Возможно, это странный способ представить себе действие, но создание новых структур данных делает наши методы чистыми и поточно-ориентированными, что является преимуществом функционального программирования.

    mutable структуры данных могут быть изменены после создания, а immutable - нет. Мутации могут рассматриваться как побочные эффекты в наших приложениях.

    mutable и immutable данные в массиве

    Давай создадим массив a с несколькими значениями. Мы присвоим переменную a к b. Что создаст новую переменную b с той же ссылкой на значения, что и a. Мы можем убедиться в этом, используя проверку со строгим равенством, поскольку она будет проверять, ссылки на значения.

    const a = [1, 2, 3];
    const b = a;
    console.log(a === b); 

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

    const a = [1, 2, 3];
    const b = a;
    b.push(4);
    console.log(a); 

    Когда мы вносим изменения в одну переменную, то, фактически, вносим изменения и в другую. Это может вызвать проблемы в коде. Функциональность, которая работает на b, изменит a, даже если мы не собирались этого делать. То же самое относится и к объектам.

    Например, у нас есть объект a, со свойством name и значением Alex. Если мы присвоим переменную a к b и внесем изменения в b, переназначив name с Alex на Julia, и выведем в консоль a.name, то увидим, что оно обновилось.

    const a = { name: "Alex" };
    const b = a;
    b.name = "Julia";
    console.log(a.name); 

    Это является проблемой для функционального программирования, потому что оно нарушает чистоту наших функций. Когда мы делаем обновления данных, мы хотим вернуть совершенно новую структуру данных, которая содержит все элементы предыдущего состояния, а также наши обновления.

    Например, метод push - это мутация в массиве. Как мы видели, он изменяет все ссылки на тот же массив. Тем не менее, мы можем создать immutable функцию высшего порядка push. Она получит value, затем array, и вернет новый массив, используя оператор распространения spread для создания клона, а затем поместит значение в него.

    Более подробнее о функциях высшего порядка.

    const push = value => array => {
      const clone = [...array];
      clone.push(value);
      return clone;
    };

    Если мы снова создадим массив const a = [1, 2, 3], и создадим второй массив, поместив в него значение с помощью нашей новой функции - push(), то увидим, что a не был изменен. Мы также можем увидеть, что a и b не равны, так как они являются ссылками на разные массивы. В данном примере, при вызове push(4)(a) - value равен 4, а array равен массиву a.

    const push = value => array => {
      const clone = [...array];
      clone.push(value);
      return clone;
    };
    
    const a = [1, 2, 3];
    const b = push(4)(a);
    
    console.log(a); 
    console.log(b); 
    console.log(a === b); 

    mutable и immutable данные в объекте

    Мы можем создать аналогичные функции для обработки изменений в объектах. Для этого создадим два класса MutableGlass и ImmutableGlass.

    Мы создадим метод takeDrink для них обоих и посмотрим на разницу между mutable и immutable обработкой. Начнем с MutableGlass. У нас будет constructor, который принимает content, amount и присваивает this.content к content, а this.amount к amount.

    class MutableGlass {
      constructor(content, amount) {
        this.content = content;
        this.amount = amount;
      }
    }

    Затем мы создадим метод takeDrink, который будет принимать value. Он будет обновлять this.amount напрямую и вернет this экземпляра класса. Мы используем Math.max(this.amount - value, 0) чтобы гарантировать, что мы никогда не получим значение меньше нуля в нашем случае.

    class MutableGlass {
      constructor(content, amount) {
        this.content = content;
        this.amount = amount;
      }
    
      takeDrink(value) {
        this.amount = Math.max(this.amount - value, 0);
        return this;
      }
    }

    Мы создадим стакан mg1 через new MutableGlass и передадим ему в качестве content - 'water', а amount - 100.

    class MutableGlass {
      constructor(content, amount) {
        this.content = content;
        this.amount = amount;
      }
    
      takeDrink(value) {
        this.amount = Math.max(this.amount - value, 0);
        return this;
      }
    }
    
    const mg1 = new MutableGlass("water", 100);

    Теперь, если мы сравним значения, путем проверки со строгим равенством, после вызова takeDrink, то увидим, что они равны. Это имеет смысл, так как они ссылаются на один и тот же экземпляр.

    const mg1 = new MutableGlass("water", 100);
    const mg2 = mg1.takeDrink(20);
    console.log(mg1 === mg2); 
    console.log(mg1.amount === mg2.amount); 

    Это происходит потому, что мы изменяем значение напрямую, меняя структуру данных после её создания.

    Теперь мы создадим ImmutableGlass. constructor будет выглядеть точно так же. Мы сделаем метод takeDrink, который также принимает value, но здесь происходит изменение.

    Когда мы вызываем метод takeDrink, то вместо того, чтобы вернуть тот же стакан, который был у нас раньше, мы возвращаем новый стакан с новым content и amount. Чтобы сделать это, мы просто создаем new ImmutableGlass, передавая content и amount.

    class ImmutableGlass {
      constructor(content, amount) {
        this.content = content;
        this.amount = amount;
      }
    
      takeDrink(value) {
        return new ImmutableGlass(this.content, Math.max(this.amount - value, 0));
      }
    }

    Теперь, если мы сравним значения после вызова takeDrink, то увидим, что они не равны. Так как ig1.amount не изменилось, а вот ig2.amount поменяло свое значение.

    const ig1 = new ImmutableGlass("water", 100);
    const ig2 = ig1.takeDrink(20);
    console.log(ig1 === ig2); 
    console.log(ig1.amount === ig2.amount); 
    console.log(ig1.amount); 
    console.log(ig2.amount); 

    типов данных и структур данных JavaScript - JavaScript

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

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

      пусть foo = 42;
    foo = 'бар';
    foo = true;
      

    Последний стандарт ECMAScript определяет девять типов:

    • Шесть типов данных , которые являются примитивами, проверяются оператором typeof:
      • undefined: typeof instance === " undefined "
      • Boolean: typeof instance === "boolean"
      • Number: typeof instance === "number"
      • Строка: typeof instance === "строка"
      • BigInt: typeof instance === "bigint"
      • Symbol: typeof instance === "symbol"
    • Строительный Типы :
      • Объект: typeof instance === " объект " .Специальные не-данные, но Structural тип для любого созданного экземпляра объекта, также используемого в качестве структур данных: новый Object , новый Array , новый Map , новый Set , новый WeakMap , новый WeakSet , новый Date и почти все, что сделано с новым ключевым словом;
      • Функция: структура без данных, хотя она также отвечает за typeof operator: typeof instance === " function " .Это просто специальное сокращение для функций, хотя каждый конструктор функции является производным от конструктора объекта.
    • Структурный корень Примитив:
      • null : typeof instance === " объект " . Специальный примитивный тип, имеющий дополнительное использование для своего значения: если объект не унаследован, отображается null ;

    Имейте в виду, что единственная ценная цель использования оператора типа или - это проверка типа данных.Если мы хотим проверить какой-либо структурный тип, производный от Object, бессмысленно использовать для этого тип , так как мы всегда будем получать «объект» . Правильный способ проверить, какой тип объекта мы используем, - это ключевое слово instanceof . Но даже в этом случае могут быть заблуждения.

    Как мы видим, значение каждого примитивного типа очевидно, за исключением undefined и null, которые почти одинаковы. Это происходит потому, что понятие Времени жестко связано с назначением алгоритмов.Мы можем указать на то, чего еще не существует или больше не существует: undefined . Но когда мы хотим иметь возможность представить что-то существующее как пустое, мы должны изобрести другое ключевое слово. И это то, что означает null : начало структурного смысла.

    Все типы, кроме объектов, определяют неизменяемые значения (то есть значения, которые нельзя изменить). Например (и в отличие от C), строки неизменяемы. Мы называем значения этих типов « примитивных значений ».

    Логический тип

    Логический тип представляет логический объект и может иметь два значения: true и false . См. Boolean и Boolean для более подробной информации.

    Тип Null

    Тип Null имеет ровно одно значение: null . См. null и Null для получения более подробной информации.

    Неопределенный тип

    Переменная, которой не было присвоено значение, имеет значение undefined . См. undefined и Undefined для более подробной информации.

    Числовой тип

    ECMAScript имеет два встроенных числовых типа: Number и BigInt (см. Ниже).

    Тип Number представляет собой значение IEEE 754 в 64-битном двоичном формате двойной точности (числа от - (2 53 - 1) до 2 53 - 1). В дополнение к представлению чисел с плавающей запятой тип числа имеет три символических значения: + Infinity , -Infinity и NaN N или N »).

    Чтобы проверить наибольшее доступное значение или наименьшее доступное значение в пределах ± Infinity , вы можете использовать константы Number.MAX_VALUE или Number.MIN_VALUE .

    Начиная с ECMAScript 2015, вы также можете проверить, находится ли число в диапазоне чисел с плавающей запятой двойной точности, используя Number.isSafeInteger () , а также Number.MAX_SAFE_INTEGER и Number.MIN_SAFE_INTEGER .

    За пределами этого диапазона целые числа в JavaScript больше не безопасны и будут представлять собой приближение значения двойной точности с плавающей запятой.

    Числовой тип имеет только одно целое число с двумя представлениями: 0 представляется как -0 и +0 . ( 0 - это псевдоним для +0 .)

    На практике это почти не влияет. Например, +0 === -0 - это истинный . Однако вы можете заметить это, если разделите на ноль:

     > 42 / +0
    бесконечность
    > 42 / -0
    -Бесконечность
      

    Хотя число часто представляет только свое значение, JavaScript предоставляет двоичных (побитовых) операторов .

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

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

    Тип BigInt

    Тип BigInt - это числовой примитив в JavaScript, который может представлять целые числа с произвольной точностью. С помощью BigInt s вы можете безопасно хранить и обрабатывать большие целые числа даже сверх безопасного целочисленного предела для Number s.

    Объект BigInt создается добавлением n в конец целого числа или вызовом конструктора.

    Вы можете получить наиболее безопасное значение, которое может быть увеличено на Number s, используя константу Number.MAX_SAFE_INTEGER . С введением BigInt s вы можете работать с номерами, выходящими за рамки Number.MAX_SAFE_INTEGER .

    Этот пример демонстрирует, где увеличение числа .MAX_SAFE_INTEGER возвращает ожидаемый результат:

     > const x = 2n ** 53n;
    99254740992n
    > const y = x + 1n;
    99254740993n
      

    Вы можете использовать операторы + , * , - , ** и % с BigInt s - точно так же, как с Number s. BigInt не совсем равно Number , но примерно так.

    BigInt ведет себя как Number в случаях, когда он конвертируется в Boolean : if , || , && , Логическое значение , ! .

    BigInt s не могут использоваться взаимозаменяемо с Number s. Вместо этого будет выдано TypeError .

    Тип строки

    Тип JavaScript String используется для представления текстовых данных.Это набор «элементов» 16-битных целочисленных значений без знака. Каждый элемент в строке занимает позицию в строке. Первый элемент имеет индекс 0 , следующий - индекс 1 и так далее. Длина строки - это количество элементов в ней.

    В отличие от некоторых языков программирования (например, C), строки JavaScript неизменяемы. Это означает, что после создания строки ее невозможно изменить.

    Тем не менее, все еще возможно создать другую строку на основе операции с исходной строкой.Например:

    • Подстрока оригинала, выбирая отдельные буквы или используя String.substr () .
    • Конкатенация двух строк с использованием оператора конкатенации ( + ) или String.concat () .
    Остерегайтесь "строкового набора" кода!

    Может возникнуть соблазн использовать строки для представления сложных данных. Это дает краткосрочные выгоды:

    • Сложные строки легко строить с помощью конкатенации.
    • Строки легко отлаживать (то, что вы видите напечатанным, всегда то, что находится в строке).
    • Строки являются общим знаменателем многих API (поля ввода, значения локального хранилища, ответы XMLHttpRequest, при использовании responseText и т. Д.), И может возникнуть соблазн работать только со строками.

    Согласно соглашениям, в строке можно представить любую структуру данных. Это не значит, что это хорошая идея. Например, с помощью разделителя можно имитировать список (в то время как массив JavaScript был бы более подходящим).К сожалению, когда разделитель используется в одном из элементов «списка», то список не работает. Можно выбрать escape-символ и т. Д. Все это требует соглашений и создает ненужную нагрузку на обслуживание.

    Используйте строки для текстовых данных. При представлении сложных данных анализирует строк и использует соответствующую абстракцию.

    Тип символа

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

    Дополнительные сведения см. В разделе «Символ» и объектная оболочка «Символ » в JavaScript.

    В информатике объект - это значение в памяти, на которое, возможно, ссылается идентификатор.

    Свойства

    В JavaScript объекты можно рассматривать как набор свойств. С помощью синтаксиса литерала объекта инициализируется ограниченный набор свойств; затем свойства можно добавлять и удалять. Значения свойств могут быть значениями любого типа, включая другие объекты, что позволяет создавать сложные структуры данных.Свойства идентифицируются с использованием ключей значений. Ключ Значение является либо строковым, либо символьным значением.

    Существует два типа свойств объекта, которые имеют определенные атрибуты: свойство data и свойство accessor .

    Примечание: Каждое свойство имеет соответствующих атрибутов. Атрибуты используются внутри движком JavaScript, поэтому вы не можете получить к ним прямой доступ. Вот почему атрибуты указаны в двойных квадратных скобках, а не в одинарных.

    Подробнее см. Object.defineProperty () .

    Свойство данных

    Связывает ключ со значением и имеет следующие атрибуты:

    Атрибуты свойства данных
    Атрибут Тип Описание Значение по умолчанию
    [[Значение]] Любой тип JavaScript Значение, полученное при доступе к свойству. неопределенный
    [[Доступно для записи]] Логическое значение Если false , свойство [[Value]] не может быть изменено. ложный
    [[Enumerable]] Логическое значение

    Если true , свойство будет перечислено в циклах for ... in.
    См. Также перечислимость и владение свойствами.

    ложный
    [[настраивается]] Логическое значение Если false , свойство не может быть удалено, не может быть изменено на свойство средства доступа, а атрибуты, отличные от [[Value]] и [[Writable]], не могут быть изменены. ложный
    Устаревшие атрибуты (в ECMAScript 3, переименованные в ECMAScript 5)
    Атрибут Тип Описание
    Только чтение Логическое значение Обратное состояние атрибута ES5 [[Writable]].
    DontEnum Логическое значение Обратное состояние атрибута ES5 [[Enumerable]].
    Не удалять Логическое значение Обратное состояние атрибута ES5 [[Configurable]].
    Свойство аксессуара

    Связывает ключ с одной из двух функций доступа ( получает и устанавливает ) для извлечения или сохранения значения и имеет следующие атрибуты:

    Атрибуты свойства доступа
    Атрибут Тип Описание Значение по умолчанию
    [[Get]] Функциональный объект или undefined Функция вызывается с пустым списком аргументов и извлекает значение свойства всякий раз, когда выполняется доступ к значению.
    См. Также получить .
    неопределенный
    [[Набор]] Функциональный объект или undefined Функция вызывается с аргументом, содержащим присвоенное значение, и выполняется всякий раз, когда происходит попытка изменения указанного свойства.
    См. Также набор .
    неопределенный
    [[Enumerable]] Логическое значение Если истинно , свойство будет перечислено для...в петлях. ложный
    [[настраивается]] Логическое значение Если false , свойство не может быть удалено и не может быть изменено на свойство данных. ложный

    «Обычные» объекты и функции

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

    Функции - это обычные объекты с дополнительной возможностью вызова .

    Даты

    При представлении дат лучше всего использовать встроенную утилиту Date в JavaScript.

    Индексированные коллекции: массивы и типизированные массивы

    Массивы - это обычные объекты, для которых существует определенная взаимосвязь между свойствами с целочисленным ключом и свойством length .

    Кроме того, массивы наследуются от Array.prototype , который предоставляет им несколько удобных методов для управления массивами. Например, indexOf (поиск значения в массиве) или push (добавление элемента в массив) и т. Д. Это делает массивы идеальным кандидатом для представления списков или наборов.

    Типизированные массивы

    являются новыми для JavaScript с ECMAScript 2015 и представляют собой массивное представление базового буфера двоичных данных. Следующая таблица помогает определить эквивалентные типы данных C:

    Int8Array -128 до 127 1 8-битовое целое число со знаком с дополнением до двух байт int8_t
    Uint8Array 0 до 255 1 8-битовое целое число без знака октет uint8_t
    Uint8ClampedArray 0 до 255 1 8-битовое целое число без знака (фиксировано) октет uint8_t
    Int16Array -32768 до 32767 2 16-разрядное целое число со знаком с дополнением до двух короткий int16_t
    Uint16Array 0 до 65535 2 16-разрядное целое число без знака короткое без знака uint16_t
    Int32Array -2147483648 до 2147483647 4 32-разрядное целое число со знаком с дополнением до двух длинный int32_t
    Uint32Array 0 до 4294967295 4 32-разрядное целое число без знака длинное без знака uint32_t
    Float32Array 1.2 × 10 -38 до 3,4 × 10 38 4 32-битное число с плавающей запятой IEEE (7 значащих цифр, например, 1,1234567 ) неограниченное поплавок поплавок
    Float64Array 5,0 × 10 -324 до 1,8 × 10 308 8 64-битное число с плавающей запятой IEEE (16 значащих цифр e.г., 1,123 ... 15 ) неограниченный двойной двойной
    BigInt64Array -2 63 до 2 63 -1 8 64-битное целое число со знаком с дополнением до двух bigint int64_t (длинный длинный со знаком)
    BigUint64Array 0 до 2 64 -1 8 64-битное целое число без знака bigint uint64_t (длинное беззнаковое длинное)

    Коллекции с ключами: Карты, Наборы, WeakMaps, WeakSets

    Эти структуры данных, представленные в ECMAScript Edition 6, принимают ссылки на объекты в качестве ключей. Set и WeakSet представляют набор объектов, а Map и WeakMap связывают значение с объектом.

    Разница между Map s и WeakMap s заключается в том, что в первом случае ключи объектов могут быть пронумерованы. Это позволяет оптимизировать сборку мусора в последнем случае.

    Можно реализовать Map s и Set s в чистом ECMAScript 5. Однако, поскольку объекты нельзя сравнивать (например, в смысле < «меньше чем»), производительность поиска обязательно будет линейной. .Их собственные реализации (включая WeakMap s) могут иметь производительность поиска, которая является приблизительно логарифмической к постоянному времени.

    Обычно для привязки данных к узлу DOM можно установить свойства непосредственно на объекте или использовать атрибуты data- * . Обратной стороной этого является то, что данные доступны любому сценарию, запущенному в одном контексте. Map s и WeakMap s упрощают частную привязку данных к объекту.

    Структурированные данные: JSON

    JSON ( J ava S cript O bject N otation) - это облегченный формат обмена данными, полученный из JavaScript, но используемый многими языками программирования.JSON создает универсальные структуры данных.

    Подробнее см. JSON и JSON .

    Больше объектов в стандартной библиотеке

    JavaScript имеет стандартную библиотеку встроенных объектов.

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

    Оператор type of может помочь вам найти тип вашей переменной.

    Пожалуйста, прочтите справочную страницу для получения более подробной информации и крайних случаев.

    Алгоритмы JavaScript и структуры данных

    Значок JavaScript

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

    Изучив основы, вы примените эти знания, создав алгоритмы для управления строками, факторизации чисел и даже расчета орбиты Международной космической станции.

    Попутно вы также изучите два важных стиля или парадигмы программирования: объектно-ориентированное программирование (ООП) и функциональное программирование (ФП).

    Курсы

    JavaScript - это язык сценариев, который можно использовать для интерактивности веб-страниц. Это одна из основных технологий Интернета, наряду с HTML и CSS, которая поддерживается всеми современными браузерами.

    В этом курсе вы изучите фундаментальные концепции программирования на JavaScript. Вы начнете с основных структур данных, таких как числа и строки. Затем вы научитесь работать с массивами, объектами, функциями, циклами, операторами if / else и т. Д.

    Развернуть курсы

    Не пройден Не пройден0 / 111

    ECMAScript, или ES, является стандартизированной версией JavaScript.Поскольку все основные браузеры следуют этой спецификации, термины ECMAScript и JavaScript взаимозаменяемы.

    Большая часть JavaScript, который вы изучили до этого момента, был в ES5 (ECMAScript 5), который был завершен в 2009 году. Хотя вы все еще можете писать программы на ES5, JavaScript постоянно развивается, и каждый год выпускаются новые функции.

    ES6, выпущенный в 2015 году, добавил в язык много новых мощных функций. В этом курсе вы познакомитесь с этими новыми функциями, включая let и const , стрелочные функции, классы, обещания и модули.

    Расширить курсы

    Не пройдено Не пройдено0 / 31

    Регулярные выражения, часто сокращаемые до «regex» или «regexp», - это шаблоны, которые помогают программистам сопоставлять, искать и заменять текст. Регулярные выражения очень эффективны, но их трудно читать, потому что они используют специальные символы для более сложных и гибких сопоставлений.

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

    Развернуть курсы

    Не пройден Не пройден0 / 33

    Отладка - это процесс прохождения вашего кода, поиска проблем и их устранения.

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

    В этом курсе вы узнаете, как использовать консоль JavaScript для отладки программ и предотвращения распространенных проблем до того, как они возникнут.

    Развернуть курсы

    Не пройден Не пройден0 / 12

    Данные могут быть сохранены и доступны разными способами. Вы уже знаете некоторые распространенные структуры данных JavaScript - массивы и объекты.

    В этом курсе базовых структур данных вы узнаете больше о различиях между массивами и объектами и о том, какие из них использовать в разных ситуациях. Вы также узнаете, как использовать полезные методы JS, такие как splice () и Object.keys () , для доступа к данным и управления ими.

    Развернуть курсы

    Не пройден Не пройден0 / 20

    Алгоритм - это серия пошаговых инструкций, описывающих, как что-то делать.

    Чтобы написать эффективный алгоритм, нужно разбить проблему на более мелкие части и тщательно продумать, как решить каждую часть с помощью кода.

    В этом курсе вы изучите основы алгоритмического мышления, написав алгоритмы, которые делают все, от преобразования температуры до обработки сложных 2D-массивов.

    Развернуть курсы

    Не пройден Не прошел0 / 16

    ООП, или объектно-ориентированное программирование, является одним из основных подходов к процессу разработки программного обеспечения. В ООП объекты и классы используются для организации кода для описания вещей и того, что они могут делать.

    В этом курсе вы изучите основные принципы ООП в JavaScript, включая ключевое слово и , цепочки прототипов, конструкторы и наследование.

    Расширить курсы

    Не пройден Не пройден0 / 26

    Функциональное программирование - еще один популярный подход к разработке программного обеспечения.В функциональном программировании код разбит на более мелкие базовые функции, которые можно комбинировать для создания сложных программ.

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

    Развернуть курсы

    Не пройден Не пройден0 / 24

    Теперь, когда вы знаете основы алгоритмического мышления, наряду с ООП и функциональным программированием, проверьте свои навыки с помощью задач по написанию промежуточных алгоритмов.

    Развернуть курсы

    Не пройден Не пройден0 / 21

    Пришло время применить свои новые навыки работы с JavaScript. Эти проекты похожи на задачи по написанию сценариев алгоритмов, которые вы делали раньше, но намного сложнее.

    Завершите эти 5 проектов JavaScript, чтобы получить сертификацию алгоритмов JavaScript и структур данных.

    Сертификация алгоритмов и структур данных JavaScript

    Не пройден Не пройден

    Просмотрите другие наши бесплатные сертификаты (мы рекомендуем делать это по порядку)

    Как писать структуры данных и алгоритмы в JavaScript

    Существует множество различных реализаций структур данных и алгоритмов на разных языках программирования.Эта статья посвящена тому, чтобы помочь вам изучить структуры данных и алгоритмы с помощью JavaScript.

    Вы узнаете об основных типах данных и структурах данных по умолчанию в JavaScript, которые помогут вам создавать очереди, связанные списки, графики, деревья и более сложные реализации. Освоив эти структуры данных, вы затем узнаете, как создавать свои собственные алгоритмы на JavaScript, от простых арифметических до более сложных алгоритмов сортировки и поиска.

    Типы базовых структур данных с использованием JavaScript

    JavaScript - это язык программирования, на котором построена сеть.Большинство веб-приложений работают на JavaScript или фреймворках, построенных на его основе, от почти универсальной библиотеки JQuery до комбинации React.js / Node.js, которая теперь поддерживает сложные инструменты в Интернете. В мире существует не менее 70 миллионов сайтов, использующих JQuery.

    JavaScript слабо типизирован и динамичен. Существует семь так называемых примитивных типов данных по умолчанию, которые мы можем определить как разные типы данных. С этими типами данных не связаны переменные - любую переменную JavaScript можно быстро переключать между тем или иным типом.Они составляют основу статических структур данных в JavaScript.

    Примитивный тип данных JavaScript 1: логические значения

    Логическое значение - это двоичная логическая переменная в JavaScript. Он вернет либо True, либо False, в зависимости от некоторого базового условия. Логические значения часто полезны для работы с состояниями If или циклами For / While: они могут определять состояние, в котором что-то продолжает выполняться или нет.

    Примитивный тип данных JavaScript 2: строки

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

    Примитивный тип данных JavaScript 3: Null

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

    Примитивный тип данных JavaScript 4: не определен

    Неопределенная переменная автоматически присваивается любой переменной, которую мы определяем и которая только что была объявлена.Например, если мы определим «var springboard» в JavaScript без какого-либо объявления того, что это за переменная, она вернется как неопределенный тип данных.

    Примитивный тип данных JavaScript 5: числа

    Числа - это один из двух способов хранения последовательностей целых чисел в JavaScript. Используя 64 бита, он может представлять числа от 2 до 53-й степени как в отрицательной, так и в положительной форме. Также есть три нецелочисленных значения, которые могут быть представлены в Numbers: положительная бесконечность, отрицательная бесконечность и NaN, что означает «Не число.«Существует определенный диапазон, в котором целые числа в JavaScript небезопасны и станут приближением - это можно проверить с помощью метода Number.isSafeInteger (). Это причина того, что у нас есть второй тип данных, который имеет дело с целыми числами в JavaScript: BigInt.

    Примитивный тип данных JavaScript 6: BigInt

    Числовой тип BigInt позволяет нам представлять целые числа, которые выходят за безопасный предел Numbers, т.е. за пределы 2 в степени 53. Этот тип данных позволяет нам работать с очень большими числами в JavaScript.Переменные BigInt во многом похожи на числовые переменные, но их нельзя использовать для работы с числовыми переменными. Ошибка TypeError будет выдана, если вы попытаетесь объединить переменные BigInt и Numbers.

    Примитивный тип данных JavaScript 7: символ

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

    Реализация структур данных с помощью JavaScript

    Определив эти примитивные типы данных, теперь мы можем работать над некоторыми реализациями структур данных, специфичными для JavaScript.Структуры данных - это способ хранения и организации только что описанных примитивов данных, чтобы к ним можно было эффективно обращаться и использовать в алгоритмах.

    Структура данных JavaScript, тип 1: массивы

    Массивы - это последовательности примитивных типов данных, похожие на список. В JavaScript есть две распространенные объектно-ориентированные реализации объектов, подобных массиву: стеки и очереди, а также специально определенный объект массива. Стеки и очереди отличаются от точного определения массивов в других языках программирования тем, как добавляются или удаляются объекты.

    Очереди - это FIFO (первый пришел - первый ушел), а стеки - LIFO (последний пришел - первый ушел). Вы можете думать об очереди как о очереди людей, идущих в магазин, где первый в очереди попадает в магазин, а о стеке как о стопке файлов, причем последний, помещенный в стек, является первым из них. .

    И очереди, и стеки дают возможность отображать каждый тип данных, хранящийся в массиве, а также срезать и «просматривать» определенные элементы. Это также верно для типа массива JavaScript, который является специально определенным объектом в JavaScript.

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

    Тип структуры данных JavaScript 2: Связанные узлы

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

    Существует несколько типов: от односвязных списков, двусвязных списков (которые связывают хвост с головой, позволяя нам перемещаться вперед и назад по различным типам данных) до деревьев и графов. Деревья соединяют родителей с несколькими дочерними узлами, в отличие от связанных списков, которые соединяют одного родителя с одним дочерним.Графики позволяют подключать несколько родительских узлов к нескольким дочерним узлам. Вот реализация связанного списка.

    Тип структуры данных JavaScript 3: хеш-таблицы

    Хеш-таблица - это структура данных, подобная словарю, где ключи связаны со значениями. Хеш-таблицы отлично подходят для быстрого поиска и изменения данных, хотя приведенные выше объекты в виде массивов и списков лучше подходят для хранения. Тем не менее, особенно в связи со стремительным ростом объемов данных, хеш-таблицы стали почти повсеместными.Например, популярные базы данных NoSQL, используемые в Интернете, такие как MongoDB и Redis, представляют собой распределенные хэш-таблицы и хранилища ключей / значений. Это пример реализации хеш-таблицы в JavaScript.

    Реализация алгоритмов с использованием JavaScript

    Теперь, когда мы закончили изучение типов данных и структур данных, из которых состоит JavaScript, мы рассмотрим различные общие алгоритмы и их уникальные реализации в JavaScript.

    Алгоритм JavaScript 1: алгоритм удвоения (арифметический алгоритм)

    Давайте начнем с простой арифметической функции, которая показывает нам, как выполнить последовательность шагов в JavaScript.Мы возьмем что-нибудь и умножим на два, а затем запишем в нашу консоль. Это требует от нас определения простых переменных и функций.

    Обратите внимание, в конце, что когда мы пытаемся передать строковый тип данных в этот алгоритм, это приводит к типу данных NaN (а не числу).

    Алгоритм JavaScript 2: QuickSort (алгоритм сортировки)

    Распространенная проблема с алгоритмами программирования состоит в том, как отсортировать массивы значений так, чтобы они располагались в некотором логическом порядке, например, от наименьшего до наибольшего целого числа в массиве чисел.QuickSort - это алгоритм сортировки, который может в этом помочь. Используя точку поворота и просматривая подмножества массива, мы можем медленно отсортировать каждый элемент, который меньше, чем точка поворота слева от нее.

    Вот реализация QuickSort на JavaScript.

    Алгоритм JavaScript 3: поиск с переходом (алгоритм поиска)

    Теперь, когда мы отсортировали массив, другой распространенный класс алгоритмов программирования пытается решить проблему поиска, если значение существует в массиве. Используя поиск с переходом, мы стремимся разбить подмножества массива так, чтобы он был более эффективным, чем двоичный поиск, при фильтрации через уже отсортированные массивы.Мы ищем интервал известных больших и меньших элементов, где может быть наше значение поиска.

    Как Springboard помогает изучать структуры данных и алгоритмы с помощью JavaScript?

    Онлайн-курсы по разработке программного обеспечения

    Springboard предназначены для того, чтобы вы получили работу в течение нескольких месяцев после завершения.

    Программа «Карьера в программной инженерии» предназначена для будущих студентов, обладающих базовыми навыками программирования и знанием JavaScript, а также навыками решения проблем и общения.

    Учебная программа для самостоятельного изучения, разработанная ведущим инструктором Колтом Стилом, поможет вам освоить веб-разработку, стандартные инструменты разработчика от Git до терминала и Github, основы SQL и структур данных, а также алгоритмы на Python и JavaScript. Вы узнаете:

    • Промежуточные манипуляции с JavaScript и DOM
    • Как работает Интернет, AJAX и jQuery
    • Современный JavaScript и тестирование
    • Основы Node.js и Express.js и способы создания полнофункциональных приложений с обоими
    • React.js и Redux
    • Структуры данных и алгоритмы в JavaScript

    Готовы переключиться на разработку программного обеспечения?

    Springboard предлагает комплексный учебный курс по разработке программного обеспечения. Вы будете работать с индивидуальным наставником, чтобы изучить ключевые аспекты интерфейсной веб-разработки, серверной веб-разработки, баз данных, а также структур данных и алгоритмов. Модули включают учебные ресурсы, практические упражнения, проекты и курсовую работу, связанную с карьерой.

    Посетите программу «Карьера по разработке программного обеспечения Springboard», чтобы узнать, соответствуете ли вы требованиям.

    Не совсем готовы погрузиться в учебный курс по разработке программного обеспечения?

    Springboard также предлагает подготовительный курс по разработке программного обеспечения, на котором вы можете изучить базовые навыки веб-разработки (HTML, CSS и JavaScript), необходимые для прохождения опроса технических навыков для программы «Карьера в программной инженерии».

    datastructures-js - npm

    объединяет все структуры данных @ datastructures-js в единый репозиторий.

    установить

     npm install --save datastructures-js 

    API

    требуется

     const {
      Куча,
    
      Очередь,
    
      Установить как EnhancedSet, // переименовано во избежание конфликта с es6 Set
    
      LinkedList,
      LinkedListNode,
      DoublyLinkedList,
      DoublyLinkedListNode,
    
      МинХип,
      MaxHeap,
    
      MinPriorityQueue,
      MaxPriorityQueue,
    
      BinarySearchTree,
      BinarySearchTreeNode,
      AvlTree,
      AvlTreeNode,
    
      Трие,
    
      График,
      DirectedGraph,
    } = require ('datastructures-js'); 

    импорт

     import {
      Куча,
    
      Очередь,
    
      Установить как EnhancedSet, // переименовано во избежание конфликта с es6 Set
    
      LinkedList,
      LinkedListNode,
      DoublyLinkedList,
      DoublyLinkedListNode,
    
      МинХип,
      MaxHeap,
    
      MinPriorityQueue,
      MaxPriorityQueue,
    
      BinarySearchTree,
      BinarySearchTreeNode,
      AvlTree,
      AvlTreeNode,
    
      Трие,
    
      График,
      DirectedGraph,
    } из 'datastructures-js'; 

    продлить

    Структуры данных реализованы здесь как классы ES6 для общих целей.Вы можете расширить любой из этих классов, чтобы добавить / изменить любую функциональность в вашем коде.

     const {Graph} = require ('datastructures-js'); // ИЛИ require ('@ datastructures-js / graph')
    
    class CustomGraph extends Graph {
      findShortestPath (pointA, pointB) {
        // код
      }
    } 

    Репозитории

    Стек

    https://github.com/datastructures-js/stack

    Очередь

    https://github.com/datastructures-js/queue

    Связанный список (одиночный / двойной)

    https: // github.com / datastructures-js / связанный список

    Комплект

    https://github.com/datastructures-js/set

    Куча (мин. / Макс.)

    https://github.com/datastructures-js/heap

    Очередь с приоритетом (мин. / Макс.)

    https://github.com/datastructures-js/priority-queue

    Дерево двоичного поиска (BST / AVL)

    https://github.com/datastructures-js/binary-search-tree

    Trie

    https://github.com/datastructures-js/trie

    График (направленный / неориентированный)

    https: // github.com / datastructures-js / график

    Сборка

      grunt сборка
      

    Лицензия

    Лицензия MIT. Полная лицензия здесь

    Структура данных массива JavaScript

    Массивы - это самая фундаментальная структура данных в любом языке программирования.

    Массивы доступны в большинстве (если не во всех) языках программирования, встроены в язык.

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

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

    Это позволяет нам выполнять такие операции, как доступ к слоту №2, зная адрес памяти первого слота, №0, и просто добавляя к нему 2 .

    В JavaScript мы работаем на более высоком уровне, а массивы работают по-другому. У нас нет доступа к памяти, как в случае с C или другими языками более низкого уровня, поэтому мы абстрагируемся от этого вида математики массивов.

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

    В JavaScript массивы могут содержать любые данные, смешивая их. У нас может быть число, затем объект, а затем еще один массив.

    Массив инициализируется с использованием этого синтаксиса:

    или

      const myArray = новый массив ()
      

    нет никакой разницы, но я предпочитаю сокращенный синтаксис [] .

    В JavaScript нам не требуется указывать размер массива во время создания, но мы можем сделать это:

      const myArray = новый массив (10)
      

    Затем мы можем заполнить массив значениями:

      пусть val = 1
    for (const [i, v] из myArray.entries ()) {
      myArray [i] = val ++
    }
      

    Вы можете ссылаться на первый элемент в массиве, используя:

    (начало индекса с 0 ) и каждый последующий элемент в массиве путем увеличения номера индекса:

      myArray [4] // 5
    myArray [3 + 4] // 8
      

    Вы можете изменить значение элемента в любой позиции, используя синтаксис:

      myArray [3] = 'Другой элемент'
      

    Массивы в JavaScript являются внутренними объектами, поэтому у них есть методы.Вы можете добавить один элемент в конец массива, используя метод push :

    Вы можете добавить элемент в любую позицию, используя метод splice () (не путать с slice () ).

    В начале:

      myArray.splice (0, 0, 'новый элемент')
      

    При индексе 3:

      myArray.splice (3, 0, 'новый элемент')
      

    Вы можете удалить элемент из конца массива, используя

    и с самого начала используя

    Мы можем найти длину массива, проверяя myArray.длина собственности.

    И мы можем перебирать элементы в массиве, используя циклы:

      для (let i = 0; i  
      myArray.forEach ((элемент, индекс) => {
      console.log (item) // значение
      console.log (index) // индекс
    }
      
      пусть i = 0
    while (i  
      // перебираем значение
    for (постоянное значение myArray) {
      приставка.log (значение) // значение
    }
    
    // также получаем индекс, используя `entries ()`
    for (const [индекс, значение] myArray.entries ()) {
      console.log (index) // индекс
      console.log (значение) // значение
    }
      

    Другие руководства по js:

    Основы JavaScript: типы и структуры данных | от CodeDraken

    Essentials - это серия статей, в которых рассматриваются наиболее часто используемые и важные методы для темы X. Это серия для разработчиков, знающих другой язык или желающих быстро начать работу.В этом посте мы рассмотрим типы и структуры данных.

    Я не буду вдаваться в подробности здесь, а просто перечислю общие темы, с которыми вы в конечном итоге столкнетесь в JS, и ресурсы, чтобы узнать о них. Другими словами, я научу вас быстрее, чем вы столкнетесь с этим позже.

    - - Предварительные требования
    - Типы и основы структур данных
    - - Есть ли типы в JS?
    - - Статически типизированный
    - - Динамически типизированный
    - - Слабо типизированный
    - - Примитивы
    - - Объекты
    - - Так когда это сбивает с толку?
    - Важные рекомендации
    - Некоторые непонятные части
    - - Почему объект не имеет значения NULL?
    - - Почему число не является числом?
    - - Двойное равенство против тройного равно
    - - Примитив не является объектом и не имеет собственных методов
    - Советы и уловки
    - Ссылки и ссылки

    Предварительные требования

    Для этой темы ничего не требуется.Это основная фундаментальная часть любого языка, но в JavaScript она быстро сбивает с толку.

    Мы будем использовать тип оператора , чтобы изучить типы, указанные ниже.

    Есть ли типы в JS?

    Кто-то может возразить, что JS нетипизирован или что он не должен вызывать свои типы системного типа. При создании переменной не требуется объявлять тип, как в некоторых других строго типизированных языках, например, int x = 10 Я (и спецификации JS) утверждают, что JS действительно имеет типы.

    JS - это с динамической типизацией и со слабой типизацией .

    Статически типизированный

    JS не является статически типизированным, если вы не используете язык, инструмент, такой как Typescript или Flow, который компилируется в код JS. Но мы кратко рассмотрим это для сравнения.

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

     int x = 5 
    string y = 'abc'

    Динамически типизированный

    Динамически типизированный язык определяет типы переменных во время выполнения .Это означает, что после запуска вашего кода компилятор / интерпретатор увидит вашу переменную и ее значение, а затем решит, какой она тип. Тип по-прежнему применяется здесь, он просто определяет, какой тип.

     var a = 1 // int 
    b = 'test' // string
    // etc

    Слабо типизированный

    Слабо типизированные языки позволяют выводить типы как другой тип . Например, 1 + '2' // '12' В JS он видит, что вы пытаетесь добавить число со строкой - недопустимая операция - поэтому он преобразует ваш номер в строку и приводит к строке '12 '.

    Примитивы

    Эти шесть типов считаются примитивами . Примитив не является объектом и не имеет собственных методов. Все примитивы неизменяемы .

    • Boolean - истина или ложь
    • Null - нет значения
    • Undefined - объявленная переменная, но ей не присвоено значение
    • Number - целые числа, числа с плавающей запятой и т. Д.
    • String - массив символов, то есть слов
    • Символ - уникальное значение, не равное никакому другому значению.

    Все остальное относится к типу Object .Основы

    примитивов

    Объекты

    Вот некоторые из стандартных объектов. Обратите внимание, что некоторые из них тоже были в примитивном списке, но не путайте их. Они действуют как конструкторов для создания этих типов. т.е. Boolean ('a') // true

    Есть два основных объекта, которые вы будете использовать для своих собственных структур:

    Есть много других объектов, просто перечислим некоторые из них:

    • Function
    • Boolean
    • Symbol
    • Error
    • Number
    • String
    • RegExp
    • Math
    • Set
    Основы объектов

    Итак, когда это сбивает с толку?

    Это сбивает с толку, когда ваши типы смешиваются, а JavaScript решает, какой тип вашего значения использует приведение типа .Об этом написана целая статья, и я не мог бы объяснить ее лучше:

    Далее я рассмотрю некоторые другие запутанные части, а также некоторые советы и рекомендации.

    • Все примитивные значения неизменяемы.
    • Помните о приведении типов.
    • Статическая типизация отсутствует, т.е. int num = 5
    • . Механизм JavaScript решает, какой это тип.

    В JavaScript много запутанных частей - см. Wtf JS?

    Почему объект пуст?

    В документации он указан как примитивный тип, но его тип возвращает «объект» .

    По сути, это ошибка, которую не исправляют, потому что она нарушает существующий код. Эта ошибка существует с первой версии JavaScript. Ошибка связана с типом функции в исходном коде JS - я воспользуюсь псевдокодом, чтобы упростить ее.

    псевдотип

    Вы поймали ошибку? Они не проверяли наличие null

    . Подробнее об отклоненном предложении по исправлению здесь и этой части исходного кода JS.

    Почему число не является числом?

    typeof NaN // 'число' WTF !?

    Короткий ответ: NaN определяется как числовой тип, но это не действительное число. NaN - это результат некоторых математических операций, которые нельзя выразить числом.

    Или, еще короче, потому, что так сказано в спецификации.

    Double Equals vs Triple Equals

    На эту тему также есть статья о CodeBurst.

    В случае сомнений всегда используйте тройное значение .

    Примитив не является объектом и не имеет собственных методов

    «Вы сказали, что у примитивов нет методов, но затем объясните, как 'abc'.длина работает! »

    Это не было ошибкой и исходит из самой документации.

    A примитив (примитивное значение, примитивный тип данных) - это данные, которые не являются объектом и не имеют методов В JavaScript есть 6 примитивных типов данных: строка , число , логическое , null , неопределенный символ , неопределенный символ , новое в ECMAScript 2015).

    Во-первых, не путайте конструкторы с примитивами - каждый примитив имеет конструктор или родительский объект. JS знает, что когда вы пытаетесь получить доступ к методу в примитиве и за кулисами, он будет использовать конструктор для создания объекта из вашего примитива. После запуска метода этот объект собирается сборщиком мусора. (удалено из памяти)

    См. несколько примеров ниже.

    строка - примитив

    Строки на самом деле являются примитивами, как описано в статье, а не целыми объектами.JS знает, когда вы пытаетесь получить доступ к методу объекта String , а переводит ваш примитив в строковый объект . Когда это будет сделано, временный объект будет удален, и его жизнь будет продолжаться как обычно.

    строковый конструктор

    Подробнее об этом читайте в книге YDKJS Кайла Симпсона:

    Способы использования типов в ваших интересах.

    Используйте их с осторожностью. По большей части вы должны использовать Number (str) parseInt (x) String (num) и т. Д.Они здесь, поэтому, если вы увидите это в чужом коде, вы будете знать, что он делает. Или, если вы играете в кодовый гольф ⛳️

    трюков - преобразование типов, значение по умолчанию, короткое, если

    Спасибо за чтение! Вопросы / отзывы оставляйте в комментариях.

    Структуры данных | Chart.js

    Свойство data набора данных может передаваться в различных форматах. По умолчанию данные анализируются с использованием связанного типа диаграммы и масштабов.

    Если используется свойство метки основного свойства данных , оно должно содержать такое же количество элементов, что и набор данных с наибольшим количеством значений.Эти метки используются для маркировки оси индекса (оси x по умолчанию). Значения меток должны быть предоставлены в виде массива. Метки обеспечения могут иметь тип строки или числа для правильной визуализации. Если вам нужны многострочные метки, вы можете предоставить массив с каждой строкой как одной записью в массиве.

    Primitive []

    Когда данные являются массивом чисел, значения из меток массива с тем же индексом используются для оси индекса ( x для вертикальных диаграмм, y для горизонтальных диаграмм).

    Объект []

    Это также внутренний формат, используемый для анализируемых данных. В этом режиме синтаксический анализ можно отключить, указав parsing: false в параметрах диаграммы или наборе данных. Если синтаксический анализ отключен, данные должны быть отсортированы и в форматах, используемых для внутреннего использования связанного типа диаграммы и масштабов.

    Предоставленные значения должны анализироваться соответствующими шкалами или во внутреннем формате связанных шкал. Распространенной ошибкой было бы предоставление целых чисел для шкалы категории , которая использует целые числа в качестве внутреннего формата, где каждое целое число представляет индекс в массиве меток. null можно использовать для пропущенных значений.

    Объект [] с использованием настраиваемых свойств

    Объект

    В этом режиме имя свойства используется для шкалы индекса и значения для шкалы значения . Для вертикальных диаграмм масштаб индекса составляет x , а шкала значений - y .

    Конфигурация набора данных

    Имя Тип Описание
    метка строка Метка для набора данных, которая появляется в легенде и всплывающих подсказках.
    зажим номер | объект Как обрезать относительно chartArea. Положительное значение допускает переполнение клипов с отрицательным значением на много пикселей внутри chartArea. 0 = клип в области диаграммы. Обрезку также можно настроить для каждой стороны: clip: {left: 5, top: false, right: -2, bottom: 0}
    order number Порядок рисования набора данных. Также влияет на порядок наложения, всплывающую подсказку и легенду.
    стек строка Идентификатор группы, к которой принадлежит этот набор данных (при объединении в стек каждая группа будет отдельным стеком). По умолчанию набор данных тип .
    синтаксический анализ логическое значение | объект Как проанализировать набор данных.

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *