Связный список (Linked List) в C: Справочник и примеры кода

Linked list (связный список) является одной из наиболее распространенных структур данных в программировании. Это упорядоченный набор элементов, где каждый элемент связан с последующим через ссылку.

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

struct Node {
    int data;          // данные
    struct Node* next; // указатель на следующий элемент
};

Для создания и добавления элементов в список необходимо определить указатели на голову и хвост списка, а затем добавлять новые элементы в конец списка при помощи функции `push_back()`. Пример кода для создания списка из трех элементов:

#include 
#include 
struct Node {
    int data;
    struct Node* next;
};
void push_back(struct Node** head, int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = NULL;
 
    if (*head == NULL) {
        *head = new_node;
        return;
    }
 
    struct Node* last = *head;
    while (last->next != NULL)
        last = last->next;
 
    last->next = new_node;
}
int main() {
    struct Node* head = NULL;
 
    push_back(&head, 1);
    push_back(&head, 2);
    push_back(&head, 3);
 
    struct Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
 
    return 0;
}

В данном примере создается список из трех элементов с данными 1, 2 и 3. Функция `push_back()` добавляет новый элемент в конец списка. Затем происходит обход списка и выводятся данные каждого элемента.

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