Двусвязный циклический список

Структуры данных / Двусвязный циклический список

Каждый узел двунаправленного (двусвязного) циклического списка (ДЦС) содержит два поля указателей - на следующий и на предыдущий узлы. Указатель на предыдущий узел корня списка содержит адрес последнего узла. Указатель на следующий узел последнего узла содержит адрес корня списка.
Двусвязный циклический список
Узел ДЦС можно представить в виде структуры, аналогичной ДЛС:

struct list {
int field; // поле данных
struct list *next; // указатель на следующий элемент
struct list *prev; // указатель на предыдущий элемент
};

Основные действия, производимые над узлами ДЦС:

  • Инициализация списка
  • Добавление узла в список
  • Удаление узла из списка
  • Вывод элементов списка
  • Вывод элементов списка в обратном порядке
  • Взаимообмен двух узлов списка
Инициализация ДЦС

Инициализация списка предназначена для создания корневого узла списка, у которого поля указателей на следующий и предыдущий узлы указывают на сам создаваемый узел.
Инициализация двусвязного циклического списка

struct list * init(int a) { // а- значение первого узла
  struct list *lst;
  // выделение памяти под корень списка
  lst = (struct list*)malloc(sizeof(struct list));
  lst->field = a;
  lst->next = lst; // указатель на следующий узел
  lst->prev = lst; // указатель на предыдущий узел
  return(lst);
}
Добавление узла в ДЦС

Функция добавления узла в ДЦС аналогична функции для ДЛС и принимает два аргумента:

  • Указатель на узел, после которого происходит добавление
  • Данные для добавляемого узла.

Процедуру добавления узла можно отобразить следующей схемой:
Добавление элемента в двусвязный циклический список

Добавление узла в ДЦС включает в себя следующие этапы:

  • создание узла добавляемого элемента и заполнение его поля данных;
  • переустановка указателя "следующий" узла, предшествующего добавляемому, на добавляемый узел;
  • переустановка указателя "предыдущий" узла, следующего за добавляемым, на добавляемый узел;
  • установка указателя "следующий" добавляемого узла на следующий узел (тот, на который указывал предшествующий узел);
  • установка указателя "предыдущий" добавляемого узла на узел, предшествующий добавляемому (узел, переданный в функцию).

Для циклического списка предыдущий узел любого узла существует, поэтому нет необходимости проверки предыдущего элемента на нулевое значение.

Таким образом, функция добавления узла в ДЦС имеет вид:

struct list * addelem(list *lst, int number) {
  struct list *temp, *p;
  temp = (struct list*)malloc(sizeof(list));
  p = lst->next; // сохранение указателя на следующий узел
  lst->next = temp; // предыдущий узел указывает на создаваемый
  temp->field = number; // сохранение поля данных добавляемого узла
  temp->next = p; // созданный узел указывает на следующий узел
  temp->prev = lst; // созданный узел указывает на предыдущий узел
  p->prev = temp;
  return(temp);
}

Возвращаемым значением функции является адрес добавленного узла.

Удаление узла ДЦС

В качестве аргументов функции удаления узла ДЦС передается указатель на удаляемый узел. Поскольку узел списка имеет поле указателя на предыдущий узел, нет необходимости передавать указатель на корень списка.

Функция возвращает указатель на узел, следующий за удаляемым.

Удаление узла может быть представлено следующей схемой:
Удаление элемента двусвязного циклического списка

Удаление узла ДЦС включает в себя следующие этапы:

  • установка указателя "следующий" предыдущего узла на узел, следующий за удаляемым;
  • установка указателя "предыдущий" следующего узла на узел, предшествующий удаляемому;
  • освобождение памяти удаляемого узла.
struct list * deletelem(list *lst) {
  struct list *prev, *next;
  prev = lst->prev; // узел, предшествующий lst
  next = lst->next; // узел, следующий за lst
  prev->next = lst->next; // переставляем указатель
  next->prev = lst->prev; // переставляем указатель
  free(lst); // освобождаем память удаляемого элемента
  return(prev);
}
Вывод элементов ДЦС

Функция вывода элементов ДЦС аналогична функции для ОЦС.
В качестве аргумента в функцию вывода элементов передается указатель на корень списка.
Функция осуществляет последовательный обход всех узлов с выводом их значений.

void listprint(list *lst) {
  struct list *p;
  p = lst;
  do {
    printf("%d ",p->field); // вывод значения элемента p
    p = p->next; // переход к следующему узлу
  } while(p != lst); // условие окончания обхода
}

Для ДЦС также можно вызвать функцию вывода элементов списка в обратном порядке.

Вывод элементов ДЦС в обратном порядке

