Изучение структур данных
Что такое связанный список?
Связный список — это динамическая структура данных. Есть три основных понятия, которые определяют связанный список.
1. Он имеет последовательность узлов. Каждый из которых содержит некоторые важные данные и указатель, назначенный следующему узлу. Представьте себе «линию конга», когда каждый человек протягивает руки к следующему человеку в очереди.
2. Указатель головы назначается первому элементу в списке.
3. Последний узел имеет указатель, которому присвоено значение NULL. Это шаблон, называемый «нулевое завершение».
С помощью этих трех правил вы можете создавать свои собственные связанные списки! Взгляните на это:
Зачем использовать связанный список?
Почему бы просто не использовать массив? Вот некоторые ситуации, когда связанный список будет работать лучше, чем массив:
1. Если вы не знаете длину данных или она будет меняться со временем
Вы можете подумать: «Я просто сделаю свой массив СУПЕР большим, чтобы избежать всей этой чепухи со связанными списками». Проблема с этим подходом заключается в том, что он тратит память впустую, и предел может быть *потенциально* достигнут.
2. Если вам нужно вставить элементы между другими элементами
Перемещение элементов в массиве обременительно и требует больших вычислительных ресурсов. Например:
3. Если вам нужно реализовать упорядочивание динамических данных
Подумайте о программе, в которой пользователь просматривает инвентарь в своем магазине. Они сканируют каждый предмет, а программа динамически подсчитывает и сохраняет элементы инвентаря. Когда вы читаете данные, не предпочли бы вы их в каком-то порядке (по производителю, номеру товара, названию и т. д.)?
4. Если вы вообще работаете с элементами по порядку (не хаотично)
С массивами вы можете сразу получить доступ к элементам по их индексу.
Со связанными списками вам нужно перебирать все элементы, пока не достигнете нужного элемента.
Как сделать связанный список?
Давайте реализуем наш собственный класс связанного списка. Мы можем составить неупорядоченный список строк. Нам потребуется…
1. Добавить строки
2. Удалить строки
3. Очистить список
4. Вывести строки на экран
5. Найдите общее количество строк в списке
Во-первых, давайте создадим узлы для связанного списка. Мы будем использовать структуру.
Давайте используем структуру Node в нашем классе UnorderedList. Сначала давайте спланируем наш класс, написав заголовок.
Далее мы можем начать нашу реализацию. Поскольку мы знаем 3 части связанного списка, давайте начнем с указателя на голову. Взгляните на диаграмму выше, если вам нужна визуализация. Мы назначим указатель на головку в очень простом конструкторе вот так.
Предварительно
Следующая логичная вещь после создания списка — добавление в него данных! Давайте рассмотрим метод prepend (потому что он самый простой). Нам придется немного поманипулировать указателями, чтобы убедиться, что мы избегаем утечек памяти и не теряем след выделенных данных. Вот диаграмма, которая поможет визуализировать алгоритм:
Обход/печать/счет/поиск
Давайте обсудим, как пройтись по списку. Общий шаблон заключается в создании временного указателя узла (обычно его называют текущим). Вы начинаете с того, что указываете на то, на что направлен указатель головы. Вы можете использовать указатель next узла для навигации по списку до тех пор, пока «next» не станет NULL, что означает, что вы достигли конца списка. Вот метод печати для более глубокого изучения списка:
Методы count и find следуют очень похожему шаблону. Вот они:
Добавить
Это относится к методу печати, но что, если вы хотите добавить узлы в конец списка? Это немного сложнее. Вот диаграмма для визуализации алгоритма добавления.
Удалять
Метод удаления использует шаблон обхода, но при этом сохраняет указатель в конце. Стратегия состоит в том, чтобы удалить данные, не теряя ни одного узла. Вот схема для визуализации алгоритма удаления:
Убрать все
Метод удаления всех обходит список и удаляет все узлы по пути. Деструктор просто вызывает этот метод. Вот код:
На этом мы завершаем введение в связанные списки. Если вас интересуют упорядоченные связанные списки, просто настройте алгоритм вставки, чтобы сравнивать каждый элемент по мере перемещения по списку. Следите за предыдущим узлом, чтобы всегда можно было вставить его в нужное место. Далее я займусь еще некоторыми структурами данных, такими как двусвязные списки или бинарные деревья поиска!
