Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-03-10

1 <ul><li><a>Изучаем структуры данных: что это?</a></li>

2 <li><a>Изучаем структуры данных: зачем вообще они нужны?</a></li>

3 <li><a>Изучаем структуры данных: топ-8</a></li>

4 <li><a>Массивы</a></li>

5 <li><a>Стеки</a></li>

6 <li><a>Очереди</a></li>

7 <li><a>Связный список</a></li>

8 <li><a>Графы</a></li>

9 <li><a>Деревья</a></li>

10 <li><a>Бор</a></li>

11 <li><a>Хэш-таблица</a></li>

12 </ul>В далеком 1976 году швейцарским ученым была написана книга "Алгоритмы + Структуры данных = Программы". Прошло уже более сорока лет, но это утверждение до сих пор актуально. Вы должны знать структуры данных, если учите языки программирования и желаете стать разработчиком. И не только знать, но и уметь их применять. Причем не столь важно, закончили ли вы институт либо просто освоили курсы программирования, - на собеседовании при устройстве на работу у вас в 90 % случаев спросят про структуры данных.

13 Этот материал - адаптированный перевод статьи "<a>The top data structures you should know for your next coding interview</a>". В этом переводе будут вкратце рассмотрены основные структуры данных, которые могут понадобиться при программировании, плюс будут перечислены наиболее популярные вопросы, которые часто задают на собеседованиях.

14 <h2>Изучаем структуры данных: что это?</h2>

15 Если говорить простым языком, то структура данных представляет собой контейнер, в котором информация скомпонована специальным образом. Чего удается достичь благодаря такому строению? Для сравнения, скажем, что при выполнении одних операций определенная структура данных будет весьма эффективна, в то время как при выполнении других - не очень. Задача разработчика вне зависимости от языка программирования (language of programming) как раз в том и состоит, чтобы уметь выбирать наиболее подходящую структуру и знать, как сравнить их между собой с учетом поставленной задачи. Но это невозможно без ясного и единого представления о существующих способах организации информации. Именно это единое представление вы и получите в процессе изучения материалов этой статьи. И займет это совсем немного времени.

16 <h2>Изучаем структуры данных: зачем вообще они нужны?</h2>

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

18 Ниже перечислены самые распространенные способы структурирования данных:

19 <ol><li>Массивы.</li>

20 <li>Очереди.</li>

21 <li>Стеки.</li>

22 <li>Деревья.</li>

23 <li>Связные списки.</li>

24 <li>Графы.</li>

25 <li>Боры.</li>

26 <li>Хэш-таблицы.</li>

27 </ol><h2>Массивы</h2>

28 Самый распространенный способ структуризации. Ниже показан простейший массив из 4-х элементов:

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

30 Массивы бывают:

31 - одномерные (как на картинке);

32 - многомерные.

33 Простейшие операции:

34 <ul><li>Insert - вставка элемента на позицию с заданным индексом;</li>

35 <li>Get - возвращение элемента, занимающего позицию с заданным индексом;</li>

36 <li>Delete - удаление;</li>

37 <li>Size - получение общего числа элементов.</li>

38 </ul>Какие вопросы, связанные с массивам, часто задают на собеседовании:

39 <ul><li>найдите 2-й минимальный элемент;</li>

40 <li>найдите неповторяющиеся целые числа;</li>

41 <li>выполните объединение двух отсортированных массивов;</li>

42 <li>выполните упорядочение положительных и отрицательных значений.</li>

43 </ul><h2>Стеки</h2>

44 Стек обычно сравнивают со стопкой книг. Когда нужно взять какую-либо книгу, к примеру, лежащую в центре стопки, вам надо сначала снять те книги, которые лежат выше. Это известный принцип LIFO (кто последний пришел, тот первый выйдет).

45 На картинке ниже - стек, который содержит 3 элемента:

46 Простейшие операции:

47 <ul><li>Push - вставка элемента в стек сверху;</li>

48 <li>Pop - возвращение верхнего компонента в стек после удаления;</li>

49 <li>isEmpty - возвращение true, когда стек пуст;</li>

50 <li>Top - возвращение верхнего компонента без удаления его из стека.</li>

51 </ul>Вопросы о стеке:

52 <ul><li>вычислите постфиксное выражение посредством стека;</li>

53 <li>отсортируйте значения;</li>

54 <li>проверьте сбалансированные скобки в выражении.</li>

55 </ul><h2>Очереди</h2>

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

57 Изображение очереди:

58 Операции:

59 <ul><li>Enqueue() - добавление элемента в конец очереди;</li>

60 <li>Dequeue() - удаление элемента из начала;</li>

61 <li>isEmpty() - возвращение true, если очередь пуста;</li>

62 <li>Top() - возвращение первого элемента.</li>

63 </ul>Вопросы:

64 <ul><li>реализовать стек посредством очереди;</li>

