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

Итак, в массиве все задачи хранятся в памяти непрерывно, то есть, у нас есть структура данных (Массив), состоящая из фиксированного числа элементов, а расположены элементы в смежных ячейках (Идут друг за другом), периодически буду приводить примеры из книги. Также стоит сказать, что элементы массива имеют индекс, по которому к ним можно быстро получить доступ, об этом еще поговорим. #Память #Связанные_списки #Массивы

Дак вот, возвращаемся к списку дел. У нас есть пока что три темки, чем мы можем заняться, для них компьютер уже выделил память (как раз три ячейки), но вдруг у нас появляется четвертая задача, а следующая ячейка памяти уже занята! Что нам теперь делать??? В таком случае, нам придется запросить новый блок памяти, где будет сразу 4 свободных ячейки памяти, которые идут друг за другом, а затем переместить наши 4 задачи туда. Но как вы уже поняли, это достаточно медленно, типо прикиньте у нас всегда будет появляться новая задача, а места под нее хватать не будет, и нам придется всегда искать в компьютере другой блок памяти. ⚙️ #Память #Связанные_списки #Массивы

✅Простейшим решением будет бронирование (резервирование) места в массиве.
Вместо того, чтобы выделять память ровно под необходимое количество элементов, выделяется больше памяти, чем нужно в данный момент. Это позволяет добавлять новые элементы в массив, не перевыделяя память каждый раз. То есть, если у нас пока что 4 задачи, но мы не уверены что это конечное число, просто резервируем сразу 7-8 мест и не паримся. Конечно же, есть недостатки.

⁉️Первое, забронировав 8 мест, не факт, что все они будут использоваться, следовательно память будет расходоваться неэффективно. И мы ее не используем и никто другой.

‼️Второе, если количество задач выйдет за 8, то перемещать все ровно придется. Теперь разберем связанные списки... #Память #Связанные_списки #Массивы

А, хотя подождите, сначала про недостатки массивов, а затем сразу к связанным спискам!

❌1. Это конечно же проблема с выделением памяти. Когда мы сохраняем задачи в массиве, нам нужен фиксированный и непрерывный участок памяти, это где элементы идут друг за другом. Если у нас всего три свободных ячейки памяти и вдруг понадобилась четвертая, но она занята, нам придется запросить новый блок памяти. Есть конечно резервирование ячеек, но про их минусы я также написал. 💻

❌2. Трудности с вставкой и удалением элементов (об этом еще поговорим позже). Вставка или удаление элемента в середине массива требует сдвига всех последующих элементов, что занимает линейное время O(n), если вы не шарите в этой теме, я об этом писал, можете смотреть в навигации. Это если че достаточно медленный алгоритм.

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

❌4. Наверное. это все-таки минус - однородность элементов в массиве. То есть, мы можем хранить только элементы одного типа

Вот если че, почитете

Ииитак, о преимуществах массивов говорить нам нельзя пока что, мы еще связанные списки не рассмотрели.

‼️ Первое, что вы сразу могли заметить, наши задачи размещаются где угодно в памяти, в каждом элементе хранится адрес следующего элемента списка. А вот набор произвольных адресов памяти объединяется в цепочку. Я немного об этом подробнее почитал, вот вам рассказываю. Каждая такая 'задача' это узел.

Связаный список содержит элемент ссылки, называемой first (первой).

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

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

Последняя ссылка содержит ссылку со значением null, обозначающую конец списка.

Так, продолжим немного позже гайс, впитывайте пока что

Воссап всем, ща буду рассказывать дальше про связанные списки.. Итак, связанный список это структура данных, которая состоит из элементов, называемых узлами.
Эти самые узлы хранят в себе данные и ссылки на следующий элемент в списке (это характерно для односвязного списка). Двухсвязный список имеет ссылки с переходом по элементам вперед и назад.

В прикрепленном сообщении все хорошо описано.

Вот вам пару ссылок, если хотите ознакомиться сами, я попробую это скомпоновать по-своему
https://medium.com/nuances-of-programming/структуры-данных-и-алгоритмы-связный-список-6ae2625be22b - связаный список

https://medium.com/nuances-of-programming/структуры-данных-кольцевой-циклический-замкнутый-связный-список-93afae65157e - кольцевой связанный список

https://nuancesprog.ru/p/15493/ - двусвязный (двунаправленный) список

✅ Вот так выглядит связанный (однонаправленный) список с переходом элементов только вперед. Про это мы уже немного сказали.

🖇А вот так выглядит двусвязный (двунаправленный) список, он содержит элемент ссылок first (для первой) и last (для последней). Также, явное отличие от односвязного списка - это переход по элементам не только вперед, но и назад. То есть, каждая ссылка связана со следующей посредством своей ссылки next, с предыдущей посредством своей ссылки prev. Последняя ссылка содержит ссылку со значением null, обозначающую конец списка.

⚙️ Теперь, третий вид связанного списка - кольцевой (циклический, замкнутый) связный список. Главная суть (сейчас вы увидите по фоткам), последний элемент не содержит null или None в указателе на следующий узел, как в обычных связных списках. Вместо этого последний узел ссылается на первый узел списка, а последний — на первый. Кольцевой связанный список можно сделать как из односвязного (однонаправленного), так и двусвязного (двунаправленного) списка. Сейчас поговорим отдельно о каждом

✅ Кольцевой связанный список из односвязного. Как вы уже заметили, конца списка со значением null нет, вместо этого указатель next последнего узла указывает на первый узел.

✅ Кольцевой связаный список из двусвязного. Указатель next последнего также указывает на первый узел, а указатель prev первого узла - указывает на последний, то есть. получается кольцевой связный список в обоих направлениях.

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

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

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

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

✅2. Отсюда вытекает следующий плюс со вставкой, или удалением элементов. Вставка или удаление элементы из середины занимает время O(1) (Очень эффективный алгоритм). Напоминаю, что O(1) - это постоянная сложность алгоритма, то есть размер входных данных нам не важен, сообщение я вам прикрепил, если забыли).

Теперь минусы:

❌1. Я вам уже сказал что в каждом элементе связанного списка хранится ссылка на следующий, следовательно, адрес нужного элемента мы получить не так уж и быстро. Проблема заключается в медленном доступе к индексу. Если в массиве мы изначально знаем адрес каждого элемента, то в связанном списке нам придется проходить от одного узла к другому, что занимает время O(n). Я уже говорил, что это постоянное время, проще говоря, нам придется пройтись по каждому элементу, чтобы найти нужный адрес элемента.

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