0: Добро пожаловать на мой канал. В этом видео я разберу такую тему, как структуры данных. Начнём с того, а что же вообще такое эти структуры данных? Описание этого понятия сводится к 1 предложению. Это контейнер.

1: Который хранит данные в организованном виде. Возможно, это предложение сейчас не совсем понятно, так что давайте рассмотрим на конкретном примере. Допустим, вы переехали в новый город и вам нужно понять, куда вы можете доехать на машине.

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

3: Например, до магазина одежды, но вот обратно доехать никак не получится, потому что эта дорога с односторонним движением, а вот от дома до продуктового магазина можно проехать по данной дороге и по этой же дороге вернуться обратно теперь перед вами стоит

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

5: От дома до магазина продуктов, от магазина продуктов до дома, от продуктового магазина до магазина одежды и так далее. Из этой информации, похожей на список, вы можете понять все тоже самое, что и из графика.

6: Однако эта информация понятна не только вам, но и компьютеру он видит, что 1 элемент это тот, откуда можно дойти, a2 куда ладно, это лишь 1 из вариантов хранения, другой же способ перечисления каждой.

7: Контрольной точки, расположенной на графике. При этом добавляя все места, куда вы можете отправиться из данной позиции. При таком раскладе ваши данные будут выглядеть вот примерно таким образом, как вы видите, здесь у нас есть таблица, где

8: В левой части перечислены здания дом, продуктовый магазин, магазин одежды, ресторан, школа, детский садик, справа в таблице находится список всех мест, куда вы можете отправиться. Таким образом, у нас есть 2 ра.

9: Разных метода хранения 1 и той же информации. Данные, которые хранят и предоставляют эти списки, одни и те же. Но вот структура у них отличается для главного осознания того, чем же структуры отличаются и зачем нужно такое разнообра.

10: Среди них поймём вот что. У нас есть 3 операции. Вставка. Например, к нашей карте нужно добавить новое здание. Операция. Вставка отвечает за это удаление, стирает с карты любой объект и, соответственно, поиск.

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

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

13: Что 4 пустые, а в 1 лежит конфета. Единственный способ узнать, в каком лежит конфета, открыть коробку и проверить содержимое. Бего говорит мне по моей оценке, тебе нужно открыть все коробки, чтобы добраться до конфеты. Омега же.

14: Утверждает, что в лучшем случае тебе придётся открыть от 1 до 3 коробок, а тета говорит, что в среднем нужно открыть от 3 до 5 коробок. Нам, как программистам интереснее всего средний и худший исход зна.

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

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

17: Сложность будет константой. Это значит, что мне неважно, сколько коробок передо мною. Я всегда открою нужную. Последняя сложность, которая нам понадобится. Логарифмическая. Она хуже, чем константа, но лучше, чем линейная. Если вы не понимаете, что она отражает, то

18: Вот вам пример. Я загадал число, оно находится в диапазоне от нуля до 9. Ваша задача его отгадать, что лучше всего сделать? Назвать число посередине, а затем спросить, больше оно или меньше его, допустим, боль.

19: Хорошо, отбрасываем левую часть и называем снова число посередине моё загаданное число меньше чем 7 получается, остаётся выбор из 2, тут уж чистый рандом, и суть заключается в том, что удвоение диапазона ли?

20: Добавит 1 лишний шаг в поиске нужного числа. Вот это и есть логарифмическая сложность. Замечательно вроде бы с тем, что такое структуры данных и как они работают. Мы разобрались. Что ещё хотелось бы сказать, прежде чем мы приступим к разбору конкретных

21: Структур, данных в этом видео на YouTube, собраны те структуры, которые необходимы для общего понимания данной темы, если вам интересны более продвинутые знания, как работают деревья, чем сбалансированное дерево отличается от обычного, какие виды?

22: Деревьев существуют и много ещё чего, что не вошло в это видео, есть у меня на бусте. Оно доступно для всех, кто приобрёл минимальный уровень доступа. К тому же, приобретая подписку, вы не только получаете полный курс по структурам данных, но вам ещё и открывается доступ.