Функция вывода элементов ДЦС в обратном порядке принимает в качестве аргумента указатель на корень списка. Функция перемещает указатель на последний узел списка и осуществляет последовательный обход всех узлов с выводом их значений в обратном порядке. Однако процедура перемещения указателя на последний узел в данном случае намного проще по сравнению с ДЛС, поскольку указатель "предыдущий" корня списка как раз и содержит адрес последнего узла.

void listprintr(list *lst) {
  struct list *p;
  p = lst;
  do {
    p = p->prev;  // переход к предыдущему узлу
    printf("%d ",p->field); // вывод значения элемента p
  } while(p != lst); // условие окончания обхода
}
Взаимообмен узлов ДЦС

В качестве аргументов функция взаимообмена узлов ДЦС принимает два указателя на обмениваемые узлы, а также указатель на корень списка. Функция возвращает адрес корневого узла списка.

Взаимообмен узлов списка осуществляется путем переустановки указателей. Для этого необходимо определить предшествующий и последующий узлы для каждого заменяемого. При этом возможны две ситуации:

  • заменяемые узлы являются соседями;
  • заменяемые узлы не являются соседями, то есть между ними имеется хотя бы один узел.

При замене соседних узлов переустановка указателей выглядит следующим образом:
Замена соседних узлов двусвязного циклического списка

При замене узлов, не являющихся соседними переустановка указателей выглядит следующим образом:
Замена узлов двусвязного циклического списка

Функция взаимообмена узлов ДЦС выглядит следующим образом:

struct list * swap(struct list *lst1, struct list *lst2, struct list *head) {
// Возвращает новый корень списка
  struct list *prev1, *prev2, *next1, *next2;
  prev1 = lst1->prev; // узел предшествующий lst1
  prev2 = lst2->prev; // узел предшествующий lst2
  next1 = lst1->next; // узел следующий за lst1
  next2 = lst2->next; // узел следующий за lst2
  if(lst2 == next1) { // обмениваются соседние узлы
    lst2->next = lst1;
    lst2->prev = prev1;
    lst1->next = next2;
    lst1->prev = lst2;
    next2->prev = lst1;
    prev1->next = lst2;
  } else if(lst1 == next2) { // обмениваются соседние узлы
    lst1->next = lst2;
    lst1->prev = prev2;
    lst2->next = next1;
    lst2->prev = lst1;
    next1->prev = lst2;
    prev2->next = lst1;
  } else { // обмениваются отстоящие узлы
    prev1->next = lst2;
    lst2->next = next1;
    prev2->next = lst1;
    lst1->next = next2;
    lst2->prev = prev1;
    next2->prev = lst1;
    lst1->prev = prev2;
    next1->prev = lst2;
  }
  if(lst1 == head)
    return(lst2);
  if(lst2 == head)
    return(lst1);
  return(head);
}

Назад


Назад: Структуры данных

Комментариев к записи: 2

  • К этой статье полезно добавить следующее:

    — С некоторой версии ядра Linux (2.6, возможно не самой первой в линии 2.6) все без исключения динамические структуры kernel (списки, деревья, графы … все) были переписаны используя единственную базовую структуру — двусвязный циклический список.

    — Для этого в types.h они определили struct list_head, а в  list.h — десятка полтора макросов для работы со списком на все случаи жизни (таких как  list_entry() или list_for_each()).

    В дополнение к предыдущему комментарию:

    — Огромный профит циклического списка (двухсвязного в частности) в том, что в нём при ошибочном разыменовании ссылок никогда не получится разименовать NULL. И тем самым завалить сразу ядро операционной системы (с последующими перезагрузками, потерями данных и др.). Это неоднократно оценили и отметили в публикациях все работающие с драйверами Linux.


  • Блог программиста

    Зачем нужен двусвязный циклический список (как и все другие виды циклических списков)?

    Мне не встречалось случаев, где можно было бы их удачно применить. Профит от одной или двух лишних дуг не очевиден.

    Единственное удачное применение (и-то с натяжкой, т.к. там не чисто циклический список), которое я видел — это задача на собеседовании(т.е. число академическое применение) следующего вида:
    дан список, содержащий цикл, но не обычный, а например
    a-b-c-d-e-f-c.

    Т.е. первые элементы могут в цикл не входить. Требуется найти начало цикла (придумать оптимальный алгоритм).

    Метод «разделяй и властвуй» с циклическими списками вроде бы и работает, но затруднено, т.е. вы не можете отщепить один элемент, а остальные обработать рекурсивно. Вы должны именно «удалить элемент из списка».

    Проблемы вижу (скорее неудобство использования), а профита — нет. Асимптотическая сложность основных операций будет точно такой же как и обычного двусвязного списка.


Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *