0: Что ж, продолжаем. И теперь давайте зададимся таким вопросом. Вот хорошо. Листы массивы, они работают, собственно, как мы рассмотрели. А что если я хочу вставить в лист какое-то значение? То есть, если

1: Я хочу вставить в лист, например, insert, в самое начало, там какую-нибудь пятёрку, да, что мне для этого нужно сделать? Ну,

2: Идеи, да, мне надо, естественно, создать эту пятёрку где-то в куче. Хорошо, давайте её создадим красным цветом, собственно, значение помечу. Ну и у нас

3: Получается пятёрка, да? 0, 0, 0, 0, 1 0.

4: 1 0.

5: Хорошо, только единственное, она, конечно, по адресу не 160, а тут уже очередная ячейка 168. Пусть будет хорошо, но куда нам надо запихнуть ссылку то на неё в лист, если мы хотим вставить в начало листа.

6: То есть вот сюда, типа, что мы должны сделать? По идее, все остальные элементы сдвигаются вправо. То есть наш нолик, который стоял на нулевом индексе, та встанет на 1 индекс нолик с 1 индекса на 2 нолик с 3 индекса.

7: 4, да, восьмёрка с 4 индекса, с 4 позиции, с 3 индекса, да, на 4 индекс с 4 индекса на 5 индекс. То есть они все сдвинутся вправо. И, по идее, то, что я хочу видеть здесь, это

8: Какой-то такой вот результат. 5:00. Че у меня там 3 нолика, да, 8, 10. И в общем то ставка, она примерно так и работает. То есть у нас все элементы будут сдвинуты.

9: Вправо. И после этого мы уже сможем в освободившееся место, соответственно, что-то вставить. Но как мы сдвигаем, подчеркну ещё раз, мы буквально копируем все наши значения. То есть мы должны взять вот это значение, да

10: Скопировать его в новое место. Вот как-то так, да, потом на его место старое мы должны скопировать предыдущее значение 0 0 1 1 00:00 и так далее сделать со всеми нашими значениями

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

12: Ну, многовато действий. Это как раз-таки проблема листа. Что нам с ней делать? Ну, на самом деле, в этом нам помогут какие-нибудь структуры данных. То есть мы понимаем, что в целом

13: Идея листа заключается в том, что это последовательно выделенная область памяти. А что если мы по другому как-нибудь организуем наше расположение данных, то есть структура памяти как раз-таки задаёт что-то как данные располага.

14: В оперативной памяти. И если лист в с точки зрения кучи, да, мы можем представить вот так вот, то есть какой-то набор последовательно расположенных объектов, понятное дело, что вставлять сюда не очень удобно. То есть, допустим, мы имеем 0, 0, 0, да, нам

15: Надо сдвинуть все нолики вправо и сюда, вставить единичку. А что, если мы как бы оставим промежутки, да? Ну, это, наверное, 1 из возможных решений проблем, да, то есть, если мы возьмём наш обычный лист,

16: Сделаем какие-то специальные промежутки через 1 элемент. Вот как-то так, да, тогда мы можем сказать, слушайте, вот нашли состоящий из 3 элементов, да, 4, ладно, элементов. И мы хотим вставить после единички пятёрку оо,

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

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

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

20: Указывать, где следующий за ним элемент в памяти.

21: Например, вот так вот, да. А что значит указывать? Ну, вы уже знаете, указать, сослаться, то есть определить адрес объекта мы вполне себе можем, и это будет выглядеть таким вот образом, да, то есть

22: Мы указываем буквально, где в памяти находится следующий элемент. Здесь после пятёрки идёт тройка, она находится по какому-то адресу. После тройки идёт семёрка, она находится по какому-то адресу и так далее. И в таком случае элементы могут находиться в каком угодно.

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

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

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

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

27: А, хорошо, графы, мы не знаем, что это такое, но графы на самом деле могут быть использованы где угодно. То есть, например, навигация, навигация в вашем навигаторе, в телефоне, когда вы хотите из точки а

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

29: Так, да, потом так, потом так, вы можете пойти так, так, вы можете пойти вот так вот так вот вы можете пойти вот так вот и вот так вот, но при этом какие-то из вот этих вот дорожек, да, они могут быть более заполнены менее

30: Не заполнены, да, например, здесь у вас вообще может быть дорога временно, как бы не работающая. Так вот, подобные вещи можно хорошо представлять в виде Графов. Мы с вами о них во 2 семестре будем говорить и как

31: Как раз-таки графы, 1 из вариантов их реализации, это через линкит листы. Более того, да, где ещё графы используются? Графы используются, когда преобразуется ваш код на этапе компиляции в байт код, в питоне в каких-то

32: Других языках программирования, да? А где именно? Ну, это, например, так называемое аст дерево, там разные есть подходы, но 1 из вариантов аст, дерево, абстракт, синтакс, 3. Абстрактное синтаксическое дерево, которое представляет ваш

33: Код в виде какого-то дерева в виде какого-то такого вот дерева.

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

35: В качестве Крайних вершин, из которых никакие вот такие чёрточки не идут, у нас расположены операнды. То есть то, с чем мы работаем. То есть вот в таком варианте мы могли бы представить в наше выражение 2, там -3 + 5. Вот, ну, со временем

36: Мы об этом поговорим, но графы у нас используются в компиляции. Для чего? Почему мы хотим так представлять код? Потому что нам это позволяет оптимизировать его. Нам позволяет это проверить его корректность и многие, многие другие вещи сделать. Более того,

37: Где ещё у нас применяются графы, графы применяются у нас в базах данных б д базы данных, то есть всевозможные там

38: Или или какие-то подобные да, варианты хранения и эффективного получения собственно данных откуда-то ну, например, red black tree да, какие-нибудь бинарные деревья поиска бина.

39: Кучи и многое, многое, многое другое.

40: Вот. Ну, это такие, знаете, довольно наглядные, наверное, простые варианты использования линкит листа в виде Графов. Естественно, гораздо больше можно придумать примеров, но это так.

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

42: Хорошо, мы не будем последовательно элементы хранить. Мы скажем, каждый элемент должен ссылаться на следующий. Окей, как нам это сделать? Ну, понятное дело, чтобы сослаться на какой-то другой объект в питоне. Мы, ну или не только.

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

44: Пятёрка наша информация, а следующий элемент хранится по адресу 0 x 2 соответственно 0 x 2. Здесь мы пишем следующий элемент за тройкой хранится по адресу 0 x 3 да, это 0 x 3 следующий элемент за.

45: Семёрка хранится по адресу 0 x. Допустим 20 да, не обязательно, что они будут идти по порядку все хорошо, 0 x 20. И здесь будет, допустим, 0 x 11 да ну, если мы добавим новый элемент на данный момент у нас

46: Конечно, следующего элемента за восьмёркой нет, поэтому там можно указать нан 0 x че у меня там было 20 все, то есть теперь у нас нет требования последовательного выделения памяти и вставлять элементы становится очен.

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

48: Создаём новую ноду в неё добавляем наше число там, не знаю, 10, например, которое мы, которое мы хотим сохранить 10. Да, предположим, что это значение хранится по адресу 0 x 9 у нас 0 x 9, неисполь.

49: И мы хотим вставить между пятёркой и тройкой. То есть на данный момент наш линкед лист выглядит следующим образом. 5, 3, 7, 8. Да, мы можем его изобразить в каком-то варианте, похожем на лист 5, 3, 7, 8.

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

51: Для нас детали какого-то объекта процесса или явления. В данный момент мы понимаем, что все это хранится в компьютере, поэтому где-то там будут ячейки памяти, где-то будут адреса, где-то будет куча и тд. И тп. Но когда мы работаем с какими-то

52: Реальными данными, нам не сильно это важно. Нам важно то, насколько эффективно мы с ними можем работать. И то, например, в каком порядке они друг с другом расположены. Ну, собственно, что здесь у нас справа на экране и отображается, возвращаясь к процессу добавления. Хорошо, мы создаём

53: Новую ноду. Мы сохраняем туда данные, которые хотим хранить в ней, да, и что делаем? Хотим запихнуть её между пятёркой и тройкой. Для этого нам нужно сделать буквально простое действие. Ну, несколько действий мы

54: Меняем значение в пятёрке 0 x, допустим, 9, да, то есть пятёрка как бы уже начинает говорить следующий за мной элемент хранится по адресу 0, x, 9 и в.

55: Новый наш элемент мы сохраняем сюда 0 x, 3 0 x 3. Все легко и просто мы добавили элемент новый, и точно также у нас будет происходить добавление и в начало, и

56: В конец и в середину, и после 1 элемента. То есть обратите внимание, мне не пришлось сдвигать все абсолютно элементы куда-то там мне не пришлось пересоздавать все элементы. Я изменил буквально адрес следующего элемента.

57: У ноды, после которой я хочу вставить новую ноду, ну и новые свои данные, ну и указал.

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