23: К эксклюзивным видео, тестам, статьям это только то, что есть сейчас со временем бонусы будут добавляться и улучшаться. А как только на моём бусте аккаунте наберётся 500 платных подписчиков, я устрою большой

24: Розыгрыш среди них заранее спасибо за вашу поддержку. 1 структура, которую мы разберём, будет массив массив, это набор элементов 1 типа. Вы можете визуализировать массив как набор коробок, расположенных в ряд. У каждой коробочки будет свой

25: Номер, по которому можно будет обратиться, причём желательно хранить во всех коробках один и тот же тип данных. Можно, конечно, изощрёнными способами расположить разные типы данных в каждой из коробочек, но это крайне нежелательно, объявляется массив.

26: 2 способами. 1 это чисто джавовский вариант, a2 пришёл с языка си инициализируется массив тоже 2 способами. Когда мы указываем содержание сразу это делается в фигурных скобках через запятую, либо через

27: Оператор нью. Далее тип данных. И в скобках говорим длину массива. После того, как длина массива обозначена, мы не можем её изменить. Такая структура называется статическим массивом. Во 2 случае наш массив будет состоять из

28: С 000000000 это происходит потому, что я лишь указал длину массива, а не заполнил его. Чтобы обратиться к какой-то ячейке, нужно использовать ссылку на массив, а в скобках указать номер ячейки. Нумерация идёт от нуля. То есть у 1 ячейки будет индекс.

29: 0 2, 1, у 3 2 и так далее. Так вот, я обращаюсь к 1 элементу в массиве и присваиваю ему значение. Посмотрим, как выглядят наши массивы. А видим мы следующее. 1 массив заполнен теми значениями.

30: Которые мы указали при инициализации, a2 массив заполнен лишь наполовину как мы помним, у целочисленного типа данных значение по умолчанию 0 это значит, что изначально созданный массив через оператор new был полностью заполнен нулями.

31: Далее, через прямое обращение к ячейке по её номеру мы меняем значение. Менять значение можно сколько угодно. Раз. То, что мы сейчас разобрали, называется одномерным статическим массивом. Конечно, полным именем его никто не называет, потому что он явля.

32: Является стандартом, то есть обычным массивом. А вот у его модификации в названии указывается особенность. Например, двумерный массив, двумерный массив это конструкция, состоящая из столбцов и строк. Каждая строка это отдель

33: Массив проще всего, конечно, двумерный массив представить как шахматное поле или поле для игры в крестики нолики, и хотя такая форма квадратная, используется в 99 процентах случаях, но это не значит, что нельзя сделать двумерный массив.

34: В виде буквы е или буквы г. Раз каждая строка в двумерном массиве это отдельный массив, то это значит, что он может иметь свою длину, отличную от длин других массивов в этой структуре для того, чтобы создать 2 д массива в java.

35: Также существует 2 варианта 1 когда в фигурных скобках мы напрямую указываем содержание массивов, а так как двумерный массив это массив из множества других массивов, то указывать мы должны содержание этих массивов тоже в фигурных скобках это 1 строка.

36: Потом через запятую, 2, 3 и 4. 2 же способ инициализации это указание количества строк и столбцов строки столбцы для того, чтобы обратиться к какому-то элементу, нам надо сначала указать номер строки, а затем

37: Номер столбца прям как в морском бое. Что нам делать, если мы хотим пройтись по двумерному массиву? Сначала, как обычно, создаём цикл, но эта конструкция пробегает лишь по строкам массива 1 строка 2, 3, 4.

38: Чтобы у конкретной строки вызвать столбец, нам нужно сделать вложенный цикл for. Остановиться цикл должен в тот момент, когда он дойдёт до конца строки. Ещё раз мы заходим в цикл. 1 значение будет 0. То есть

39: 1 строка далее мы заходим во вложенный цикл, который пробегается по столбцам 0 0 0 1, 0 2 0 3. Как только вложенный цикл дойдёт до конца, он завершит свою работу и отдаст управление внешнему циклу внешний цикл.

40: Бавят к. А единицу тем самым перескочит на другую строку. Потом мы снова зайдём во внутренний цикл и пробежимся уже по 2 строке. Эта итерация будет повторяться до тех пор, пока не закончатся строки в двумерном массиве теперь.

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

