Двусвязный список
Двусвязный список
Мы рассмотрели односвязный список и пришли к неутешительным выводам - список разумно использовать в качестве стека, потому что операции вставки в начало списка и удаления из начала списка имеют сложность порядка 1, с дополнительными манёврами можно добиться сложности вставки в конец порядка 1 и определения длины за O(1), но удаление с конца, вставка и поиск элемента остаются O(n).
Каким образом можно упростить удаление последнего элемента? Очевидно, что если бы мы хранили указатель на предыдущий элемент, то было бы возможно удалять последний.
Двусвязный список - это структура данных, которая состоит из узлов, которые хранят полезные данные, указатели на предыдущий узел и следующий узел.
Для реализации списка нам понадобится структура узел
typedef struct _Node { void *value; struct _Node *next; struct _Node *prev; } Node;
Указатель prev хранит адрес предыдущего узла, если его нет (значит, это первый узел) то переменная равна NULL. Аналогично, указатель next хранит адрес следующего узла. Структура "Двусвязный Список" будет хранить свой размер (чтобы не пересчитывать количество элементов каждый раз), а также указатель head, ссылающийся на первый элемент, и указатель tail, ссылающийся на последний элемент
typedef struct _DblLinkedList { size_t size; Node *head; Node *tail; } DblLinkedList;
В случае, когда в списке нет элементов, оба они равны нулю. Если в списке один элемент, то оба указателя ссылаются на один и тот же элемент (соответственное, они равны). Об этом постоянно следует помнить: каждый раз, удаляя или вставляя элемент, придётся проверять, чтобы указатели head и tail правильно хранили адреса.
Первая функция, как обычно, создаёт экземпляр структуры DblLinkedList
DblLinkedList* createDblLinkedList() { DblLinkedList *tmp = (DblLinkedList*) malloc(sizeof(DblLinkedList)); tmp->size = 0; tmp->head = tmp->tail = NULL; return tmp; }
В ней нет ничего интересного. Заодно опишем функцию, которая удаляет список
void deleteDblLinkedList(DblLinkedList **list) { Node *tmp = (*list)->head; Node *next = NULL; while (tmp) { next = tmp->next; free(tmp); tmp = next; } free(*list); (*list) = NULL; }
Теперь, определим набор стандартных функций – pushFront и popFront для работы с головой, pushBack И popBack для работы с последним элементом, getNth, insert и deleteNth для вставки и удаления в произвольное место.
Вставка спереди очень похожа на вставку в односвязный список. Сначала создаётся новый элемент
Node *tmp = (Node*) malloc(sizeof(Node)); if (tmp == NULL) { exit(1); }
потом задаём ему значения
tmp->value = data; tmp->next = list->head; tmp->prev = NULL;
Так как он стал первым, то указатель next ссылается на старую голову списка, а предыдущего элемента нет. Теперь, если в списке уже был головной элемент, то его указатель prev должен ссылаться на вновь созданный элемент
if (list->head) { list->head->prev = tmp; }
Теперь проверим указатель tail. Если он пустой, то после добавления нового элемента он должен ссылаться на него
if (list->tail == NULL) { list->tail = tmp; }
Теперь перекинем указатель head на вновь созданный элемент и увеличим значение счётчика size
list->head = tmp; list->size++;
Весь код
void pushFront(DblLinkedList *list, void *data) { Node *tmp = (Node*) malloc(sizeof(Node)); if (tmp == NULL) { exit(1); } tmp->value = data; tmp->next = list->head; tmp->prev = NULL; if (list->head) { list->head->prev = tmp; } list->head = tmp; if (list->tail == NULL) { list->tail = tmp; } list->size++; }
Удаление из начала списка также похоже на оное для односвязного списка. Прибавляются только перекидывания дополнительных указателей и проверка, чтобы указатель на последний элемент, в случае, если элементов больше не осталось, стал равным нулю.
Сначала создадим указатель на первый элемент списка. Он понадобится, чтобы после изменения всех указателей prev и next мы смогли удалить узел.
Node *prev; void *tmp; if (list->head == NULL) { exit(2); } prev = list->head;
После этого перекинем указатель head на следующий за ним элемент
list->head = list->head->next;
Далее проверяем, что удаляемы элемент не является одновременно последним (когда в списке всего один элемент), после чего освобождаем память.
Полный код
void* popFront(DblLinkedList *list) { Node *prev; void *tmp; if (list->head == NULL) { exit(2); } prev = list->head; list->head = list->head->next; if (list->head) { list->head->prev = NULL; } if (prev == list->tail) { list->tail = NULL; } tmp = prev->value; free(prev); list->size--; return tmp; }
Вставка в конец и удаление с конца очень похожи - просто мы переворачиваем список. Соответственное, все prev меняются на next, а head на tail
void pushBack(DblLinkedList *list, void *value) { Node *tmp = (Node*) malloc(sizeof(Node)); if (tmp == NULL) { exit(3); } tmp->value = value; tmp->next = NULL; tmp->prev = list->tail; if (list->tail) { list->tail->next = tmp; } list->tail = tmp; if (list->head == NULL) { list->head = tmp; } list->size++; } void* popBack(DblLinkedList *list) { Node *next; void *tmp; if (list->tail == NULL) { exit(4); } next = list->tail; list->tail = list->tail->prev; if (list->tail) { list->tail->next = NULL; } if (next == list->head) { list->head = NULL; } tmp = next->value; free(next); list->size--; return tmp; }
Получение n-го элемента очень простое и не отличается от оного для односвязного списка.
Node* getNth(DblLinkedList *list, size_t index) { Node *tmp = list->head; size_t i = 0; while (tmp && i < index) { tmp = tmp->next; i++; } return tmp; }
Можно улучшить эту функцию: если список длинный, то в зависимости от индекса можно проходить либо с начала в конец, либо с конца в начало. Это позволяет всегда использовать не более N/2 шагов.
Node* getNthq(DblLinkedList *list, size_t index) { Node *tmp = NULL; size_t i; if (index < list->size/2) { i = 0; tmp = list->head; while (tmp && i < index) { tmp = tmp->next; i++; } } else { i = list->size - 1; tmp = list->tail; while (tmp && i > index) { tmp = tmp->prev; i--; } } return tmp; }
Теперь можно написать функцию удаления и вставки узла. Сначала находим нужный элемент, затем создаём либо новый узел (если вставка), либо указатель на удаляемый элемент. Затем изменяем все указатели.
void insert(DblLinkedList *list, size_t index, void *value) { Node *elm = NULL; Node *ins = NULL; elm = getNth(list, index); if (elm == NULL) { exit(5); } ins = (Node*) malloc(sizeof(Node)); ins->value = value; ins->prev = elm; ins->next = elm->next; if (elm->next) { elm->next->prev = ins; } elm->next = ins; if (!elm->prev) { list->head = elm; } if (!elm->next) { list->tail = elm; } list->size++; } void* deleteNth(DblLinkedList *list, size_t index) { Node *elm = NULL; void *tmp = NULL; elm = getNth(list, index); if (elm == NULL) { exit(5); } if (elm->prev) { elm->prev->next = elm->next; } if (elm->next) { elm->next->prev = elm->prev; } tmp = elm->value; if (!elm->prev) { list->head = elm->next; } if (!elm->next) { list->tail = elm->prev; } free(elm); list->size--; return tmp; }
Не забываем, конечно, смотреть за значениями head И tail, чтобы они указывали на существующие в данный момент элементы.
Добавим пару вспомогательных функций, которые помогут в работе. Первая - это печать списка. Так как тип значения - void*, то необходимо передавать функцию печати одного элемента.
void printDblLinkedList(DblLinkedList *list, void (*fun)(void*)) { Node *tmp = list->head; while (tmp) { fun(tmp->value); tmp = tmp->next; } printf("\n"); }
В примерах будем использовать переменные типа int
void printInt(void *value) { printf("%d ", *((int*) value)); }
Вторая функция – создание списка из массива
DblLinkedList* fromArray(void *arr, size_t n, size_t size) { DblLinkedList *tmp = NULL; size_t i = 0; if (arr == NULL) { exit(7); } tmp = createDblLinkedList(); while (i < n) { pushBack(tmp, ((char*)arr + i*size)); i++; } return tmp; }
Теперь можно пользоваться двусвязным списком
void main() { DblLinkedList *list = createDblLinkedList(); int a, b, c, d, e, f, g, h; a = 10; b = 20; c = 30; d = 40; e = 50; f = 60; g = 70; h = 80; pushFront(list, &aamp;a); pushFront(list, &b); pushFront(list, &c); pushBack(list, &d); pushBack(list, &e); pushBack(list, &f); printDblLinkedList(list, printInt); printf("length %d\n", list->size); printf("nth 2 %d\n", *((int*)(getNthq(list, 2))->value)); printf("nth 5 %d\n", *((int*)(getNthq(list, 5))->value)); printf("popFront %d\n", *((int*)popFront(list))); printf("popFront %d\n", *((int*)popFront(list))); printf("head %d\n", *((int*)(list->head->value))); printf("tail %d\n", *((int*)(list->tail->value))); printf("popBack %d\n", *((int*)popBack(list))); printf("popBack %d\n", *((int*)popBack(list))); printf("length %d\n", list->size); printDblLinkedList(list, printInt); insert(list, 1, &g); printDblLinkedList(list, printInt); deleteNth(list, 0); printDblLinkedList(list, printInt); deleteDblLinkedList(&list); getch(); }
Сортировка вставками
Ранее мы рассмотрели алгоритм сортировки однонаправленного связного списка методом слияния. Двусвязный список можно сортировать точно также, поэтому сейчас рассмотрим другой алгоритм - сортировку вставками. Суть алгоритма очень простая – создаём новый двунаправленный связный список. Вставляем в него первый элемент неотсортированного списка. Для вставки второго элемента проходим по отсортированному списку и ищем место, куда вставить. Если место не найдено, то вставляем в конец. Очевидно, что если тип данных не известен, то необходимо будет передавать функцию сравнения, с помощью которой можно изменить порядок сортировки.
Для реализации нам понадобится ещё одна функция - вставка до указанного элемента. Эта функция будет получать указатель на список, указатель на узел, перед которым нужно вставить элемент и новые данные.
void insertBeforeElement(DblLinkedList *list, Node* elm, void *value) { Node *ins = NULL; if (elm == NULL) { exit(6); } if (!elm->prev) { pushFront(list, value); return; } ins = (Node*) malloc(sizeof(Node)); ins->value = value; ins->prev = elm->prev; elm->prev->next = ins; ins->next = elm; elm->prev = ins; list->size++; }
Теперь непосредственно сортировка
void insertionSort(DblLinkedList **list, int (*cmp)(void*, void*)) { DblLinkedList *out = createDblLinkedList(); Node *sorted = NULL; Node *unsorted = NULL; pushFront(out, popFront(*list)); unsorted = (*list)->head; while (unsorted) { sorted = out->head; while (sorted && !cmp(unsorted->value, sorted->value)) { sorted = sorted->next; } if (sorted) { insertBeforeElement(out, sorted, unsorted->value); } else { pushBack(out, unsorted->value); } unsorted = unsorted->next; } free(*list); *list = out; }
Видно, что в конце в переданном списке не остаётся элементов, так как мы их выталкиваем, так что старый список мы подменяем на вновь созданный.
Сложность алгоритма – O(n2), мы имеем одни проход по неотсортированному списку сложностью порядка n, для каждого элемента проходим по отсортированному.
Так как при каждом создании нового узла мы удаляем узел из первого списка, то дополнительной памяти не требуется.
Тепер сравним сложности различных операций для односвязного и двусвязного списка. Однонаправленный связный список
pushFront | popFront | pushBack | popBack | insert | delete | get | size |
---|---|---|---|---|---|---|---|
O(1) | O(1) | O(1) | O(n) | O(n) | O(n) | O(n) | O(1) |
Двусвязный список
pushFront | popFront | pushBack | popBack | insert | delete | get | size |
---|---|---|---|---|---|---|---|
O(1) | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) | O(1) |