65 <li>обратить первые k-элементы в очереди;</li>

66 <li>сгенерировать двоичные числа от 1 до n, используя очередь.</li>

67 </ul><h2>Связный список</h2>

68 Эта структура напоминает массив, но если выполнить сравнение, становится понятно, что связный список отличается по ряду характеристик:

69 - выделение памяти;

70 - внутренняя структура;

71 - особенности вставки и удаления.

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

73 Применение - реализация файловых систем, хэш-таблицы, списки смежности.

74 Типы:

75 <ul><li>односвязный (однонаправленный);</li>

76 <li>двусвязный (двунаправленный).</li>

77 </ul>Простейшие действия:

78 <ul><li>InsertAtEnd - вставка заданного элемента в конец;</li>

79 <li>InsertAtHead - вставка в начало (с головы);</li>

80 <li>Delete - удаление из списка;</li>

81 <li>DeleteAtHead - удаление первого компонента;</li>

82 <li>Search - возвращение заданного компонента из списка;</li>

83 <li>isEmpty - возвращение true, если имеющийся список пуст.</li>

84 </ul>Вопросы:

85 <ul><li>обратить связный список;</li>

86 <li>найти петлю;</li>

87 <li>вернуть N-ный узел с начала списка;</li>

88 <li>удалить дублирующиеся значения.</li>

89 </ul><h2>Графы</h2>

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

91 Типы:

92 <ul><li>неориентированные;</li>

93 <li>ориентированные.</li>

94 </ul>В языке программирования популярны графы 2-х типов:

95 <ul><li>матрица смежности;</li>

96 <li>список смежности.</li>

97 </ul>Также надо знать самые популярные алгоритмы обхода графа:

98 <ul><li>поиск в ширину;</li>

99 <li>поиск в глубину.</li>

100 </ul>Вопросы к собеседованию, которые желательно проработать:

101 <ul><li>реализация поиска в ширину и глубину;</li>

102 <li>проверка, является ли граф деревом;</li>

103 <li>подсчет числа ребер;</li>

104 <li>поиск кратчайшего пути между 2-мя вершинами.</li>

105 </ul><h2>Деревья</h2>

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

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

108 Ниже - рисунок простого дерева:

109 Деревья бывают разных типов:

110 <ul><li>N-арное;</li>

111 <li>сбалансированное;</li>

112 <li>двоичное;</li>

113 <li>двоичное дерево поиска;</li>

114 <li>АВЛ-дерево;</li>

115 <li>красно-черное дерево;</li>

116 <li>2-3 дерево.</li>

117 </ul>Сегодня широко используют двоичные деревья.

118 На собеседовании у вас могут попросить найти:

119 <ul><li>высоту двоичного дерева;</li>

120 <li>k-ное максимальное значение в 2-чном древе поиска;</li>

121 <li>узлы, которые расположены на расстоянии “k” от корня;</li>

122 <li>предки заданной вершины в 2-чном дереве.</li>

123 </ul><h2>Бор</h2>

124 Второе название - "префиксное дерево". Речь идет о древовидной структуре, которая весьма эффективна в процессе решении задач на строки. Бор обеспечивает быстрое извлечение информации и часто используется при поиске слов в словаре, автоматических завершений в поисковике, а также в IP-маршрутизации.

125 Давайте посмотрим, как 3 слова "top", "thus" и "their" хранятся в бору:

126 Вопросы:

127 <ul><li>подсчет общего числа слов, которые сохранены в бору;</li>

128 <li>вывод на экран всех слов, сохраненных в бору;</li>

129 <li>сортировка элементов массива посредством бора;</li>

130 <li>построение слова из словаря;</li>

131 <li>создание словаря T9.</li>

132 </ul><h2>Хэш-таблица</h2>

133 Хэширование используется в целях уникальной идентификации и сохранения объектов по вычисленному индексу, который называют "ключом". В результате объект хранится в формате "ключ-значение", а коллекция этих объектов представляет собой "словарь". Поиск объекта осуществляется по его ключу. Есть разные структуры данных, которые построены по принципам хэширования, к примеру, широко известна хэш-таблица(обычно ее реализуют посредством массивов).От чего зависит производительность хэширующей структуры:

134 <ul><li>от хэш-функции;</li>

135 <li>от размера хэш-таблицы;</li>

136 <li>от метода обработки коллизий.</li>

137 </ul>Что могут спросить:

138 <ul><li>поиск симметричных пар;</li>

139 <li>отслеживание полной траектории пути;</li>

140 <li>поиск, является ли массив подмножеством другого массива;</li>

141 <li>проверка, можно ли назвать массивы непересекающимися.</li>

142 </ul>Надеемся, этот перевод был вам полезен, и теперь вы имеете единое понимание основных структур данных, которые должен знать каждый разработчик. Мы уверены, что предоставленная информация обязательно поможет на собеседовании по программированию. Успехов!

143