Двусвязный список [List]

[Все типы данных]

Рассматриваемые темы:
1. Что такое двусвязный список
2. Как хранится двусвязный список в памяти компьютера?
3. Реализация базовых операций
4. Оценка сложности базовых операций

Первые два пункта очень подробно освещены в литературе:
1) Для общего представления читаем Википедию.
2) Для более детального и наглядного изучения Окулов. Абстрактные типы данных
3) Очень хорошее описания языка С++ и динамических структур данных можно найти в книге Павловской

Договоримся, что в дальнейшем речь будет идти о двусвязном списке, в котором каждый узел будет хранить 4 байтное целочисленное значение.

На третьем пункте остановимся по поподробней.
Для начала рассмотрим класс, описывающий элемент списка:

1. class ListNode
2. {
3. public:
4.   int value;
5.   ListNode *next;
6.   ListNode *prev;
7. };

* This source code was highlighted with Source Code Highlighter.

Надеюсь комментарии излишни. Но если остались вопросы, возвращаемся к первым двум пунктам и еще раз внимательно читаем теорию.
Теперь рассмотрим класс, описывающий сам двусвязный список:

1. class List
2. {
3. private:
4.   ListNode* _pBegin;
5.   ListNode* _pEnd;
6.   unsigned int _size;
7. };

* This source code was highlighted with Source Code Highlighter.

Интуитивно можно догадаться о смысле каждого из полей. Двигаемся дальше. Составим список функций, которые мы хотим реализовать для двусвязного списка, которые будут являться методами класса List:

1. List();
2. List(int size);
3. List(int size, int data);
4. void assign(int data); // инициализация всего списка значением data
5. ListNode* back(); //указатель на конец
6. ListNode* begin(); // указатель на начало
7. bool empty(); // проверка на пустоту
8. ListNode* erase(ListNode* pWhere); // удалить узел
9. ListNode* find(int data); // найти первый узел, содержащий data
10. ListNode* insertBefore(ListNode* Where, int data); // вставка до
11. ListNode* insertАfter(ListNode* Where, int data); // вставка после
12. void output(); // вывод
13. bool pop_back(); // удаление с конца
14. bool pop_front(); // удаление с начала
15. void push_back(int data); // добавление в конец
16. void push_front(int data); // добавление в начало
17. bool remove(int data); // удалить все узлы, содержащие такую data
18. void resize(unsigned int newLen); // изменить размер
19. void reverse(); // реверснуть список
20. unsigned int size(); // размер списка
21. void Swap(ListNode* a, ListNode* b); // обмен двух элементов местами

* This source code was highlighted with Source Code Highlighter.

Список функций был разработан согласно набору функций класса list из STL, который является аналогом нашего разрабатываемого класса. Вместо итераторов мы будет использовать указатели на узлы списка. Разрабатываемый класс List в первую очередь должен дать ответы на вопросы – как устроены базовые операции и как эффективно их можно реализовать самостоятельно. В реальных боевых условиях рекомендуется использовать std::list<T>, хотя могут быть случаи, когда использование нашего класса List может привести к ускорению работы программы.

Предлагаю ознакомится с полной реализацией двусвязного списка на примере класса List:
ListNode.h
List.h
List.cpp

Самая замудренная операция оказалась void Swap(ListNode* a, ListNode* b). Если Вы можете предложить более изящную реализацию этой операции – будет крайне интересно с ней ознакомиться.

Алгоритмические сложности базовых операций:

1) Получение элемента по индексу	O(N)
2) Добавление элемента в конец	O(1)
3) Добавление элемента в начало	O(1)
4) Добавление элемента в “середину”	O(1), если известно место, иначе O(N)
5) Удаление элемента с конца	O(1)
6) Удаление элемента с начала	O(1)
7) Удаление элемента с “середины”	O(1), если известно место, иначе O(N)