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

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

Теперь мы вполне можем выявить плюсы массивов и сравнить со списками.

1.✅ Конечно же это доступ к индексу. Мы изначально знаем адрес каждого элемента и легко можем обратиться к элементам по их индексу за время O(1). Это возможно благодаря тому, что элементы массива хранятся последовательно в памяти.

2.✅ Если со связанными списками есть проблема с использованием памяти, то у массивов затраты куда меньше, поскольку хранятся они последовательно в непрерывном блоке памяти.

Время выполнения основных операций и использование памяти.
‼️Могу пояснить, динамическая память на указатели в связанных списках - это значит, что на каждый указатель компьютер также выделяет память (у двусвязного списка будет два узла, на которые также будет выделена память), поэтому память динамически развивается.

Мы обязательно вернемся еще к этой теме, потому что это используется программистами повсеместно, как минимум)). Но я бы хотел еще поговорить об этом в практическом плане, показать примеры, но данная теория будет важна, как для меня, так и для вас.🧑‍💻

‼️Давайте подведем итоги‼️

Что лучше использовать? Связанные списки или Массивы? Массивы очень популярны, так как используют произвольный доступ (Это когда мы можем обратиться к нужному элементу по индексу. Например, будет у нас 5 элементов - можем обратиться к любому из них). Связанные списки поддерживают только последовательный доступ (Это когда мы можем читать элементы последовательно, начиная с первого. Пример тот же, есть 5 элементов, но, чтобы дойти до 5, нам нужно прочитать все перед ним и перейти по ссылкам к последнему пятому элементу). ⁉️

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

🧑‍💻Если же у нас случай, который требует постоянной вставки или удаления элементов в середине списка, динамическое изменение размера (размер структуры данных может изменяться в процессе работы программы), то смело используйте связанные списки!