среда, 8 декабря 2010 г.

Двусвязный список [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)

6 комментариев:

  1. Вот более элегантный способ обменять 2 элемента:

    // Приватный метод
    void List::swap(ListNode *a, ListNode *b)
    {
    ListNode* tmpNode;

    tmpNode = a->prev;
    a->prev = b->prev;
    b->prev = tmpNode;

    tmpNode = a->next;
    a->next = b->next;
    b->next = tmpNode;
    }

    void List::swapNodes(ListNode *a, ListNode *b)
    {
    if (!a || !b || a == b) return;

    if (a == _pBegin) _pBegin = b;
    else if (b == _pBegin) _pBegin = a;

    if (a == _pEnd) _pEnd = b;
    else if (b == _pEnd) _pEnd = a;

    ListNode* prevA = a->prev;
    ListNode* nextA = a->next;

    ListNode* prevB = b->prev;
    ListNode* nextB = b->next;


    if (a == prevB)
    {
    // смежные элементы, a -> b
    b->prev = a->prev;
    a->next = b->next;

    a->prev = b;
    b->next = a;
    }
    else if (b == prevA)
    {
    // смежные элементы, b -> a
    a->prev = b->prev;
    b->next = a->next;

    b->prev = a;
    a->next = b;
    }
    else
    {
    // несмежные элементы
    swap(a, b);

    if (prevA) prevA->next = b;

    if (nextA) nextA->prev = b;

    if (prevB) prevB->next = a;

    if (nextB) nextB->prev = a;
    }
    }

    ОтветитьУдалить
  2. Зачем использовать два класса там, где хватает одной структуры? Не понимаю.

    ОтветитьУдалить
    Ответы
    1. класс и структура в принципе одно и тоже(особенно для компилятора), а второй это двигатель списка, зачем повторять код функции 1000 раз!!!!!!! это ведь память и время процессора

      Удалить
  3. А вы можете реализовать само меню с вызовом этих функций?
    К примеру:
    1. Добавить вначало
    2. Добавить в конец
    3. Просмотр
    Не получается у меня это сделать...

    ОтветитьУдалить
    Ответы
    1. О вызове функций советую прочитать здесь http://ru.wikibooks.org/wiki/C++ в разделе Инкапсуляция.
      Меню мы реализовать можем, но в этом нет необходимости.

      Удалить
  4. > Самая замудренная операция оказалась void Swap(ListNode* a, ListNode* b). Если Вы можете предложить более изящную
    > реализацию этой операции – будет крайне интересно с ней ознакомиться.
    В моем блоге есть изящное решение. Приглашаю обсудить: http://y-engine.blogspot.com/

    ОтветитьУдалить