Основные структуры данных. Матчасть. Азы

https://medium.freecodecamp.org/the-top-data-structures-you-should-know-for-your-next-coding-interview-36af0831f5e3
  • Перевод
Все чаще замечаю, что современным самоучкам очень не хватает матчасти. Все знают языки, но мало основы, такие как типы данных или алгоритмы. Немного про типы данных.

Еще в далеком 1976 швейцарский ученый Никлаус Вирт написал книгу Алгоритмы + структуры данных = программы.

40+ лет спустя это уравнение все еще верно. И если вы самоучка и надолго в программировании пробегитесь по статье, можно по диагонали. Можно код кофе.



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

Что такое структура данных?


Структура данных — это контейнер, который хранит данные в определенном макете. Этот «макет» позволяет структуре данных быть эффективной в некоторых операциях и неэффективной в других.

Какие бывают?


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

Нелинейные, если обход узлов нелинейный, а данные не последовательны. Пример: граф и деревья.

Основные структуры данных.


  1. Массивы
  2. Стеки
  3. Очереди
  4. Связанные списки
  5. Графы
  6. Деревья
  7. Префиксные деревья
  8. Хэш таблицы

Массивы


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

Изображение простого массива размера 4, содержащего элементы (1, 2, 3 и 4).



Каждому элементу данных присваивается положительное числовое значение (индекс), который соответствует позиции элемента в массиве. Большинство языков определяют начальный индекс массива как 0.

Бывают


Одномерные, как показано выше.
Многомерные, массивы внутри массивов.

Основные операции


  • Insert-вставляет элемент по заданному индексу
  • Get-возвращает элемент по заданному индексу
  • Delete-удаление элемента по заданному индексу
  • Size-получить общее количество элементов в массиве

Вопросы


  • Найти второй минимальный элемент массива
  • Первые неповторяющиеся целые числа в массиве
  • Объединить два отсортированных массива
  • Изменение порядка положительных и отрицательных значений в массиве

Стеки


Стек — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).

Это не массивы. Это очередь. Придумал Алан Тюринг.

Примером стека может быть куча книг, расположенных в вертикальном порядке. Для того, чтобы получить книгу, которая где-то посередине, вам нужно будет удалить все книги, размещенные на ней. Так работает метод LIFO (Last In First Out). Функция «Отменить» в приложениях работает по LIFO.

Изображение стека, в три элемента (1, 2 и 3), где 3 находится наверху и будет удален первым.



Основные операции


  • Push-вставляет элемент сверху
  • Pop-возвращает верхний элемент после удаления из стека
  • isEmpty-возвращает true, если стек пуст
  • Top-возвращает верхний элемент без удаления из стека

Вопросы


  • Реализовать очередь с помощью стека
  • Сортировка значений в стеке
  • Реализация двух стеков в массиве
  • Реверс строки с помощью стека

Очереди


Подобно стекам, очередь — хранит элемент последовательным образом. Существенное отличие от стека – использование FIFO (First in First Out) вместо LIFO.

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

Изображение очереди, в четыре элемента (1, 2, 3 и 4), где 1 находится наверху и будет удален первым



Основные операции


  • Enqueue—) — вставляет элемент в конец очереди
  • Dequeue () — удаляет элемент из начала очереди
  • isEmpty () — возвращает значение true, если очередь пуста
  • Top () — возвращает первый элемент очереди

Вопросы


  • Реализовать cтек с помощью очереди
  • Реверс первых N элементов очереди
  • Генерация двоичных чисел от 1 до N с помощью очереди

Связанный список


Связанный список – массив где каждый элемент является отдельным объектом и состоит из двух элементов – данных и ссылки на следующий узел.

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

Бывают


Однонаправленный, каждый узел хранит адрес или ссылку на следующий узел в списке и последний узел имеет следующий адрес или ссылку как NULL.

1->2->3->4->NULL

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

NULL<-1<->2<->3->NULL

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

1->2->3->1

Самое частое, линейный однонаправленный список. Пример – файловая система.



Основные операции


  • InsertAtEnd — Вставка заданного элемента в конец списка
  • InsertAtHead — Вставка элемента в начало списка
  • Delete — удаляет заданный элемент из списка
  • DeleteAtHead — удаляет первый элемент списка
  • Search — возвращает заданный элемент из списка
  • isEmpty — возвращает True, если связанный список пуст

Вопросы


  • Реверс связанного списка
  • Определение цикла в связанном списке
  • Возврат N элемента из конца в связанном списке
  • Удаление дубликатов из связанного списка

Графы


Граф-это набор узлов (вершин), которые соединены друг с другом в виде сети ребрами (дугами).



Бывают


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

Встречаются в таких формах как


  • Матрица смежности
  • Список смежности

Общие алгоритмы обхода графа


  • Поиск в ширину – обход по уровням
  • Поиск в глубину – обход по вершинам

Вопросы


  • Реализовать поиск по ширине и глубине
  • Проверить является ли граф деревом или нет
  • Посчитать количество ребер в графе
  • Найти кратчайший путь между двумя вершинами