42: Что-нибудь простое. Например, таблицу умножения выводить мы будем произведение номера строки и номера столбца, только не забываем, что нумерация начинается с нуля, а это значит, что для нормального вывода прибавляем единичку к обоим параметрам.

43: В завершении цикла переводим на следующую строку в консоли.

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

45: Может изменять свой размер на ходу. В этом примере у меня есть динамический массив размером в 5 элементов. Этот массив заполнен какими-то данными, но на самом деле мой массив выглядит примерно вот так. Давайте разбираться изначально у нас

46: Есть статический массив под этот массив наше приложение выделяет конкретное место в памяти, далее на этот массив накладывается обёртка, например, в java, это array, list в python, list, в си и си плюс плюс вектор.

47: Эта обёртка внутри себя хранит ссылку на этот массив памяти, а нам, как пользователям, говорит у меня есть определённая ёмкость. Эта ёмкость зависит от того, сколько изначально места в памяти выделено под статический массив. А так.

48: У меня есть размер. Этот размер будет зависеть от количества объектов, хранимых мною. Положишь в меня 1 объект. Значит, мой сайсс будет равен 1. Положишь 2, будет равен 2. Но как только ты заполнишь.

49: Меня, например, на 70%, то мне придётся создать новый статический массив в полтора раза больше, чем нынешний. И только потом ты можешь класть в меня объекты. Как вы понимаете, создание нового массива, копирование содержимого

50: Из старого массива в новый занимает ресурсы системы, но при этом у нас есть структура данных, которая при необходимости сама себя расширяет. Перейдём в среду разработки, создадим объекты динамического массива и

51: Перейдём в класс array, лист. Что мы можем здесь увидеть интересного? Изначально массив имеет размер в 10 элементов. Посмотрим, какие конструкторы есть в этом классе. С помощью 1 мы можем задавать изначальную длину хранимого массива.

52: Это релевантно в тех случаях, когда мы уверены в том, что наш массив будет хранить какое-то количество элементов. Например, больше 100. В таком случае мы в конструкторе передаём число 100, и наш массив выделит память под

53: 100 элементов главное тут не перемудрите, потому что память приложения ограничена. А если вы будете выделять память под массивы, при этом их не заполняя, из этого ничего хорошего не выйдет. 2 конструктор это конструктор по умолчанию.

54: И по умолчанию его длина будет равна 10. Ну и последний случай это когда мы передаём коллекцию в аргументе конструктора, тем самым создавая клон. Причём, заметьте, мы можем передать любую структуру данных, которая наследуется от интерфей.

55: Collection вернёмся к новосозданному динамическому массиву и вообще проверим, какой у него размер, пустой ли он, и взглянем, что он содержит изначально наш динамический массив, пустой его размер равен нулю и is empty показывает тру давайте.

56: Попробуем добавить несколько элементов в наш массив, запустим и в консоли видим состояние данной коллекции. Теперь проверим следующее. Зададим изначальную ёмкость массива. Пусть будет 20. Создадим цикл, который добавит 40 элементов.

57: Наш массив и проверим результат. И, как мы видим, изначальная ёмкость равна 20, но финальный размер размер равен 40. Изначальная ёмкость массива равна 20, а размер нулю. Когда было доба

58: Добавлено 15 элементов. В динамический массив java увидела, что massive, под который выделялась память, был заполнен на 75%, далее был создан ещё 1 массив только размером уже на 50% больше, чем

59: Предыдущий, то есть память была выделена под размер массива в 30 элементов, потом уже существующий массив был скопирован в новосозданный и объект, динамика рей внутри себя уже ссылается на этот наш новый массив, а старый

60: Так как на него никто не ссылается, был очищен сборщиком мусора, когда 75% и от этого массива было заполнено, тогда итерация повторилась. По идее, цикл расширения повторялся 3 раза, в конце которого ёмкость она же

61: Пасти должна быть равна 68. Поэтому, кстати, лучше сразу обозначить примерную ёмкость динамического массива. Представьте, что ваш массив должен содержать 1000 элементов, а вы не указали изначальный объём, и он будет начинаться

