Ускоряем работу односвязного списка

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

Можно сильно ускорить работу со списком, если хранить одновременно указатель на голову, указатель на последний элемент и размер списка. Реализуем базовые операции: вставка в начало и конец, удаление из начала, вставка и удаление элемента из произвольного места списка.

Кроме того, будем хранить в узле не тип int, а указатель на переменную произвольного типа.

typedef struct Node {
	void *value;
	struct Node *next;
} Node;

typedef struct LinkedList {
	Node *head;
	Node *tail;
	size_t size;
} LinkedList;

Далее, заведём набор ошибок, чтобы потом было проще отлаживать программу

typedef enum LINKED_LIST_ERRORS {
	MEMORY_EXHAUST,
	LIST_UNDERFLOW,
	BAD_ELEMENT_NUMBER
} LINKED_LIST_ERRORS;

static char *LINKED_LIST_ERRORS_STR[3] = {
	"Memory Exhaust: can't allocate memory",
	"List Underflow: can't pop more elements",
	"Bad Element Number: no such element in list"
};

Список ошибок, естественно, можно дальше расширять.

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

LinkedList* createLinkedList() {
	LinkedList* tmp = (LinkedList*) malloc(sizeof(LinkedList));
	tmp->head = tmp->tail = NULL;
	tmp->size = 0;

	return tmp;
}

Здесь нет ничего интересного. Также делаем функцию удаления списка.

void deleteLinkedList(LinkedList **list) {
	Node* prev = NULL;
	while ((*list)->head->next) {
		prev = (*list)->head;
		(*list)->head = (*list)->head->next;
		free(prev);
	}
	free((*list)->head);
	free(*list);
	*list = NULL;
}

Теперь самое интересное. Функция pushFront не сильно отличается от той, которую мы рассматривали ранее. Единственная разница в том, что нужно проверять - если указатель tail равнялся NULL, то это первый элемент и ему надо присвоить указатель на вновь созданный узел.

void pushFront(LinkedList *list, void *value) {
	Node *tmp = (Node*) malloc(sizeof(Node));
	if (tmp == NULL) {
		throwListError(MEMORY_EXHAUST, __LINE__);
	}

	tmp->next = list->head;
	tmp->value = value;
	list->head = tmp;
	if (list->tail == NULL) {
		list->tail = tmp;
	}
	list->size++;
}

Здесь появляется функция throwListError - функция выводит сообщение и приложение заканчивается с ошибкой.

void throwListError(LINKED_LIST_ERRORS err, int line) {
	printf("LinkedList.c [%d] %s", line, LINKED_LIST_ERRORS_STR[err]);
	exit(err);
}

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

void printList(LinkedList *list, void (*fun)(void *)) {
	Node *iter = list->head;
	while (iter) {
		fun(iter->value);
		iter = iter->next;
	}
	printf("\n");
}

Теперь приступим к проверке. Вот здесь всё становится несколько сложнее.

#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include "LinkedList.h"

void printInt(void *a) {
	printf("%d ", *((int*) a));
}

void main() {
	LinkedList *list = createLinkedList();
	int a, b, c;

	a = 10;
	b = 20;
	c = 30;
	pushFront(list, &a);
	pushFront(list, &b);
	pushFront(list, &c);

	printList(list, printInt);
	getch();
	deleteLinkedList(&list);
}

Так как узел хранит адрес переменной, то необходимо, чтобы, во-первых, передаваемая переменная имела адрес, а во-вторых, эта переменная должна жить всё время, что мы работаем со списком.

void main() {
	LinkedList *list = createLinkedList();
	int a, b, c;
	a = 10;
	b = 20;
	c = 30;
	pushFront(list, &a);
	pushFront(list, &b);
	pushFront(list, &c);
	printList(list, printInt);
	a = 30;
	c = 10;
	printList(list, printInt);
	deleteLinkedList(&list);
	getch();
}

Если требуется много работать с объектами, добавлять и удалять значения, то иногда будет сложно хранить их и определять, какие из них удалены, а какие ещё живут. Одно из решений – хранить в структуре списка указатель на функции, которые бы работали с нужным типом данных. Так как природа объектов может быть любой, то необходимо уметь копировать объект, чтобы вставлять копию на него, вместо указателя на оригинал, а также нужна функция удаления объекта из узла.

