6 структури от данни, които всеки програмист трябва да знае

Пътят към това да станеш опитен и успешен програмист е труден, но със сигурност е постижим. Структурите от данни са основен компонент, който всеки студент по програмиране трябва да овладее и има вероятност вече да сте научили или да сте работили с някои основни структури от данни, като масиви или списъци.

Интервюиращите предпочитат да задават въпроси, свързани със структурите от данни, така че ако се подготвяте за интервю за работа, ще трябва да подобрите знанията си за структурите от данни. Прочетете, докато изброяваме най-важните структури от данни за програмисти и интервюта за работа.

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

Елементите в рамките на свързания списък се съхраняват в отделни възли, които са свързани (свързани) с помощта на указатели. Можете да мислите за свързан списък като верига от възли, свързани един с друг чрез различни указатели.

Свързани: Въведение в използването на свързани списъци в Java

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

Всеки свързан списък има възел на главата и опашката. Единично свързаните списъчни възли имат само един указател, който сочи към следващия възел във веригата. В допълнение към следващия указател, двойно свързаните списъчни възли имат друг указател, който сочи към предишния възел във веригата.

Въпросите за интервю, свързани със свързани списъци, обикновено се въртят около вмъкването, търсенето или изтриването на конкретен елемент. Вмъкването в свързан списък отнема O(1) време, но изтриването и търсенето може да отнеме O(n) време в най-лошия случай. Така че свързаните списъци не са идеални.

2. Двоично дърво

Двоичните дървета са най-популярното подмножество на структурата от данни на семейството на дърветата; елементите в двоично дърво са подредени в йерархия. Други видове дървета включват AVL, червено-черни, B дървета и др. Възлите на двоичното дърво съдържат елемента данни и два указателя към всеки дъщерен възел.

Всеки родителски възел в двоично дърво може да има максимум два дъщерни възела и всеки дъщерен възел от своя страна може да бъде родител на два възела.

Свързани: Ръководство за начинаещи за двоични дървета

Двоично дърво за търсене (BST) съхранява данни в сортиран ред, където елементи с ключ-стойност по-малка от родителската възел се съхраняват отляво, а елементите с ключ-стойност, по-голяма от родителския възел, се съхраняват в право.

Бинарните дървета обикновено се питат в интервюта, така че ако се подготвяте за интервю, трябва да знаете как да сплескате двоично дърво, да търсите конкретен елемент и др.

3. Хеш таблица

Хеш таблиците или хеш карти са високоефективна структура от данни, която съхранява данни във формат на масив. На всеки елемент от данни се присвоява уникална индексна стойност в хеш таблица, която позволява ефективно търсене и изтриване.

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

Всяка хеш таблица съхранява елементи от данни в двойка стойност-индекс.

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

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

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

4. Стекове

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

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

Стековете имат две основни операции – push и pop. Push се използва за вмъкване на елемент в стека, а pop премахва най-горния елемент от стека.

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

5. Опашки

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

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

Свързани: Ръководство за начинаещи за разбиране на опашките и приоритетните опашки

Приоритетните опашки са неразделно приложение на опашките в много жизненоважни приложения, като например планирането на процесора. В опашката с приоритет елементите се подреждат според техния приоритет, а не по реда на пристигане.

6. Купища

Купчините са вид двоично дърво, където възлите са подредени във възходящ или низходящ ред. В Min Heap стойността на ключа на родителя е равна или по-малка от тази на неговите деца, а основният възел съдържа минималната стойност на цялата купчина.

По същия начин, основният възел на Max Heap съдържа максималната стойност на ключа на хийпа; трябва да запазите свойството min/max heap през цялата купчина.

Свързани: Купчини срещу Стекове: Какво ги отличава?

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

Научете структури от данни

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

Те са жизненоважна част от програмирането и почти всеки проект ще изисква от вас да ги използвате. Знаенето коя структура от данни е идеална за даден сценарий е от решаващо значение.

7 алгоритма, които всеки програмист трябва да знае

Тези алгоритми са от съществено значение за работния процес на всеки програмист.

Прочетете Следващото

За автора