|
Двусвязный список (list) в STL на С++Курс по структурам данных: https://stepik.org/a/134212 На этом занятии мы рассмотрим уже готовую реализацию двусвязного списка из стандартной библиотеки шаблонов (STL). Чтобы воспользоваться этой коллекцией данных, вначале нужно подключить модуль list: #include <list>А, затем, в функции main() определить объект класса list, например, так: int main() { using namespace std; list<int> lst; return 0; } Все, у нас в программе имеется объект lst, который представляет собой двусвязный список. Обратите внимание, в угловых скобках прописан тип int – тот тип данных, который предполагается хранить в элементах двусвязного списка. Вместо типа int можно прописать любой другой, включая собственные определения классов и структур. То есть, мы здесь имеем универсальную реализацию списка, который может работать с любыми типами данных. Но для простоты пусть будет тип int. Далее, если прописать lst и поставить точку, то интегрированная среда покажет набор методов, поддерживаемых данным классом. На этом занятии мы рассмотрим наиболее значимые из них. Начнем со способа инициализации списка. При создании двусвязного списка командой: list<int> lst; создается пустой список (без элементов). Мы в этом можем легко убедиться, если вызовем метод size(), который возвращает общее число элементов: cout << lst.size() << endl; Если же нам нужно прописать в список некоторый набор начальных значений, то это можно сделать так: list<int> lst = {1, 5, 3, 2}; или так (без разницы): list<int> lst {1, 5, 3, 2}; В обоих случаях мы получим список из четырех элементов со значениями 1, 5, 3, 2. Давайте выведем их в консоль: for (auto it = lst.cbegin(); it != lst.cend(); it++) cout << *it << " "; cout << endl; Смотрите, чтобы перебрать элементы связного списка используется механизм итераторов, который в С++ нужно прописывать явно. Вначале с помощь метода cbegin() получаем константный итератор, установленный в самое начало списка. Затем, делаем цикл до тех пор, пока адрес итератора не равен конечному адресу. А оператор it++ позволяет сместить итератор на следующий элемент списка. В самом цикле с помощью операции разыменования указателя *it получаем значение текущего элемента списка и выводим его в консоль. Фактически, с помощью итератора мы последовательно переходим от одного элемента к другому, используя ссылки next и prev, которые есть у каждого объекта двусвязного списка. Обратите внимание, у двусвязного списка list имеются методы:
Отличие между этими методами заключается в том, что через константный итератор нельзя менять значения списка (только читать), а через обычный – можно. Во всем остальном они работают одинаково. Далее, если нам нужно просто получить значения первого или последнего элементов, то для этого существуют методы front() и back(): cout << lst.front() << endl; cout << lst.back() << endl; Видим значения 1 и 2. Эти методы бывают весьма полезны, например, при реализации очередей, о которых мы будем говорить на следующем занятии. Следующий часто используемый метод empty(), который возвращает булево значение true – если список пуст, и false в противном случае. Например, методы front() и back() будут приводить к ошибке, если их вызвать для пустого списка. Поэтому правильнее было бы обращаться к ним с проверкой: if (!lst.empty()) { cout << lst.front() << endl; cout << lst.back() << endl; } Добавление элементов в списокСледующий набор методов, используемый для добавления элементов в двусвязный список. Методы push_back() и push_front() используются для добавления элементов в конец и начало списка. Например: list<int> lst; lst.push_back(1); lst.push_front(4); lst.push_front(-4); lst.push_back(-1); Увидим значения: -4, 4, 1, -1. Если нам требуется вставить какое-либо значение в произвольную позицию, то для этого используется метод insert(). Этот метод использует итератор для указания позиции вставки. Например, если определить итератор с помощью команды: auto pos_it = lst.cbegin(); то получим указатель на первую позицию, куда и будет вставлен элемент: lst.insert(pos_it, 100); Если нужно вставить во вторую позицию, то это можно сделать так: auto pos_it = lst.cbegin(); pos_it++; lst.insert(pos_it, 100); или в более краткой записи: auto pos_it = lst.cbegin(); lst.insert(++pos_it, 100); Обратите внимание, что оператор ++ должен быть записан перед итератором pos_it. Если его прописать после, то сначала будет выполнен метод insert() и только потом изменится итератор на единицу. Если нужно вставить элемент в произвольную k-ю позицию, то сначала итератор устанавливается в эту позицию, например, с помощью цикла: auto pos_it = lst.cbegin(); int n = 3; for (int k = 0; k < n; ++pos_it, ++k) ; lst.insert(pos_it, 100); а, затем, выполняется команда insert(). Поэтому операция вставки, в общем случае, имеет сложность O(n), где n – общее число элементов в списке. Также с помощью insert() можно относительно просто вставить сразу несколько одинаковых значений, например, так: lst.insert(pos_it, 5, 3); Выполняется вставка пяти троек, начиная с позиции pos_it. Удаление элементов из спискаПоследняя группа методов связана с удалением элементов из списка. Если нам нужно очистить список (удалить все элементы), то это делается с помощью метода clear(): lst.clear(); Для удаления первого или последнего элемента – методы pop_front() и pop_back(): lst.pop_front(); lst.pop_back(); Наконец, удаление произвольного элемента выполняется методом erase(). Здесь также, как и в методе insert(), необходимо определить итератор на удаляемый элемент, например, так: auto pos_it = lst.cbegin(); lst.erase(++pos_it); В результате будет удален второй элемент. Либо можно задать границы удаляемых элементов через итераторы: auto start_it = lst.cbegin(); auto end_it = lst.cend(); lst.erase(++start_it, --end_it); ЗаключениеВот основные операции при работе с двусвязными списками объекта list языка С++. Конечно, мы рассмотрели не все доступные операции, но с ними можно подробно ознакомиться, например, на ресурсе: https://en.cppreference.com/w/cpp/container/list А на данный момент вы должны себе представлять, как работают следующие методы двухсвязного списка класса list:
Курс по структурам данных: https://stepik.org/a/134212 Видео по теме |
