linked_list.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
} typedef Node;

// Двунаправленный связной список
struct LinkedList {
    size_t capacity;
    size_t size;
    void* data;

    Node* first;
    Node* last;
    Node* free_node;  // Свободные ячейки в памяти
} typedef LinkedList;

LinkedList create_linked_list(const size_t capacity) {
    LinkedList linked_list;
    linked_list.capacity = capacity;
    linked_list.size = 0;
    linked_list.data = malloc(capacity * sizeof(Node));
    linked_list.first = NULL;
    linked_list.last = NULL;

    // Инициализация списка свободных позиций - кастомный аллокатор
    linked_list.free_node = linked_list.data;
    Node* current_node = linked_list.data + sizeof(Node);
    current_node->prev = linked_list.free_node;
    linked_list.free_node->next = current_node;

    for (size_t i = 1; i < capacity; ++i) {
        Node *node = linked_list.data + i * sizeof(Node);
        current_node->next = node;
        current_node = node;
    }

    return linked_list;
}

void free_linked_list(LinkedList* linked_list) {
    free(linked_list->data);
}

Node* allocate_node(LinkedList* linked_list) {
    assert(linked_list->size + 1 <= linked_list->capacity && "Overflow");
    assert(linked_list->free_node != NULL && "No free memory");

    ++linked_list->size;
    Node* node = linked_list->free_node;
    linked_list->free_node = node->next;
    return node;
}

void free_node(LinkedList* linked_list, Node* node) {
    assert(linked_list->size - 1 >= 0 && "List is empty");
    assert(node != NULL && "Node is NULL");

    --linked_list->size;
    node->next = linked_list->free_node;
    linked_list->free_node = node;
}

Node* insert_after_node(LinkedList* linked_list, Node* target_node, int value) {
    Node* node = allocate_node(linked_list);
    node->data = value;

    // Обновление связей
    node->prev = target_node;
    node->next = NULL;
    target_node->next = node;

    if (target_node == linked_list->last) {
        linked_list->last = node;
    }

    return node;
}

// Вставка в конец списка
Node* insert_after(LinkedList *linked_list, int value) {
    if (linked_list->last == NULL) {
        Node* node = allocate_node(linked_list);
        node->data = value;
        node->next = NULL;
        node->prev = NULL;
        linked_list->first = node;
        linked_list->last = node;
        return node;
    }

    return insert_after_node(linked_list, linked_list->last, value);
}

void remove_node(LinkedList* linked_list, Node* node) {
    Node* prev = node->prev;
    Node* next = node->next;

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

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

    free_node(linked_list, node);
}

// Вставка в начало списка
Node* insert_before(LinkedList* linkedList, int value) {
    // Аналогично, лень писать
}

int main() {
    LinkedList list = create_linked_list(10);
    insert_after(&list, 123);
    insert_after(&list, 1354);
    Node* node_to_remove = insert_after(&list, 341);
    insert_after(&list, 22);
    insert_after(&list, 5546);
    insert_after(&list, 2);

    remove_node(&list, node_to_remove);

    printf("CAPACITY: %zu\n", list.capacity);
    printf("SIZE: %zu\n", list.size);

    Node* current = list.first;

    // Проход по всем элементам
    while (current != list.last) {
        printf("%d->", current->data);
        current = current->next;
    }

    printf("%d\n", list.last->data);

    free_linked_list(&list);
    return 0;
}