62: Со стандартных 10 ячеек памяти, потом расшириться до 15, далее до 23 и так далее. Все эти действа потребляют ресурсы. Не лучше ли сразу оптимизировать процесс, опять же, оптимизировать, а не выделять память под

63: 1000 элементов, а хранить в массиве всего 10. Замечательно. Следующая структура данных это стек. Лично мне нравится представлять себе стек как тарелку с блинами. Тогда тарелка это контейнер, который хранит наши данные, а блины и есть

64: Те самые данные сначала я кладу на тарелку блин, под названием skyrim, далее кладу minecraft na скайрим, потом ведьмака gta, а завершает мою тарелку фоллаут. Теперь я хочу пройтись по содержи.

65: Данной структуры в обычном массиве 1 был ббы скайрим, потому что он был добавлен 1, однако в стеке все наоборот 1 будет fallout, так как он лежит сверху, посмотрим, как это выглядит в java сначала.

66: Объявляем тип объекта стек дженерики, указываем хранимый тип данных в этой структуре. Даю имя и через new создаю экземпляр. Теперь, чтобы положить что-то в стек, мне необходимо выполнить метод пуш. Добавим в том же порядке.

67: Элементы, что и в теоретическом примере выведем в консоль пока все тоже самое, что и в обычном массиве теперь попробуем в некую переменную элемент положить 1 доступную запись и что мы видим мы получили

68: Fallout, он как раз сверху лежал. Это так называемое лифо или последний пришёл, 1 ушёл, но это не самое интересное. Данный элемент пропал из объекта стек. Как так получилось? Это из за особенности метода.

69: Поп он достаёт последний положенный элемент стек, попутно удаляя его из этого самого стека. Но что, если я хочу получить определённый элемент, не удаляя его из структуры, тогда нам надо использовать метод get.

70: Все как и в обычном массиве, например, если мы хотим получить объект minecraft, то можно сначала найти индекс данного объекта, а потом получить его.

71: Выведем в консоль и увидим, что данный объект все ещё в стеке вообще такая структура данных, как стек, используется потоками в java потоки используют стек как место для хранения локальных переменных и вре.

72: Данных данный подход довольно эффективен и безопасен для java помимо того, что его легко реализовать довольно быстро и просто создавать отдельный стек для каждого потока, так ещё он мало потребляет памяти, и благодаря его структуре можно.

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

74: Которую будем возвращать и создаём условия для выхода из рекурсии. Что такое факториал факториал это произведение всех натуральных чисел до заданного числа. То есть факториал 5 будет равен 1 умноженное на 2, умноженное на 3, умноженное на

75: 4 и на 5. Умножение на единицу не даёт никакого эффекта, так что когда н будет равен единице, то рекурсия закончится. Далее вызываем саму рекурсию. Ну и в конце вернём результат. Например, мы вызываем метод и передаём его

76: Ему число 5, далее он внутри себя создаст некую переменную result и присвоит ей значение n, умноженное на результат вызова функции н - 1, то есть 4 данная рекурсия будет происходить до тех пор, пока число

77: Н не станет равно единице, потому что в таком случае, когда у нас, н равно единице просто вернётся переменная result, так как поток работает на такой структуре, как stuck, то разворачиваться она будет в обратном порядке, сначала вернётся результат с послед.

78: Вызванного метода, он равен единице. Мы эту единицу умножаем на 2, потому что в методе н. Равен 2. Потом мы доходим до н. Равному 3, то есть 2 * 3. Затем мы умножаем на н в размере 4, и в конце мы умножаем на 5

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

80: Большую рекурсию. Наше приложение рухнет, вызвав ошибку стек оверфлоу. Следующие структуры данных это очереди. Тут, наверное, самое простое сравнение. Сравнение с обычной очередью людей в магазине, в аптеке, в аэропорту.

81: Как мы помним, стек работает по принципу последний пришёл, 1 ушёл, обычная же очередь устроена по принципу 1 пришёл, 1 ушёл, и, по сути, данная коллекция предназначена для хранения элементов. Перед обработкой она не является полноценной структур.

