Linked List в C: изучение основ и продвинутых методов

Связанный список (linked list) в языке C – это структура данных, которая состоит из набора узлов, каждый из которых содержит значение и указатель на следующий узел в списке.

Пример кода для объявления структуры узла связанного списка:

c
struct Node {
    int data;
    struct Node* next;
};

Здесь мы определяем структуру узла, состоящую из целочисленного значения (data) и указателя на следующий узел (next).

Для создания и инициализации нового узла мы можем использовать функцию malloc() для выделения памяти под новый узел и оператор "->" для доступа к полям структуры через указатель:

c
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

Эта функция создает новый узел со значением data и указателем на следующий узел, установленным в NULL.

Для добавления нового узла в конец связанного списка мы можем использовать цикл while для перебора узлов до последнего, затем добавляем новый узел как следующий за последним узлом:

c
void append(struct Node** headRef, int data) {
    struct Node* newNode = newNode(data);
    struct Node* last = *headRef;
    if (*headRef == NULL) {
        *headRef = newNode;
        return;
    }
    while (last->next != NULL) {
        last = last->next;
    }
    last->next = newNode;
    return;
}

Здесь мы передаем указатель на указатель на начало (headRef) по ссылке, так как может потребоваться обновление значения, если список пустой. Если список пустой, то мы устанавливаем указатель на начало равным указателю на новый узел. Если список не пустой, то мы находим последний узел и устанавливаем новый узел как следующий за последним.

Остальные функции, такие как обход связанного списка, вставка узла в начало списка, удаление узла из конца списка и т.д., могут быть реализованы с использованием указателей и операций присваивания.

c
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}
void push(struct Node** headRef, int data) {
    struct Node* node = newNode(data);
    node->next = *headRef;
    *headRef = node;
}
void deleteTail(struct Node** headRef) {
    struct Node* temp = *headRef;
    struct Node* prev;
    if (temp == NULL || temp->next == NULL) {
        free(temp);
        *headRef = NULL;
        return;
    }
    while (temp->next != NULL) {
        prev = temp;
        temp = temp->next;
    }
    free(temp);
    prev->next = NULL;
}

Таким образом, связанный список – это мощная структура данных в C, позволяющая эффективно добавлять, удалять и обновлять элементы списка. Реализация связанного списка в C может показаться сложной и запутанной, но с опытом использования этой структуры данных становится более понятной.