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

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

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

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

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

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

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

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

function Stack() {
    this.count = 0
    this.storage = {}

    this.push = function(value) {
        this.storage[this.count] = value
        this.count++
    }

    this.pop = function() {
        if (this.count === 0) return undefined
        this.count--
        let result = this.storage[this.count]
        delete this.storage[this.count]
        return result
    }

    this.peek = function() {
        return this.storage[this.count - 1]
    }

    this.size = function() {
        return this.count
    }
}

2. Очередь (кью) (Queue)

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

Очередь имеет следующие методы:

• enqueue: войти в очередь, добавить элемент в конец
• dequeue: покинуть очередь, удалить первый элемент и вернуть его
• front: получить первый элемент
• isEmpty: проверить, пуста ли очередь
• size: получить количество элементов в очереди

function Queue() {
    let collection = []

    this.print = function() {
        console.log(collection)
    }

    this.enqueue = function(element) {
        collection.push(element)
    }

    this.dequeue = function() {
        return collection.shift()
    }

    this.front = function() {
        return collection[0]
    }

    this.isEmpty = function() {
        return collection.length === 0
    }

    this.size = function() {
        return collection.length
    }
}

    

Порядок очередности (приоритет)

function PriorityQueue() {
    ...
    this.enqueue = function(element) {
        if (this.isEmpty()) {
            collection.push(element)
        } else {
            let added = false
            for (let i = 0; i < collection.length; i++) {
                if (element[1] < collection[i][1]) {
                    collection.splice(i, 0, element)
                    added = true
                    break;
                }
            }
            if (!added) {
                collection.push(element)
            }
        }
    }
}

let pQ = new PriorityQueue()
pQ.enqueue([gannicus, 3])
pQ.enqueue([spartacus, 1])
pQ.enqueue([crixus, 2])
pQ.enqueue([oenomaus, 4])
pQ.print()

[
    [spartacus, 1],
    [crixus, 2],
    [gannicus, 3],
    [oenomaus, 4]
]

3. Связный список (связанный, список узлов и ссылок или указателей) (Linked List)

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

• size: вернуть количество узлов
• head: вернуть первый элемент (head — голова)
• add: добавить элемент в конец (tail — хвост)
• remove: удалить несколько узлов
• indexOf: вернуть индекс узла
• elementAt: вернуть узел по индексу
• addAt: вставить узел в определенное место (по индексу)
• removeAt: удалить определенный узел (по индексу)

// узел
function Node(element) {
    // данные
    this.element = element
    // указатель на следующий узел
    this.next = null
}

function LinkedList() {
    let length = 0
    let head = null
    this.size = function() {
        return length
    }

    this.head = function() {
        return head
    }

    this.add = function(element) {
        let node = new Node(element)
        if (head === null) {
            head = node
        } else {
            let currentNode = head
            while (currentNode.next) {
                currentNode = currentNode.next
            }
            currentNode.next = node
        }
        length++
    }

    this.remove = function(element) {
        let currentNode = head
        let previousNode
        if (currentNode.element !== element) {
            head = currentNode.next
        } else {
            while (currentNode.element !== element) {
                previousNode = currentNode
                currentNode = currentNode.next
            }
            previousNode.next = currentNode.next
        }
        length--
    }

    this.isEmpty = function() {
        return length === 0
    }

    this.indexOf = function(element) {
        let currentNode = head
        let index = -1
        while (currentNode) {
            index++
            if (currentNode.element === element) {
                return index
            }
            currentNode = currentNode.next
        }
        return -1
    }

    this.elementAt = function(index) {
        let currentNode = head
        let count = 0
        while (count < index) {
            count++
            currentNode = currentNode.next
        }
        return currentNode.element
    }

    this.addAt = function(index, element) {
        let node = new Node(element)
        let currentNode = head
        let previousNode
        let currentIndex = 0
        if (index > length) return false
        if (index === 0) {
            node.next = currentNode
            head = node
        } else {
            while (currentIndex < index) {
                currentIndex++
                previousNode = currentNode
                currentNode = currentNode.next
            }
            node.next = currentNode
            previousNode.next = node
        }
        length++
    }

    this.removeAt = function(index) {
        let currentNode = head
        let previousNode
        let currentIndex = 0
        if (index < 0 || index >= length) return null
        if (index === 0) {
            head = currentIndex.next
        } else {
            while (currentIndex < index) {
                currentIndex++
                previousNode = currentNode
                currentNode = currentNode.next
            }
            previousNode.next = currentNode.next
        }
        length--
        return currentNode.element
    }
}

    




    

4. Коллекция (значений) (Set)

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

Стандартная коллекция имеет следующие методы:

• values: вернуть все элементы в коллекции
• size: вернуть количество элементов
• has: проверить, имеется ли элемент в коллекции
• add: добавить элемент
• remove: удалить элемент
• union: вернуть область пересечения двух коллекций
• difference: вернуть отличия двух коллекций
• subset: проверить, является ли одна коллекция подмножеством другой