82: Данных, как и стек. Опять же, возвращаясь к очереди из людей, все эти люди хотят заказать вкусную еду. Допустим, ты пришёл 3, тогда твоя очередь наступит только в тот момент, когда 1 и 2 перед тобой.

83: Исчезнут. Если же ты пришёл 1, то ты 1 и уйдёшь. Я упомянул, что очередь это лишь этап перед обработкой. Все верно. Очередь это всего лишь интерфейс, у которого множество реализаций. Очередь может быть.

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

85: Очередь возьмём за основу динамический массив при добавлении в него нового элемента он становится за тем элементом, который был добавлен до него обратная очередь позволяет вставлять элементы в самое начало, но это не самое важное важнее.

86: То, как мы можем пробежаться по данному массиву, жёлтая и синяя стрелочки это указатели, когда мы вызываем метод, который берет 1 элемент из массива. Тогда жёлтая стрелочка становится на голову массива. Тот, на кого она будет указывать, попадёт под наш

87: Метод, он будет Достан из массива и доставлен туда, откуда был вызван метод. Очередь сократится, а жёлтый указатель теперь будет показывать на следующий элемент. Но это же обратная очередь. Значит, у нас есть ещё и стрелочка в кон.

88: Массива так называемом хвосте, а это уже получается, что мы можем взять последний элемент массива, прям как в стеке или на тарелке с блинами вызываем метод пол ласт и теперь уже исчезнет последний элемент из массива, а синий указа

89: Перейдёт к последнему существующему элементу, то есть получается, что dq так называемая двунаправленная очередь позволяет брать не только по принципу 1 пришёл, 1 ушёл, так ещё и по принципу последний пришёл, 1 ушёл.

90: Посмотрим на примере рейде кью. Для начала создадим простенький, подже класс людей, который будет состоять из полей. Имя, фамилия и возраст. Теперь перейдём к созданию структуры данных. На основе обратной очереди. Мы поняли, что все очереди

91: Которые существуют. Это интерфейсы, а значит, что нельзя создавать объекты из них. Следовательно, нам нужен какой-то класс, который реализовывал бы обратную очередь. Самая известная реализация декьюбелис лист. Но его мы рассмотрим чуть

92: Позже. А сейчас воспользуемся рейде кью. Это динамический массив. С обратной очередью добавлю в эту коллекцию несколько людей. А теперь самое интересное я могу взять из массива 1 или последнего человека прове.

93: Проверим сначала изначальную ёмкость массива, затем возьмём 1 элемент, потом 2, а в конце проверим, изменился ли массив. Мы видим, что 3 элемента хранится в нашем массиве. 1 в нашей очереди Антон Антонов. А

94: Последний в очереди Пётр Петров и в конце тоже 3 элемента. То есть, по сути у нас есть обычная очередь, где 1 элемент пришёл 1 ушёл и есть обратная очередь, где последним пришёл, 1 ушёл прям.

95: Ещё 2 метода пол ласт, который получает последний элемент и убирает его из очереди пол ласт и есть пол ферст, который берет 1 элемент и убирает его из очереди.

96: Полним код ещё раз и заметим, что из нашего массива пропало 2 элемента сначала в порядке обычной очереди, как в магазине ушёл Антон, а потом, как в стеке или с тарелки блинов, ушёл Пётр, то есть последний из очереди и в конце.

97: Остался лишь Василий. Помимо обычного метода добавления мы ещё и можем выбирать, куда пойдёт наш элемент. Например, я хочу, чтобы Василий стал 1 в очереди. Но если я этот же метод эт ферст

98: Добавлю Петру, то 1 в очереди уже станет он перед василием. Давайте посмотрим, так ли это. Да, и, как мы видим, 1 у нас идёт Пётр, последний Антон, ну и 2, соответственно, Василий, значит, что произошло сначала в нашу оче,

99: Очередь. 1 стал Антон, у него 0 индекс. Потом мы с помощью метода эт ферст добавили василия, и уже он приобрёл индекс 0, а Антон переместился под индекс 1. А когда мы вызвали метод эт ферст для петра,

