Двусвязные списки в C++

По своей структуре списки сильно отличаются от векторов и деков, хотя они поддерживают почти весь набор операций характерных для деков и векторов, кроме того в списках есть набор специфических функций, каких именно, рассмотрим далее. Чтобы воспользоваться контейнером списков в С++, вам необходимо подключить следующий заголовочный файл:

#include <list>

Давайте рассмотрим пример программы с использованием списка:

#include <iostream>
#include <list>     // подключаем заголовок списка
#include <iterator> // заголовок итераторов
using namespace std;

int main()
{
   list<int> myList; // объявляем пустой список
   for(int i = 0; i < 11; i++) {
       myList.push_back(i); // добавляем в список новые элементы
   }

   cout << "Список: ";
   copy(myList.begin(), myList.end(), ostream_iterator<int>(cout," ")); // вывод на экран элементов списка
   cout << "\nПервый элемент списка: " << myList.front();
   cout << "\nПоследний элемент списка: " << myList.back();
   return 0;
}

Результат работы программы:

Список: 0 1 2 3 4 5 6 7 8 9 10 
Первый элемент списка: 0 
Последний элемент списка: 10

Во второй строке мы подключили заголовок для использования контейнера списков. В строке 8 объявлен пустой список, то есть он не содержал никаких элементов. Дальше, в цикле for, в строках 9-11 мы заполняем стек новыми элементами. Добавить элементы в стек можно с помощью метода push_back(). В строке 14 выполняется вывод элементов списка на экран, с помощью функции copy(). Вывести элементы списка через цикл с использованием операции индексирования не получится, так как списки не поддерживают эту операцию:

myList[i]; // приведет к ошибке

Нельзя получить произвольный доступ к элементам списка. Для прямого обращения к элементам списка предусмотрены два метода: front() и back(), как показано в строках 15-16.  Давайте рассмотрим еще один пример программы, где показаны еще несколько замечательных функций списков:

#include <iostream>
#include <list>     // подключаем заголовок списка
#include <iterator> // заголовок итераторов
#include <ctime>
#include <cstdlib>
using namespace std;

int main()
{
   list<int> myList; // объявляем пустой список
   srand(time(NULL));

   for(int i = 0; i < 15; i++) {
       myList.push_back(rand()%20); // добавляем в список новые элементы
   }

   cout << "Список: ";
   copy(myList.begin(), myList.end(), ostream_iterator<int>(cout," "));

   myList.sort();   // отсортировали список по возрастанию
   cout << "\nОтсортированный список: ";
   copy(myList.begin(), myList.end(), ostream_iterator<int>(cout," "));

   myList.unique();   // удалили дубликаты элементов списка
   cout << "\nСписок с уникальными элементами: ";
   copy(myList.begin(), myList.end(), ostream_iterator<int>(cout," "));

   list<int> myList2; // объявляем еще один пустой список
   for(int i = 0; i < 15; i++) {
       myList2.push_back(rand()%20); // добавляем в список новые элементы
   }

   cout << "\nСписок2: ";
   copy(myList2.begin(), myList2.end(), ostream_iterator<int>(cout," "));

   myList2.merge(myList);
   cout << "\nОбъединили списки: ";
   copy(myList2.begin(), myList2.end(), ostream_iterator<int>(cout," "));
   return 0;
}

В строке 14 мы заполняем список случайными элементами, как всегда для заполнения списка используется метод push_back(), каждый новый элемент всегда добавляется в конец списка. Если вы хотите добавлять каждый новый элемент в начало списка, то используйте метод push_front(). В строке 20, мы воспользовались функцией сортировки списков — sort(), результат отсортированного списка выводится в строке 22. В строке 24, с помощью функции unique() в списке myList были удалены дубликаты элементов списка, это видно в результате работы программы. В строках 28 — 31 мы создали еще один список и заполнили его другими случайными элементами. И теперь, в строке 36, мы вызвали метод merge(), который объединил два списка. Результат программы можно посмотреть ниже:

Список: 6 15 6 10 6 15 18 17 15 18 18 11 12 17 17 
Отсортированный список: 6 6 6 10 11 12 15 15 15 17 17 17 18 18 18 
Список с уникальными элементами: 6 10 11 12 15 17 18 
Список2: 1 6 14 18 5 3 0 13 3 6 8 1 15 13 19 
Объединили списки: 1 6 6 10 11 12 14 15 17 18 5 3 0 13 3 6 8 1 15 13 18 19