// дистанцируемся от Set в JS
function MySet() {
    let collection = []
    this.has = function(element) {
        return (collection.indexOf(element) !== -1)
    }

    this.values = function() {
        return collection
    }

    this.size = function() {
        return collection.length
    }

    this.add = function(element) {
        if (!this.has(element)) {
            collection.push(element)
            return true
        }
        return false
    }

    this.remove = function(element) {
        if (this.has(element)) {
            index = collection.indexOf(element)
            collection.splice(index, 1)
            return true
        }
        return false
    }

    this.union = function(otherSet) {
        let unionSet = new MySet()
        let firstSet = this.values()
        let secondSet = otherSet.values()
        firstSet.forEach(i => unionSet.add(i))
        secondSet.forEach(i => unionSet.add(i))
    }

    this.intersection = function(otherSet) {
        let intersectionSet = new MySet()
        let firstSet = this.values()
        firstSet.forEach(function(e) {
            if (otherSet.has(e)) {
                intersectionSet.add(e)
            }
        })
        return intersectionSet
    }

    this.difference = function(otherSet) {
        let differenceSet = new MySet()
        let firstSet = this.values()
        firstSet.forEach(function(e) {
            if (!otherSet.has(e)) {
                differenceSet.add(e)
            }
        })
        return differenceSet
    }

    this.subset = function(otherSet) {
        lat firstSet = this.values()
        return firstSet.every(value => otherSet.has(value))
    }
}

    

5. Хеш-таблица (таблица кэширования) (Hash Table)

Хеш-таблица — это структура данных, которая строится по принципу ключ-значение. Из-за высокой скорости поиска значений по ключам, она используется в таких структурах, как Map, Dictionary и Object. Как показано на рисунке, хеш-таблица имеет hash function, преобразующую ключи в список номеров, которые используются как имена (значения) ключей. Время поиска значения по ключу может достигать O(1). Одинаковые ключи должны возвращать одинаковые значения — в этом суть функции хэширования.

Хеш-таблица имеет следующие методы:

• add: добавить пару ключ/значение
• remove: удалить пару
• lookup: найти значение по ключу

function hash(string, max) {
    let hash = 0
    for (let i = 0; i < string.length; i++) {
        hash += string.charCodeAt(i)
    }
    return hash % max
}

function HashTable() {
    let storage = []
    const storageLimit = 4

    this.add = function(key, value) {
        let index = hash(key, storageLimit)
        if (storage[index] === undefined) {
            storage[index] = [
                [key, value]
            ]
        } else {
            let inserted = false
            for (let i = 0; i < storage[index].len; i++) {
                if (storage[index][i][0] === key) {
                    storage[index][i][1] = value
                    inserted = true
                }
            }
            if (inserted === false) {
                storage[index].push([key, value])
            }
        }
    }

    this.remove = function(key) {
        let index = hash(key, storageLimit)
        if (storage[index].length === 1 && storage[index][0][0] === key) {
            delete storage[index]
        } else {
            for (let i = 0; i < storage[index]; i++) {
                if (storage[index][i][0] === key) {
                    delete storage[index][i]
                }
            }
        }
    }

    this.lookup = function(key) {
        let index = hash(key, storageLimit)
        if (storage[index] === undefined) {
            return undefined
        } else {
            for (let i = 0; i < storage[index].length; i++) {
                if (storage[index][i][0] === key) {
                    return storage[index][i][1]
                }
            }
        }
    }
}

    

6. Дерево (Tree)

Древовидная структура — это многослойная (многоуровневая) структура. Это также нелинейная структура, в отличие от массива, стека и очереди. Данная структура очень эффективна в части добавления и поиска элементов. Вот некоторые концепции древовидной структуры:

• root: корневой элемент, не имеет «родителя»
• parent node: прямой узел верхнего слоя (уровня), может быть только одним
• child node: прямой узел (узлы) нижнего уровня, может быть несколько
• siblings: дочерние элементы одного родительского узла
• leaf: узел без «детей»
• Edge: ветка или ссылка (связь) между узлами
• Path: путь (совокупность ссылок) от начального узла до целевого элемента
• Height of Tree (высота дерева): количество ссылок самого длинного пути от определенного элемента до узла, не имеющего потомков
• Depth of Node (глубина узла): количество ссылок от корневого узла до определенного элемента
• Degree of Node: количество потомков

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

• add: добавить узел
• findMin: получить минимальный узел
• findMax: получить максимальный узел
• find: найти определенный узел
• isPresent: проверить наличие определенного узла
• remove: удалить узел

class Node {
    constructor(data, left = null, right = null) {
        this.data = data
        this.left = left
        this.right = right
    }
}

class BST {
    constructor() {
        this.root = null
    }

