10 общи структури на данни, обяснени с видеоклипове + упражнения

„Лоши програмисти се притесняват от кода. Добрите програмисти се тревожат за структурите на данните и техните взаимоотношения. “- Линус Торвалдс, създател на Linux
** Актуализиране ** Моят видео курс за Алгоритми вече е на живо! Вижте алгоритмите в движение от публикации на Manning. Вземете 39% отстъпка от курса ми, като използвате код „39carnes“! Или можете да получите 50% отстъпка от курса ми за дълбоко обучение в движение с код „vlcarnes2“.

Структурите на данните са важна част от разработването на софтуер и една от най-често срещаните теми за въпроси за интервю за работа на разработчици.

Добрата новина е, че те са основно специализирани формати за организиране и съхраняване на данни.

Ще ви науча на 10 от най-често срещаните структури от данни - точно тук, в тази кратка статия.

Вградих видеоклипове, които създадох за всяка от тези структури от данни. Свързах и примери за кодове за всеки от тях, които показват как да ги прилагаме в JavaScript.

И за да ви дам малко практика, аз съм свързан с предизвикателствата от учебната програма на freeCodeCamp.

Имайте предвид, че някои от тези структури от данни включват сложността на времето в Big O нотация. Това не е включено за всички тях, тъй като времевата сложност понякога се основава на начина, по който се прилага. Ако искате да научите повече за Big O Notation, разгледайте моята статия за него или това видео от Briana Marie.

Също така имайте предвид, че въпреки че показвам как да прилагате тези структури от данни в JavaScript, за повечето от тях никога няма да е необходимо сами да ги прилагате, освен ако не използвате език на ниско ниво като C.

JavaScript (като повечето езици на високо ниво) има вградени реализации на много от тези структури от данни.

Все пак знанието как да внедрите тези структури от данни ще ви даде огромно предимство в търсенето на работа на програмиста ви и може да ви е полезно, когато се опитвате да напишете високоефективен код.

Свързани списъци

Свързан списък е една от най-основните структури на данни. Често се сравнява с масив, тъй като много други структури от данни могат да бъдат реализирани или с масив, или с свързан списък. Всеки от тях има предимства и недостатъци.

Представяне на свързан списък

Свързан списък се състои от група възли, които заедно представляват последователност. Всеки възел съдържа две неща: действителните данни, които се съхраняват (които по принцип могат да бъдат всякакъв тип данни) и указател (или връзка) към следващия възел в последователността. Има и двойно свързани списъци, където всеки възел има указател както към следващия елемент, така и към предишния елемент в списъка.

Най-основните операции в свързания списък са добавяне на елемент в списъка, изтриване на елемент от списъка и търсене в списъка за елемент.

Вижте кода за свързан списък в JavaScript тук.

Времева сложност на свързания списък
╔═══════════╦═════════╦════════════╗
║ Алгоритъм ║ Среден ║ Най-лош случай ║
╠═══════════╬═════════╬════════════╣
Пространство ║ O (n) ║ O (n) ║
Търсене ║ O (n) ║ O (n) ║
Поставете ║ O (1) ║ O (1) ║
║ Изтрийте ║ O (1) ║ O (1) ║
╚═══════════╩═════════╩════════════╝

предизвикателства за freeCodeCamp

  • Работете с възли в свързан списък
  • Създайте Свързан клас списък
  • Премахване на елементи от свързан списък
  • Търсете в свързан списък
  • Премахване на елементи от свързан списък по индекс
  • Добавете елементи в конкретен индекс в свързан списък
  • Създайте списък с двойно обвързване
  • Обърнете двойно свързан списък

Купища

Стека е основна структура на данни, в която можете да вмъквате или изтривате само елементи в горната част на стека. Тя е нещо подобно на купчина книги. Ако искате да погледнете книга в средата на стека, първо трябва да свалите всички книги над нея.

Стекът се счита за LIFO (Last In First Out) - означава, че последният елемент, който сложите в стека, е първият елемент, който излиза от стека

Представяне на стекове