Деревья


Дерево-это иерархическая структура данных, состоящая из узлов (вершин) и ребер (дуг). Деревья по сути связанные графы без циклов.

Древовидные структуры везде и всюду. Дерево скилов в играх знают все.

Простое дерево



Типы деревьев

Бинарное дерево самое распространенное.

«Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. » — Procs

Три способа обхода дерева


  • В прямом порядке (сверху вниз) — префиксная форма.
  • В симметричном порядке (слева направо) — инфиксная форма.
  • В обратном порядке (снизу вверх) — постфиксная форма.

Вопросы


  • Найти высоту бинарного дерева
  • Найти N наименьший элемент в двоичном дереве поиска
  • Найти узлы на расстоянии N от корня
  • Найти предков N узла в двоичном дереве

Trie ( префиксное деревое )


Разновидность дерева для строк, быстрый поиск. Словари. Т9.

Вот как такое дерево хранит слова «top», «thus» и «their».



Слова хранятся сверху вниз, зеленые цветные узлы «p», «s» и «r» указывают на конец «top», «thus « и «their» соответственно.

Вопросы


  • Подсчитать общее количество слов
  • Вывести все слова
  • Сортировка элементов массива с префиксного дерева
  • Создание словаря T9

Хэш таблицы


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

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

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

Эффективность хеширования зависит от

  • Функции хеширования
  • Размера хэш-таблицы
  • Метода борьбы с коллизиями

Пример сопоставления хеша в массиве. Индекс этого массива вычисляется через хэш-функцию.


Вопросы


  • Найти симметричные пары в массиве
  • Найти, если массив является подмножеством другого массива
  • Описать открытое хеширование

Список ресурсов



Вместо заключения


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

Спасибо, что прочли. Надеюсь не зря потратили время =)