    add(data) {
        const node = this.root
        if (node === null) {
            this.root = new Node(data)
            return
        } else {
            const searchTree = function(node) {
                if (data < node.data) {
                    if (node.left === null) {
                        node.left = new Node(data)
                        return
                    } else if (node.left !== null) {
                        return searchTree(node.left)
                    }
                } else if (data > node.data) {
                    if (node.right === null) {
                        node.right = new Node(data)
                        return
                    } else if (node.right !== null) {
                        return searchTree(node.right)
                    }
                } else {
                    return null
                }
            }
            return searchTree(node)
        }
    }

    findMin() {
        let current = this.root
        while (current.left !== null) {
            current = current.left
        }
        return current.data
    }

    findMax() {
        let current = this.root
        while (current.right !== null) {
            current = current.right
        }
        return current.data
    }

    find(data) {
        let current = this.root
        while (current.data !== data) {
            if (data < current.data) {
                current = current.left
            } else {
                current = current.right
            }
            if (current === null) {
                return null
            }
        }
        return current
    }

    isPresent(data) {
        let current = this.root
        while (current) {
            if (data === current.data) {
                return true
            }
            data < current.data ? current = current.left : current = current.right
        }
        return false
    }

    remove(data) {
        const removeNode = function(node, data) {
            if (node === null) return null
            if (data === node.data) {
                // потомки отсутствуют
                if (node.left === null && node.right === null) return null
                // отсутствует левый узел
                if (node.left === null) return node.right
                // отсутствует правый узел
                if (node.right === null) return node.left
                // имеется два узла
                let tempNode = node.right
                while (tempNode.left !== null) {
                    tempNode = tempNode.left
                }
                node.data = tempNode.data
                node.right = removeNode(node.right, tempNode.data)
                return node
            } else if (data < node.data) {
                node.left = removeNode(node.right, data)
                return node
            } else {
                node.right = removeNode(node.right, data)
                return node
            }
        }
        this.root = removeNode(this.root, data)
    }
}

const bst = new BST()
bst.add(4)
bst.add(2)
bst.add(6)
bst.add(1)
bst.add(3)
bst.add(5)
bst.add(7)
bst.remove(4)
console.log(bst.findMin())
console.log(bst.findMax())
bst.remove(7)
console.log(bst.findMax())
console.log(bst.isPresent(4))

1
7
6
false

7. Нагруженное (префиксное) дерево (Trie, читается как «try»)

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

Каждый узел дерева — буква алфавита, следование по ветке приводит к формированию слова. Оно также содержит «булевый индикатор» для определения того, что текущий узел является последней буквой.

Префиксное дерево имеет следующие методы:

• add: добавить слово в словарь
• isWord: проверить наличие слова
• print: вернуть все слова

// узел дерева
function Node() {
    this.keys = new Map()
    this.end = false
    this.setEnd = function() {
        this.end = true
    }
    this.isEnd = function() {
        return this.end
    }
}

function Trie() {
    this.root = new Node()
    this.add = function(input, node = this.root) {
        if (input.length === 0) {
            node.setEnd()
            return
        } else if (!node.keys.has(input[0])) {
            node.keys.set(input[0], new Node())
            return this.add(input.substr(1), node.key.get(input[0]))
        } else {
            return this.add(input.substr(1), node.keys.get(input[0]))
        }
    }

    this.isWord = function(word) {
        let node = this.root
        while (word.length > 1) {
            if (node.keys.has(word[0])) {
                return false
            } else {
                node = node.keys.get(word[0])
                word = word.substr(1)
            }
        }
        return (node.keys.has(word) && node.keys.get(word).isEnd()) ? true : false
    }

    this.print = function() {
        let words = new Array()
        let search = function(node = this.root, string) {
            if (node.keys.size !== 0) {
                for (let letter of node.keys.keys()) {
                    search(node.keys.get(letter), string.concat(letter))
                }
                if (node.isEnd()) {
                    words.push(string)
                }
            } else {
                string.length > 0 ? words.push(string) : undefined
                return
            }
        }
        search(this.root, new String())
        return words.length > 0 ? words : null
    }
}

8. Граф (график) (Graph)

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

Графы могут быть представлены в виде списка или матрицы.

Список

Матрица

Поиск по графу осуществляется двумя методами — поиск в ширину (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 ⛳️

Перевод статьи 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 алгоритмы и структуры данных Мастер-класс

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 - нет. Мутации могут рассматриваться как побочные эффекты в наших приложениях.

Давай создадим массив 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); 

Мы можем создать аналогичные функции для обработки изменений в объектах. Для этого создадим два класса 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 ⁵³ - 1) до 2 ⁵³ - 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-символ и т. Д. Все это требует соглашений и создает ненужную нагрузку на обслуживание.

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

Тип символа

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

 npm install --save datastructures-js 

 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'; 

 const {Graph} = require ('datastructures-js'); // ИЛИ require ('@ datastructures-js / graph')

class CustomGraph extends Graph {
  findShortestPath (pointA, pointB) {
    // код
  }
} 

  grunt сборка
  

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

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

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

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

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

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

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

  для (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 (значение) // значение
}
  

 int x = 5 
 string y = 'abc' 

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