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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

✅Ссылки на материал с постов да и просто важные ссылки для вашего изучения. 💻

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

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

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

https://docs-python.ru/tutorial/operatsii-chislami-python/problemy-chisel-plavajuschej-zapjatoj/#float-error - проблема чисел с плавающей точкой с курса

https://struchkov.dev/blog/ru/floating-point-math/ - Точность чисел с плавающей запятой
https://stepik.org/course/58852/syllabus — КУРС, КОТОРЫЙ МЫ ПРОХОДИМ

🔗 Python: "Поколение Python": курс для начинающих.
🔗 Python: "Поколение Python": курс для начинающих (часть 2).
⚙️ Python (Базовые знания)
🖇 Алгоритмы
🌶 Machine learning
📁 Язык C
💲 Пост с навигацией на всякий
🐍 Разбор кода на Python
🧑‍💻ЕГЭ (Информатика): Решение задач на Python

✔️ Связанные списки и массивы💲

Достаточно большая тема, снизу будет представлена навигация по спискам и массивам... Таким лазурным цветом будем обозначать подтемы, к примеру, есть блок ❗️Алгоритмы❗️а ❗️Связанные списки и массивы❗️ достаточно большая подтема.

0️⃣ Вступление

1️⃣ Массивы

2️⃣ Основная проблема массивов

3️⃣ Резервирование места в массиве и минусы

4️⃣ Недостатки массивов ❌

5️⃣ Связные списки

6️⃣ Структура связного (однонаправленного) списка

7️⃣ Структура двусвязного (двунаправленного) списка

8️⃣ Структура кольцевого (циклического) связного списка

9️⃣ Кольцевой связанный список из односвязного.

1️⃣0️⃣ Кольцевой связанный список из двусвязного.

1️⃣1️⃣ Плюсы связных списков ✅

1️⃣2️⃣ Минусы связных списков ❌

1️⃣3️⃣ Плюсы массивов ✅

1️⃣4️⃣ Время выполнения основных операций и использование памяти 🕐

1️⃣5️⃣ Что лучше использовать❓

__________________________________

🟰Н А В И Г А Ц И Я🟰

🟰 В Е Р Н У Т Ь С Я К А Л Г О Р И Т М А М🟰

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

Мы этой темы немного коснулись, ниже как обычно ссылки 🔗

0️⃣ Пояснение Big(O) и линейное время O(n)

1️⃣ Константная сложность O(1) и логарифмическое время O(log n)

2️⃣ Бинарный поиск и простой‼️

3️⃣ Снова линейное время ✔️

4️⃣ Квадратичная сложность и сортировка пузырьком✔️

5️⃣ Что такое Big(O) и зачем оно нужно? (обновленные посты)

6️⃣ Постоянное время (Константная сложность O(1))💲

7️⃣ Пример алгоритма со сложность O(1) на Python ❗️

8️⃣ Что такое Асимптотическая сложность алгоритма❓

9️⃣‼️ Что такое Логарифмическое время O(n log n), Бинарный поиск‼️

1️⃣0️⃣ Как найти средний индекс ❓

1️⃣1️⃣🌶Разбор кода бинарного поиска🌶

__________________________________

🟰Н А В И Г А Ц И Я🟰

🟰В Е Р Н У Т Ь С Я К А Л Г О Р И Т М А М🟰

Завтра, я думаю, можно посвятить еще постов этой теме, побольше расскажу про виды Big(O)

🧑‍💻Всем ку, хотел мы немного объединить темы по Big(O), чтобы у всех было понимание что это и с чем это едят. Но, в любом случае, я вам сделал пост про сложность алгоритмов и время выполнения, туда добавлю и сегодняшние посты.🖤

0️⃣🔗 Я уже говорил, что Big(O) это нотация, нужная для описания сложности алгоритмов. Она помогает нам описывать, насколько быстро работает алгоритм. Запись O(n) называется 'O - большое', ❗️n отвечает за количество операций. Такая запись отвечала бы, например, за проверку неотсортированного списка. Допустим, есть у нас список [0, 16, 22, 4, 17, 8]. Как вы видите, список не отсортирован, значит, если бы мы захотели найти какое то число в этом списке, то нам нужно пришлось бы пройтись по всем значениям этого списка.

1️⃣ Очень важный момент‼️. Запись Big(O) дает нам также представление о том, насколько наш алгоритм будет эффективен, по мере того, как будут увеличиваться входные данные. Пример все тот же: [0, 16, 22, 4, 17, 8].

🖇В нашем списке 6 элементов, а мы хотим найти, например, последний элемент - 8. Простым поиском, то есть, обычным перебором, мы это делали бы не так уж и долго, потому что элементов всего-навсего 6. А теперь представьте, что элементов в списке у нас не 6, а несколько тысяч) Навряд ли вам понравилось бы искать там какой-нибудь элемент...

🧑‍💻Начнем с постоянного времени O(1). Это константная сложность. Такая сложность возникает, когда наш алгоритм будет всегда иметь одинаковую производительность, независимо от размера вашего набора входных данных.

❓Помните наш пример списка [0, 16, 22, 4, 17, 8].?
Дак вот, мы с вами спокойно можем получить доступ к любому элементу по его индексу.

0 - 0
16 - 1
22 - 2
4 - 3
17 - 4
8 - 5

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

Йоу всем привет, ща будем разъ💀💀💀ывать биг (O)