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

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

Если направить указатель последнего элемента двунаправленного списка не на 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);
}

Базовые операции. Сортировка вставками