100: То он стал под индексом 0, а все остальные элементы, которые уже находились в очереди, переместились на 1 index вперёд, превосходно, сейчас мы рассмотрим такую структуру данных, как связанный список, связанный список это структура данных.

101: Для хранения набора элементов. Допустим, у меня есть несколько чисел, я бы мог их расположить в массиве, а потом по индексу определённой ячейки я бы мог обратиться к какому-то конкретному числу. Связанный список устроен по другому. Если массив это мно,

102: Множество ячеек, объединённых в 1 монолитную структуру, то связанный список это набор из множества блоков, соединённых друг с другом прямо как звенья цепи эти блоки могут быть связаны в 1 сторону либо связаны друг.

103: С другом. Когда блок имеет связь с тем блоком, который идёт до него и на блок спереди, то список становится двунаправленным. В связанном списке данные хранятся в ноде Нода. Это блок, состоящий из данных и.

104: И ссылок на следующую или на следующую и предыдущую ноду фишка линкит листа в том, что каждая Нода может храниться где угодно вообще в любом доступном участке памяти, но как тогда 1 ноде ссылаться на другую, а делать она?

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

106: Какое-то количество байт. Так вот, если мы берём все тот же массив, то для него обязательно выделять смежные ячейки. А вот нодам все равно, где располагаться. 2 ноды 1 списка могут находиться в разных частях памяти свя.

107: Зываются они между друг другом посредством условного номера в памяти, безусловно, все это сложнее устроено, но общая картина понятна. Нода хранит данные и индекс участка памяти следующей или предыдущей ноды, если

108: Если у ноды нет адреса на следующий элемент, то такая Нода считается хвостом, а так как линкит лист в java реализует двунаправленную очередь, то мы можем проходить по элементам как с начала, так и с конца, однако у вас мог возникнуть вопрос каждый.

109: Элемент имеет ссылку на следующий. Либо, если ссылки нет, то данная Нода является хвостом, но на начало линкит листа никакая другая Нода не ссылается, так как нам получить доступ к 1 ноде. А для этого нам нужен указатель с помощью

110: Которого мы могли бы достать. 1 элемент. Его ещё называют головой. В чем разница между динамическим массивом и связанным списком. 1, что бросается в глаза, так это то, что в массиве мы можем получить любой элемент по его

111: Индексу, а вот в списке, чтобы достать что-либо, что не является хвостом или головой, надо пройтись по всему списку до Нужных данных. 2 отличие. Если я хочу расширить массив, то мне необходимо для этого создать новый

112: Большего размера, затем скопировать все данные из предыдущего и вставить в новый для добавления новой ноды требуется лишь добавить ссылку, чтобы провести операцию удаления из начала массива. Мне нужно сделать

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

114: То для связанного списка это сделать на раз. 2 конкретные методы мы рассматривать не будем. Мы их разобрали уже при разборе очередей. А вот на сравнение 2 структур мы взглянем релист против линкид лист. 1 на очереди будет добавление

115: Элемента в начало для ray листа необходимо указывать индекс ячейки, в которую мы хотим поместить данные, а у связанного списка есть метод add ферст из интерфейса де que запустим ну тут уже после.

116: 1 раза все понятно, но для объективности сделаем тест ещё пару раз, 1, 2.

117: Да, добавление элементов в начало у линкит лист в 100 раз быстрее, чем у динамического массива. Теперь сравним добавление в середину массива и в середину связанного списка.

118: Но прежде чем я запущу данное сравнение, ответьте на вопрос, что будет быстрее, по вашему мнению, подумали теперь я запущу процесс.

119: Ой, внезапно оказалось, что добавление в середину массива намного быстрее, чем добавление нового элемента в середину линкит листа. Давайте сначала исправим вывод консоль мидл и запустим ещё раз сравнение.

120: Может, у меня что-то залагало?

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

122: Элемент тогда ещё линки лист может на равных скоростях с релист это сделать, но как только нужно получить элемент не из начала и не из конца, то связанный список всегда проиграет связанный список. Хорош.

123: В тех случаях, когда нам нужно добавлять или удалять элементы сначала либо с конца, не зря, динамический массив самая популярная структура данных, a2 по популярности структура данных словари, они же хэш таблицы вот 1 из примеров слова.

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

