Двусвязные и кольцевые списки

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

В односвязном списке можно идти только вперёд. Двусвязный список хранит ещё и адрес предыдущего узла:

typedef struct
{
    int id;
    int course;
    double score;
} Student;

typedef struct DNode
{
    Student data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

prev смотрит на предыдущий узел, next — на следующий. У первого узла prev == NULL, у последнего next == NULL.

Вставка и удаление

Вставка после узла p:

DNode *insert_after(DNode *p, Student value)
{
    DNode *node = malloc(sizeof(*node));
    if (node == NULL)
    {
        return NULL;
    }

    node->data = value;
    node->next = p->next;
    node->prev = p;

    if (p->next != NULL)
    {
        p->next->prev = node;
    }
    p->next = node;

    return node;
}

Удаление узла p:

void remove_node(DNode **head, DNode *p)
{
    if (p->prev != NULL)
    {
        p->prev->next = p->next;
    }
    else
    {
        *head = p->next;
    }

    if (p->next != NULL)
    {
        p->next->prev = p->prev;
    }

    free(p);
}

Порядок действий важен: сначала перецепляем соседей, потом освобождаем узел.

Обход в обе стороны

for (DNode *p = head; p != NULL; p = p->next)
{
    printf("%d %d %.2f\n", p->data.id, p->data.course, p->data.score);
}

for (DNode *p = tail; p != NULL; p = p->prev)
{
    printf("%d %d %.2f\n", p->data.id, p->data.course, p->data.score);
}

Если хранить только head, обратный обход начинают с последнего узла, найденного прямым проходом. Можно хранить и tail.

Разворот двусвязного списка

Нужно поменять местами prev и next у каждого узла и переставить head:

DNode *reverse(DNode *head)
{
    DNode *p = head;
    DNode *new_head = NULL;

    while (p != NULL)
    {
        DNode *next = p->next;
        p->next = p->prev;
        p->prev = next;
        new_head = p;
        p = next;
    }

    return new_head;
}

Кольцевой список

В кольцевом списке последний узел ссылается на первый, а не на NULL:

typedef struct CNode
{
    Student data;
    struct CNode *next;
} CNode;

Если список не пуст, tail->next == head. Обход нужно ограничивать: либо заранее знать количество узлов, либо остановиться, когда снова пришли к head.

CNode *p = head;
do
{
    printf("%d %d %.2f\n", p->data.id, p->data.course, p->data.score);
    p = p->next;
} while (p != head);

Задача Иосифа

Кольцевой список удобен для моделирования «считалки»: N элементов стоят по кругу, каждый K-й удаляется, счёт продолжается со следующего.

CNode *josephus(CNode *head, int k)
{
    if (head == NULL)
    {
        return NULL;
    }

    CNode *prev = head;
    while (prev->next != head)
    {
        prev = prev->next;
    }

    CNode *cur = head;
    while (cur->next != cur)
    {
        for (int i = 1; i < k; i++)
        {
            prev = cur;
            cur = cur->next;
        }

        prev->next = cur->next;
        CNode *next = cur->next;
        free(cur);
        cur = next;
    }

    return cur;
}

Функция возвращает последний оставшийся узел; его нужно освободить отдельно.

Разделение и слияние

Разделить кольцо на два можно, разорвав две связи и замкнув каждую часть. Слияние двух колец — соединить хвост первого с головой второго и наоборот. Главное — не потерять указатели и не оставить «полукольцо».

Частые ошибки

Документация

• Структуры
• Указатели
• malloc
• free

Что запомнить

1. В двусвязном узле два указателя: prev и next.
2. При вставке/удалении обновляйте оба направления.
3. Разворот двусвязного списка — обмен prev и next у каждого узла.
4. В кольцевом списке последний узел ссылается на первый.
5. Обход кольца ограничивайте возвратом к head.
6. После работы освободите все узлы.