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

На Главную / Структуры данных / Двусвязный список

Теги: Двусвязный список, двунаправленный связный список, си, сортировка списка вставками

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

Мы рассмотрели односвязный список и пришли к неутешительным выводам - список разумно использовать в качестве стека, потому что операции вставки в начало списка и удаления из начала списка имеют сложность порядка 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;

Пустая структура типа DblLinkedList

В случае, когда в списке нет элементов, оба они равны нулю. Если в списке один элемент, то оба указателя ссылаются на один и тот же элемент (соответственное, они равны). Об этом постоянно следует помнить: каждый раз, удаляя или вставляя элемент, придётся проверять, чтобы указатели head и tail правильно хранили адреса.

Структура типа DblLinkedList с одним элементом

Первая функция, как обычно, создаёт экземпляр структуры 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

Перекинули указазатель head списка на вновь созданный элемент

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;

Перекидываем указатель head на следующий элемент

Далее проверяем, что удаляемы элемент не является одновременно последним (когда в списке всего один элемент), после чего освобождаем память.

Создали указатель на первый элемент

Полный код

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(n²), мы имеем одни проход по неотсортированному списку сложностью порядка 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)

Q&A

Всё ещё не понятно? – пиши вопросы на ящик

Улучшение односвязного списка

Кольцевой двусвязный список