PS: Прошу извинить, как оказалось, перевод статьи уже был тут и очень недавно, я проглядел.
Если интересно, вот она, спасибо Hokum, буду внимательнее.
Поделиться публикацией
Комментарии 38
    +5
    Я тоже могу пробежаться по различным источникам и накатать подобную статью. В чем ее смысл? Если уж Вы начали про «многие самоучки не знают матчасть», то потрудитесь рассказать, чем предложенная в этой статье матчасть необходима самоучкам, какие проблемы возникают из-за ее незнания, в каких кейсах используются те или иные типы и почему.

    UPD. Я понимаю, что это перевод, поэтому вопрос больше риторический. Но к автору перевода аналогично-схожий вопрос, зачем Вы потратили время на перевод этого?
      –1
      Проблем как таковых не возникает, программировать можно и не сильно заморачиваясь стеки ты делаешь или очередь. Потому как многие сейчас учат язык по роликам на юутубе.

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

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

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

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


        Как это тогда понимать?

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


        Вы не привели ни одной строчки кода, чтобы это показать.

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


        Действительно, тут не просто перевод. Тут просто перечисление и ни одного ответа на вопрос «Зачем это нужно знать», «В чем разница, кроме внешней», «Где и что используется и почему»
          0
          Как это тогда понимать?


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

          Вы не привели ни одной строчки кода, чтобы это показать.

          Извольте
          $arOne = array('a','b');


          Вы уважаемый как не читали ссылки так и не будете, так к чему это )
            +3
            Языки под веб, почти не типизированы

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

              0
              В первую очередь спасибо за статью, думаю все же она вполне может быть полезна и труд не напрасен. Но насчет вашей фразы

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


              мне не очень понятно, что за фетиш такой — «крупные компании». Если речь идет о гугл или яндекс, думаю там даже знания о том как работают хэши и что я знаю про деревья будет очень мало. И совершенно не вижу никакой необходимости работать в т.н. «крупных компаниях». Думаю понимание хэширования и умение им в нужный момент пользоваться пригодится даже в самой самой мелкой компании.
                0
                Спасибо на добром слове.

                На счет больших компаний, это не фетиш, просто бывают случаи когда приходят кодеры а их спрашивают технологии, а не кодинг, пример не в тему, но из последнего, от нас уходил пхп кодер, писал нормально, пошел в авито а там спросили «чем отличается https2 от http», он и ушел, хотя вроде простая для веб разработчика вещь. Но в кодинге не нужна и он с этим отличием не сталкивался сам.
          +1
          Перевод ради перевода…
           <rhetoric> Зачем? </rhetoric>
            +1
            Отчего же так критично, во-первых если вы сходите на оригинал вы увидите, что он меньше, я не зря писал источники другие.
            Во-вторых, чтение ради чтения получается по вашему, я специально указал что это азы, просто в стримах на ютубе не рассказывают, а это есть )

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

            Я хотел напомнить за кодингом есть еще пласт знаний. Да про них если ты кодишь под веб можно и не думать вообще, а можно и пробежаться для ликбеза
              0
              Критично, потому что мне была интересна эта тема (как раз потому что я самоучка), в первых абзацах я решил, что тут действительно что-то интересное. И впоследствии узнав, что статья — пустышка, мое разочарование было настолько сильным, что я даже оставил комментарии под этой статьей.
              0
              В стримах может и не рассказывают, но есть же каналы, где ну очень много очень разнообразной информации, Володя Моженков, к примеру, и по базовым структурам и по алгоритмам роликов наснимал.
              +5
              И если вы самоучка и надолго в программировании пробегитесь по статье

              Я самоучка, в программировании в этом году как двадцать лет, и надеюсь здесь и оставаться.


              Пробежался по статье. Нашел ошибку, неточность, неактуальный список вопросов, снова ошибку, надоело, бросил.


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


              P.S.


              По сути это [хэштаблица] ассоциативный массив, в котором ключ представлен в виде хеш-функции.

              А что такое ассоциативный массив?

                –1
                Спасибо, что прочли. Про неточности и особенно вопросы, не буду спорить, вы 21 год в профессии, конечно вы их видите, а те кто год или два увидят? Не обязательно
                А новые слова они могут увидеть, пойдут по ссылкам пощелкают

                Про ассоциативные массивы не упомянул, это проглядел, сейчас поправлю
                  +2
                  Про неточности и особенно вопросы, не буду спорить, вы 21 год в профессии, конечно вы их видите, а те кто год или два увидят?

                  Ну так в этом же и проблема — ошибок не увидят, и подумают, что так и правильно. А нет.


                  А новые слова они могут увидеть, пойдут по ссылкам пощелкают

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

                  0
                  На интервью такие приходят

                  любом разумном
                  не лукавьте не любом, считать ли стрим по пхп обучающим материалом?
                    0
                    На интервью такие приходят

                    Какие "такие"?


                    не лукавьте не любом, считать ли стрим по пхп обучающим материалом?

                    Никогда не видел и не слышал "стримов по пхп", ничего не могу сказать. А вот считать ли вашу статью обучающим материалом?

                      0
                      Но вы почему-то утверждаете, что люди этого не знают.

                      Которые этого не знают.

                      Нет, я не претендую на этот статус, я буду вполне рад если ознакомительным.
                        +1
                        Которые этого не знают.

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


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

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


                        (Вы, что характерно, так и не поправили описание хэш-таблицы на правильное)

                          0
                          ко мне на собеседование, и начинают мне рассказывать


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

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

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

                            Не поправлю, а зачту неправильный ответ.


                            Спасибо еще раз, что показали где не прав

                            Эм. У вас ошибки разбросаны по всей статье.

                              0
                              А вот это думаю зря, отчего не поправить, но это уже дело ваше.

                              Да, да, вы писали об этом, я помню это замечание.
                                0
                                А вот это думаю зря, отчего не поправить, но это уже дело ваше.

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


                                Да, да, вы писали об этом, я помню это замечание.

                                Но ничего с ним не делаете.

                                  0
                                  А вот это думаю зря, отчего не поправить, но это уже дело ваше.


                                  Зачем тратить оплачиваемое время специалиста на обучение человека, который за свою карьеру/обучение не удосужился прочитать 1 (одну!!!!) несложную книжку? Зачем он вообще такой нужен? Знаете сколько таких ходит по собеседованиям и тратит чужое время?
                            +1

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

                              0
                              Я отвечу, что такого вопроса в заметке и не ставилось, однако думаю вас ответ не удовлетворит )
                                +1

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

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

                                  Спасибо еще раз за ваше мнение.
                                    +2

                                    Нет, она (дискуссия) про то, есть ли польза от вашей статьи, или нет.

                        0
                        9 августа был опубликован перевод этой же статьи: habr.com/company/alconost/blog/419685
                        Бегло сравнив две публикации, я не нашел принципиальных различий. Зачем делать еще один перевод одного и того же? Может стоило написать статью посвещенную этой теме, учесть в ней замечания к первому переводу и размещать уже не как перевод, а как свою собственную работу?
                          0
                          Да, вы правы, стоило, я не нашел эту статью, видимо плохо искал. Спасибо, что указали на это, буду лучше выбирать темы ((
                            0
                            Там не менее паршивый перевод очень паршивой статьи.
                          0
                          Trie представлено нерационально: зачем хранить пустые связи типа e -> i -> r, по ссылке от h, если вместо этого можно хранить просто суффикс «eir» и разбить его на компоненты только тогда, когда нужно будет вставить какой-нибудь «they»?
                            +1

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

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

                            Некоторые куски текста (например описание связного списка) прямо из википедии скопированы.
                              –1
                              Автор, очень хорошая статья. Мне очень понравилось что вся информация собрана в одном месте и написано коротко и по сути.
                                0
                                Спасибо =)
                                Это перевод, правда, я не совсем автор, я только собрал
                                  0
                                  коротко и по сути.

                                  … и неправильно в ряде мест. Вы все их нашли?

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

                                Самое читаемое