Кольцо из двусвязного списка

Кольцо на двусвязном списке.

Если направить указатель последнего элемента двунаправленного списка не на NULL, а не первый элемент, то получим структуру-кольцо. Кольцо – циклическая структура, которая обычно реализует операции вставки и удаления, а также операции next и prev, позволяющие двигаться вперёд и назад по кольцу. Если кольцо собрано из односвязного списка, то операция prev, соответственно, не поддерживается. Наша структура-кольцо будет, подобно двусвязному списку, хранить указатель на узел кольца и его размер.

typedef int T;

typedef struct _Node {
	T data;
	struct _Node *next;
	struct _Node *prev;
} Node;

typedef struct _Ring {
	size_t size;
	Node *current;
} Ring;

Ring* createRing() {
	Ring *tmp = (Ring*)malloc(sizeof(Ring));
	
	tmp->size = 0;
	tmp->current = NULL;

	return tmp;
}

Никаких особенностей здесь нет. Всё очень похоже на двусвязный список. Функции добавления и удаления элементов:

void addElement(Ring *ring, T value) {
	Node *prev = NULL;
	Node *tmp = (Node*)malloc(sizeof(Node));

	tmp->data = value;
	//Если в кольце нет элементов
	if (ring->current == NULL) {
		ring->current = tmp;
		tmp->next = tmp->prev = tmp;			
	} else {
		prev = ring->current->next->prev;
		tmp->next = ring->current->next;
		tmp->prev = ring->current;
		prev->prev = tmp;
		ring->current->next = tmp;
		ring->current = tmp;	
	}
	ring->size++;
}

T removeElement(Ring *ring) {
	Node *afterTarget = NULL;
	T retVal;

	if (ring->current == NULL) {
		exit(1);
	}

	//Если в кольце последний элемент
	if (ring->current->next == ring->current) {
		retVal = ring->current->data;
		free(ring->current);
		ring->current = NULL;			
	} else {
		afterTarget = ring->current->next;
		ring->current->prev->next = afterTarget;
		afterTarget->prev = ring->current->prev;
		retVal = ring->current->data;
		free(ring->current);
		ring->current = afterTarget;
	}
	ring->size--;
	return retVal;
}

Заметьте, что при добавлении нового элемента указатель на элемент кольца сдвигается на вновь добавленный элемент. При удалении указатель current сдвигается на следующий элемент, после удаляемого. Функции prev и next позволяют двигаться по кольцевому списку. next сдвигает указатель current вперёд, prev назад.

Node* next(Ring *ring) {
	Node* retVal = NULL;
	if (ring->current) {
		ring->current = ring->current->next;
		retVal = ring->current;
	} 
	return retVal;
}

Node* prev(Ring *ring) {
	Node* retVal = NULL;
	if (ring->current) {
		ring->current = ring->current->prev;
		retVal = ring->current;
	}
	return retVal;
}

Последняя функция – circle. Она получает кольцо и функцию, которую применяет к каждому узлу кольца. Мы обходим кольцо до тех пор, пока не наткнёмся на первый узел. Все узлы имеют разный адрес в памяти благодаря тому, что функция addElement создаёт для каждого элемента новый узел

void circle(const Ring *ring, void (*f)(Node* node)) {
	Node *anchor = ring->current;
	if (anchor) {		
		do {
			f(anchor);
			anchor = anchor->next;
		} while (anchor != ring->current);
	}
}

void printNode(Node *node) {
	printf("%d ", node->data);
}

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