125: Она передаст мне те значения, которые хранятся под этим ключом. Мы также можем запросить координаты Парижа. Данный словарь хранит их так что мы получим положительный ответ. А вот город Берлин наш словарь не хранит, поэтому

126: Мы не узнаем у него ширину и долготу данного города. Словарь делится на 2 части ключи и значения города. Это ключи. По ним мы можем получить значение, то есть данные, которые хранятся под определённым индексом, да?

127: Это совсем как массив, в котором есть индекс. И по этому индексу можно обратиться к конкретной ячейке, только называться данная связь будет пара ключ значения. Значит, словарь это набор пар, ключ значения или же это структура данных.

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

129: Где будут храниться данные в словарях? Такие места называются бакетами. Мы вызываем операцию добавления. Далее есть такой метод, как хэш код. Он вычисляет номер нашего объекта. Обычно хэш код возвращает.

130: Данных int, но мы же не будем создавать 4 миллиарда и 300000000 Бакетов, а именно столько хранит в себе интеджер. Поэтому мы создадим всего 5 Бакетов для тех ключей, чей хэшкод меньше 86000000.

131: Будет 1 Бакет для 2 бакета диапазон от 86000000 до 1 миллиарда 720000000, для 3 бакета от 1 миллиарда семиста 20000000 до 2 миллиардов 580000000.

132: Такой диапазон мы указываем для каждого бакета. Вот такие значения нам возвращает наш хэшкод. Понятно, что здесь 2 миллиарда 321000000. И после этого есть ещё какие-то там 1000 и сотни, но мы упустим это из виду, расставим ключи по бакетам и у нас

133: У нас выходит такая ситуация, что Анна находится в 1 бакете, ключ, в 3, Миша и Мария в 4, а Коля в самом последнем. И это при том, что мы добавляем сначала ключ, он идёт в 3 Бакет, так как его диапазон находится

134: От 1 миллиарда семиста 20000000 до 2 миллиардов 580000000. Далее у нас по Такому же принципу вставляется Миша, потом Анна, Мария и kolya. Можно, конечно же, использовать ещё 1 вариант например, использовать остаток отделения на

135: Количество Бакетов вам может показаться странным, что остаток отделения, например, у Миши равен 1, хотя у него вроде бы в конце 0, но опять же напоминаю, что это миллионы. После этого есть ещё 1000 и сотни. Соответственно, уже при таком распределении

136: Когда мы распределяем по остатку от деления на количество Бакетов, у нас выходит следующая ситуация, где Мария находится в 1 бакете, Миша во 2, ключ и Анна в 3, и Коля расположился в 4.

137: Там 5 Бакет пустует. В любом случае, какой бы способ распределения мы не выбрали. У нас всегда возникает ситуация, при которой в 1 Бакет попадёт более 1 пары ключ значения. Обычно Бакет в словаре использует связанный список. Это значит, что

138: 1 элемент содержит ссылку на 2 и так далее. Когда количество элементов будет равно количеству Бакетов, мы можем увеличить их количество в полтора или 2 раза. Мы видим, что в этом примере у нас 5 Бакетов и, соответственно, 5 элементов.

139: Значит, что делаем? Увеличиваем количество Бакетов в 2 раза. Конечно же, старые элементы распределяются по новым бакетам. Так, например, если Мария была раньше в нулевом бакете, она и осталась в нулевом. Ладно, вот Миша раньше был в бакете под

140: 1 а сейчас он находится под индексом 2. К Коле добавилась Настя, а Анна и ключ расположились в новосозданных бакетах. Операция поиска и удаления происходит по схожему пути. Мы вычисляем хэшкод ключа прове.

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

142: Чем 1, то мы будем сравнивать постепенно. Сначала с 1, потом со 2, с 3, 4 и так пока не дойдём либо до конца массива, либо пока не найдём нужный ключ. У меня Настя успешно нашлась, и выдалось значение 23, если я хочу

143: Хочу удалить пару ключ значения из hash таблицы, то мне надо провернуть все те же действия, вычислить хэш код, узнать, в каком бакете он может находиться. У меня остаток отделения на 10. Здесь будет 3. Сначала сравниваем по hash ко.