typedef struct LinkedList {
	Node *head;
	Node *tail;
	size_t size;
	void* (*copy)(void*);
	void (*ifree)(void*);
} LinkedList;

Не забываем, что мы не реализуем функцию сортировки, ведь в таком случае нам понадобилась бы ещё и функция сравнения.

Тогда создание объекта типа односвязный список будет выглядеть как-то так

LinkedList* createLinkedList(void* (*copy)(void*), void (*ifree)(void*)) {
	LinkedList* tmp = (LinkedList*) malloc(sizeof(LinkedList));
	tmp->head = tmp->tail = NULL;
	tmp->size = 0;
	tmp->copy = copy;
	tmp->ifree = ifree;

	return tmp;
}

Удаление

void deleteLinkedList(LinkedList **list) {
	Node* prev = NULL;
	while ((*list)->head->next) {
		prev = (*list)->head;
		(*list)->head = (*list)->head->next;
		(*list)->ifree(prev->value);
		free(prev);
	}
	(*list)->ifree((*list)->head->value);
	free((*list)->head);
	free(*list);
	*list = NULL;
}

Вставки в начало и конец

void pushFront(LinkedList *list, void *value) {
	Node *tmp = (Node*) malloc(sizeof(Node));
	if (tmp == NULL) {
		throwListError(MEMORY_EXHAUST, __LINE__);
	}

	tmp->next = list->head;
	tmp->value = list->copy(value);
	list->head = tmp;
	if (list->tail == NULL) {
		list->tail = tmp;
	}
	list->size++;
}

void shift(LinkedList *list, void *value) {
	Node *tmp = (Node*) malloc(sizeof(Node));
	if (tmp == NULL) {
		throwListError(MEMORY_EXHAUST, __LINE__);
	}

	tmp->next = NULL;
	tmp->value = list->copy(value);
	if (list->tail) {
		list->tail->next = tmp;
	}
	list->tail = tmp;
	if (list->head == NULL) {
		list->head = tmp;
	}
	list->size++;
}

А вот выталкивание из начала не поменялось: удалением данных должен озаботится тот, кто их принял

void* popFront(LinkedList *list) {
	Node *tmp = NULL;
	void *value = NULL;
	if (list->head == NULL) {
		throwListError(LIST_UNDERFLOW, __LINE__);
	}

	tmp = list->head;
	value = tmp->value;
	list->head = list->head->next;
	if (list->tail == tmp) {
		list->tail = NULL;
	}
	free(tmp);
	list->size--;

	return value;
}

К сожалению, выталкивание элемента с конца не получится реализовать так же просто. Его сложность останется n и потребует прохода всех элементов, пока мы не доберёмся до предпоследнего.

Поиск n-го элемента ничем не отличается от оного для прошлой реализации, его сложность n. Вставка и удаление также остались со сложностью порядка n.

void insert(LinkedList *list, void *value, size_t n) {
	unsigned i = 0;
	Node *tmp = NULL;
	Node *iter = list->head;
	while (i < n) {
		if (iter == NULL) {
			throwListError(BAD_ELEMENT_NUMBER, __LINE__);
		}
		iter = iter->next;
		i++;
	}
	tmp = (Node*) malloc(sizeof(Node));
	tmp->value = list->copy(value);
	
	if (iter->next) {
		tmp->next = iter->next;
	} else {
		tmp->next = NULL;
		list->tail->next = tmp;
	}

	list->size++;
	iter->next = tmp;
}

void* deleteNth(LinkedList *list, size_t n) {
	if (n == 0) {
		return popFront(list);
	} else {
		Node *prev = getNth(list, n-1);
		Node *elm = prev->next;
		void *val = elm->value;
		prev->next = elm->next;
		free(elm);
		if (prev->next == NULL) {
			list->tail = prev;
		}
		list->size--;
		return val;
	}
}

Таким образом, для односвязного списка, имея только указатель на первый элемент мы получили сложность

Сложность операций для односвязного списка, если хранить только указатель на первый элемент.

pushFront	popFront	pushBack	popBack	insert	delete	get	size
O(1)	O(1)	O(n)	O(n)	O(n)	O(n)	O(n)	O(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)

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

Рекурсия на односвязных списках