Има три основни операции, които могат да се извършват на стекове: вмъкване на елемент в стек (наречен "push"), изтриване на елемент от стека (наречен "pop") и показване на съдържанието на стека (понякога наричан "pip" ").

Вижте кода за стек в JavaScript тук.

Сложност на стека време
╔═══════════╦═════════╦════════════╗
║ Алгоритъм ║ Среден ║ Най-лош случай ║
╠═══════════╬═════════╬════════════╣
Пространство ║ O (n) ║ O (n) ║
Търсене ║ O (n) ║ O (n) ║
Поставете ║ O (1) ║ O (1) ║
║ Изтрийте ║ O (1) ║ O (1) ║
╚═══════════╩═════════╩════════════╝

предизвикателства за freeCodeCamp

  • Научете как работи стека
  • Създайте клас на стека

Опашките

Можете да мислите за опашка като линия от хора в магазин за хранителни стоки. Първият в реда е първият, който се сервира. Точно като опашка.

Представяне на опашка

Опашката се счита FIFO (First In First Out), за да демонстрира начина, по който достъпът до данните. Това означава, че след като се добави нов елемент, всички елементи, добавени преди това, трябва да бъдат премахнати, преди новият елемент да може да бъде премахнат.

Опашката има само две основни операции: enqueue и dequeue. Enqueue означава да вмъкнете елемент в задната част на опашката, а dequeue означава премахване на предния елемент.

Вижте кода за опашка в JavaScript тук.

Сложност на времето на опашката
╔═══════════╦═════════╦════════════╗
║ Алгоритъм ║ Среден ║ Най-лош случай ║
╠═══════════╬═════════╬════════════╣
Пространство ║ O (n) ║ O (n) ║
Търсене ║ O (n) ║ O (n) ║
Поставете ║ O (1) ║ O (1) ║
║ Изтрийте ║ O (1) ║ O (1) ║
╚═══════════╩═════════╩════════════╝

предизвикателства за freeCodeCamp

  • Създайте клас на опашка
  • Създайте клас с приоритетна опашка
  • Създайте кръгла опашка

Комплекти

Задайте представителство

Зададената структура на данни съхранява стойности без конкретен ред и без повторени стойности. Освен че можете да добавяте и премахвате елементи към даден набор, има няколко други важни зададени функции, които работят с два набора едновременно.

  • Съединение - Това комбинира всички елементи от два различни набора и връща това като нов набор (без дубликати).
  • Пресичане - Като се имат предвид два набора, тази функция връща друг набор, който има всички елементи, които са част от двата набора.
  • Разлика - Това връща списък с елементи, които са в един набор, но НЕ в различен набор.
  • Подмножество - Това връща булева стойност, която показва дали всички елементи от един набор са включени в различен набор.

Вижте кода, за да реализирате набор в JavaScript тук.

предизвикателства за freeCodeCamp

  • Създайте клас клас
  • Премахване от комплект
  • Размер на комплекта
  • Извършете съюз на два комплекта
  • Извършете пресечка на два набора от данни
  • Извършете разлика в два набора данни
  • Извършете проверка на подмножество на два набора данни
  • Създаване и добавяне към набори в ES6
  • Премахване на елементи от набор в ES6
  • Използвайте .has и .size на ES6 Set
  • Използвайте Spread and Notes за интеграция на ES5 Set ()

Карти

Карта е структура на данни, която съхранява данни в двойки ключ / стойност, където всеки ключ е уникален. Карта понякога се нарича асоциативен масив или речник. Често се използва за бързо търсене на данни. Картите позволяват следните неща:

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

Вижте кода, за да внедрите карта в JavaScript тук.

предизвикателства за freeCodeCamp

  • Създайте структура на данните от картата
  • Създайте JavaScript карта на ES6

Хеш таблици

Таблица на хеш и представяне на хеш функции

Хеш-таблицата е структура от данни на картата, която съдържа двойки ключ / стойност. Той използва хеш функция, за да изчисли индекс в масив от кодове или слотове, от които може да се намери желаната стойност.

Хеш функцията обикновено приема низ като вход и извежда числова стойност. Хеш функцията трябва винаги да дава един и същ номер на изхода за един и същи вход. Когато два входа хеш към един и същ цифров изход, това се нарича сблъсък. Целта е да има няколко сблъсъка.

Така че, когато въведете двойка ключ / стойност в хеш таблицата, ключът се изпълнява чрез хеш функцията и се превръща в число. Тази цифрова стойност след това се използва като действителния ключ, от който се съхранява стойността. Когато се опитате отново да получите достъп до същия ключ, функцията хеширане ще обработи ключа и ще върне същия числен резултат. След това числото ще се използва за търсене на свързаната стойност. Това осигурява средно много ефикасно време за търсене на O (1).

Вижте кода за хеш таблица тук.

Времева сложност на хеш таблицата
╔═══════════╦═════════╦════════════╗
║ Алгоритъм ║ Среден ║ Най-лош случай ║
╠═══════════╬═════════╬════════════╣
Пространство ║ O (n) ║ O (n) ║
Търсене ║ O (1) ║ O (n) ║
Поставете ║ O (1) ║ O (n) ║
║ Изтрийте ║ O (1) ║ O (n) ║
╚═══════════╩═════════╩════════════╝

предизвикателства за freeCodeCamp

  • Създайте таблица за хеш

Двоично дърво за търсене

Двоично дърво за търсене

Дърво е структура от данни, съставена от възли, има следните характеристики:

  1. Всяко дърво има корен възел (в горната част).
  2. Кореновият възел има нула или повече дъщерни възли.
  3. Всеки детски възел има нула или повече дъщерни възли и т.н.

Двоично дърво за търсене добавя тези две характеристики:

  1. Всеки възел има до две деца.
  2. За всеки възел неговите леви потомци са по-малко от текущия възел, което е по-малко от десните потомци.

Двоичните дървета за търсене позволяват бързо търсене, добавяне и премахване на елементи. Начинът, по който са настроени, означава, че средно всяко сравнение позволява операциите да прескачат около половината от дървото, така че всяко търсене, вмъкване или изтриване отнема време, пропорционално на логаритъма на броя на елементите, съхранявани в дървото.

Вижте кода за двоично дърво за търсене в JavaScript тук.

Сложност на бинарно време за търсене
╔═══════════╦══════════╦════════════╗
║ Алгоритъм ║ Среден ║ Най-лош случай ║
╠═══════════╬══════════╬════════════╣
Пространство ║ O (n) ║ O (n) ║
Търсене ║ O (лог n) ║ O (n) ║
Поставете ║ O (лог n) ║ O (n) ║
║ Изтриване ║ O (лог n) ║ O (n) ║
╚═══════════╩══════════╩════════════╝

предизвикателства за freeCodeCamp

  • Намерете минималната и максималната стойност в двоично дърво за търсене
  • Добавете нов елемент към двоично дърво за търсене
  • Проверете дали елемент присъства в бинарно дърво за търсене
  • Намерете минималната и максималната височина на двоично дърво за търсене
  • Използвайте първо търсене в дълбочина в двоично дърво за търсене
  • Използвайте първо търсене в широчина на дървото за търсене
  • Изтрийте листов възел в двоично дърво за търсене
  • Изтрийте възел с едно дете в двоично дърво за търсене
  • Изтрийте възел с две деца в двоично дърво за търсене
  • Обърнете двоично дърво

Trie

Трие (произнася се "опита") или префикс дърво е вид дърво за търсене. Трие съхранява данни на стъпки, където всяка стъпка е възел в трие. Опитите често се използват за съхраняване на думи за бързо търсене, например функция за автоматично завършване на думи.

Трие представителство

Всеки възел в езиково трие съдържа една буква от дума. Следвате клоните на трие, за да пишете дума, по една буква в даден момент. Стъпките започват да се разклоняват, когато редът на буквите се различава от другите думи в триетата или когато една дума завършва. Всеки възел съдържа буква (данни) и булева информация, която показва дали възелът е последният възел в дума.

Погледнете изображението и можете да образувате думи. Винаги започвайте от коренния възел в горната част и работете надолу. Показаното тук трие съдържа думата топка, бухалка, кукла, направете, dork, общежитие, изпратете, смисъл.

Вижте кода за трие в JavaScript тук.

предизвикателства за freeCodeCamp

  • Създайте дърво за търсене на Trie

Binary Heap

Бинарна купчина е друг вид структура на данни за дърво. Всеки възел има най-много две деца. Също така, това е пълно дърво. Това означава, че всички нива са напълно запълнени до последното ниво и последното ниво се запълва отляво надясно.

Минимални и максимални представления за купчина

Двоичната купчина може да бъде или min heap или max heap. В максимална грамада ключовете на родителските възли винаги са по-големи или равни на тези на децата. В мин. Купчина ключовете на родителските възли са по-малки или равни на тези на децата.

Редът между нивата е важен, но редът на възлите на същото ниво не е важен. На изображението можете да видите, че третото ниво на мин. Грамада има стойности 10, 6 и 12. Тези числа не са в ред.

Вижте кода за грамада в JavaScript тук.

Сложност на бинарно време за купчина
╔═══════════╦══════════╦════════════╗
║ Алгоритъм ║ Среден ║ Най-лош случай ║
╠═══════════╬══════════╬════════════╣
Пространство ║ O (n) ║ O (n) ║
Търсене ║ O (n) ║ O (n) ║
Поставете ║ O (1) ║ O (log n) ║
║ Изтриване ║ O (log n) ║ O (log n) ║
Peek ║ O (1) ║ O (1) ║
╚═══════════╩══════════╩════════════╝

предизвикателства за freeCodeCamp

  • Вмъкнете елемент в Max Heap
  • Премахване на елемент от Max Heap
  • Реализирайте сортирането на купчина с минимална купчина

диаграма

Графиките са колекции от възли (наричани още върхове) и връзките (наречени ръбове) между тях. Графиките са известни и като мрежи.

Един пример за графики е социална мрежа. Възлите са хора, а краищата са приятелство.

Има два основни типа графики: насочени и насочени. Ненасочените графики са графики без посока по краищата между възлите. За разлика от тях насочените графики са графики с посока в краищата му.

Два често срещани начина за представяне на графика са списък на съседни и матрица на съседство.

Матрица графика на съседничеството

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

Матрицата за съседство е мрежа от числа, където всеки ред или колона представлява различен възел в графиката. В пресечната точка на ред и колона е число, което показва връзката. Нулите означават, че няма ръб или връзка. Онези означават, че има връзка. Числата по-високи от една могат да се използват за показване на различни тегла.

Алгоритмите за преминаване са алгоритми за преминаване или посещение на възли в графика. Основните типове алгоритми за преминаване са първо търсене по ширина и първо търсене по дълбочина. Едно от използванията е да се определи колко близо са възлите до коренния възел. Вижте как да приложите първото търсене в JavaScript във видеото по-долу.

Вижте кода за първо търсене в широчината на матрица графика на съседство в JavaScript.

Времева сложност на списъка на придружителността (графиката)
╔═══════════════╦════════════╗
║ Алгоритъм ║ Време ║
╠═══════════════╬════════════╣
║ Съхранение ║ O (| V | + | E |) ║
║ Добавете Vertex ║ O (1) ║
Добавете Edge ║ O (1) ║
║ Извадете Vertex ║ O (| V | + | E |) ║
Премахване на ръба ║ O (| E |) ║
Запитване ║ O (| V |) ║
╚═══════════════╩════════════╝

предизвикателства за freeCodeCamp

  • Списък за съседство
  • Матрица за съпричастност
  • Матрица на случаите
  • Първо търсене
  • Дълбоко-първо търсене

| Повече ▼

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

Или можете да проверите моя видео курс въз основа на тази книга: Алгоритми в движение от публикации на Manning. Вземете 39% отстъпка от курса ми, като използвате код „39carnes“!