144: Коду. Если хэш код обнаружился правильный, то потом сравниваем по иквел. Если у нас и по иквел у 2 ключа равны, тогда мы удаляем эту пару. Ключ значения из бакета, как вы понимаете, чтобы словарь работал как надо у него

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

146: При 1 вызове метода хэш код пришёл ответ 8, а при повторном вызове вернулось число 1 мы должны быть уверены, что у строки Анна хэш код всегда равен, например, 8, это позволяет нам быть убеждён.

147: В том, что если конкретно в этом бакете нет такого ключа, то его и во всей структуре не будет, но, к сожалению, числа не бесконечные, и в большинстве случаев возникнет такая ситуация, где под 1 хэш кодом скрываются 2 разных

148: Ключа это нормально. Такая ситуация называется коллизия, поэтому мы сначала сравниваем по хэш коду. И если хэш код равен, то мы уже будем сравнивать по иквел и только когда ключи равны и по хэш коду, и по иквел.

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

150: В 1 Бакет не беда. Мы можем каждый раз проверять при добавлении новой пары, есть ли свободный Бакет поблизости. Если есть, то мы можем положить данный элемент в него. Да, такое действие усложняет поиск в нашей структуре, но

151: Что поделать, есть лучшее решение сделать хранение в бакете не с помощью связанного списка, а с помощью деревьев. Если у вас есть желание узнать об остальных структурах, то полное видео уже лежит у меня на бусте. Оно доступно всем.

152: При любом уровне платной подписки, надеюсь, это видео было вам полезно. В скором времени у меня выйдет видео по алгоритмам, так что до скорого результаты скидывайте в комментарии под этим видео. А теперь давайте вернёмся к самому началу, где мы пытались подобрать

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

154: Является, потому что в деревьях узлы 1 уровня не могут ссылаться друг на друга. Что же тогда получается? А получается вот что суть такой структуры данных, как граф, показать взаимодействие узлов, то есть он

155: На связях между вершинами. По сути, мне не важно, на каком уровне расположен дом или где находится магазин одежды или продуктовый магазин. А важно мне то, что дом и продуктовый магазин связаны друг с другом. Мне важно то, что дом связан со школой или

156: Магазином одежды. Если наши ребра имеют направление, а на карте они имеют, значит, наш граф называется ориентированным также в зависимости от количества рёбер вершины можно определить его степень, она может быть чётной или нечётной, но связь

157: Между нодами не ограничивается только лишь рёбрами. Есть ещё и дуги, они поставляются парно и могут иметь разные направления. И это ещё не все. Узел может ссылаться сам на себя, делая петлю. Хорошо, мы поняли.

158: Что граф это структура данных, а наша карта, по сути, является графом. Однако все ещё непонятно, как компьютеру его воспринимать. Помните, с помощью чего мы делали таблицу умножения? Да, именно с помощью двумерного массива построим матрицу. Где значение

159: Столбцов и строк является значениями узлов. Если у нас из 1 узла можно попасть в другой, а из детского Садика домой можно, значит, мы ставим единицу. Если же связи нет, как и между детским садиком и продуктовым магазином, то мы ставим 0 детский.

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

161: Себя он попасть тоже не может. Теперь выстраиваем связи для школы из школы домой попасть нельзя. Ставим 0. Продуктовый магазин тоже нельзя. Магазин одежды никак. В ресторан можно, значит, ставим единицу из

162: Школы в школу тоже никак не попасть. А вот в детский садик уже можно. Заполняем таблицу для каждого узла, для ресторана, для магазина, одежды, для продуктового магазина и для дома. Теперь, если я захочу посмотреть, как попасть домой, то я на

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

164: Ориентируется на связях, то мы не только можем указывать на связь между узлами, но ещё у нас может быть вариант придать вес этим рёбрам. У меня ребра символизируют дороги, а значит вес. В моём случае это расстояние. И вот теперь

165: Я знаю, что от дома до продуктового магазина всего 1 километр, а до магазина одежды 2 и в школу, конечно же, самая длинная дорога продолженность в 5 километров.