Погружение в мир односвязных списков на языке C: от основ до реализации

Когда речь заходит о структурах данных, односвязные списки занимают особое место. Они просты, но в то же время невероятно мощные. Если вы когда-либо задумывались, как реализовать односвязный список на языке C, то эта статья для вас. Мы не просто рассмотрим теорию, но и шаг за шагом создадим свою собственную реализацию, разберёмся в нюансах и узнаем, где и как можно применить эту структуру данных на практике.

Что такое односвязный список?

Перед тем как погрузиться в реализацию, давайте разберёмся, что же такое односвязный список. Это линейная структура данных, в которой каждый элемент (узел) содержит данные и ссылку на следующий узел. В отличие от массивов, односвязные списки не требуют выделения фиксированного объёма памяти, что делает их более гибкими.

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

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

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

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

Здесь мы объявили структуру Node, которая содержит целочисленное поле data и указатель на следующий узел next. Теперь, когда у нас есть базовая структура, давайте перейдём к реализации самого списка.

Создание односвязного списка

Теперь, когда мы определили структуру узла, давайте создадим сам односвязный список. Мы начнём с определения структуры списка, которая будет содержать указатель на первый узел.

typedef struct LinkedList {
    Node* head;  // Указатель на первый узел
} LinkedList;

С помощью этой структуры мы сможем управлять нашим списком. Теперь давайте добавим функции для работы с нашим односвязным списком. Мы начнём с функции, которая создаёт новый узел.

Функция для создания нового узла

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // Выделяем память
    newNode->data = data;                        // Заполняем данные
    newNode->next = NULL;                        // Указываем на NULL
    return newNode;                              // Возвращаем новый узел
}

Эта функция выделяет память для нового узла, заполняет его данными и устанавливает указатель на следующий узел в NULL, так как это будет последний узел на данный момент.

Добавление узла в начало списка

Теперь давайте реализуем функцию, которая добавляет новый узел в начало списка. Это довольно простая операция, которая требует обновления указателя head.

void insertAtBeginning(LinkedList* list, int data) {
    Node* newNode = createNode(data); // Создаём новый узел
    newNode->next = list->head;        // Указываем на текущий первый узел
    list->head = newNode;              // Обновляем указатель head
}

Функция insertAtBeginning получает указатель на список и данные для нового узла. Она создаёт новый узел, устанавливает его next на текущий первый узел и обновляет указатель head.

Добавление узла в конец списка

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

void insertAtEnd(LinkedList* list, int data) {
    Node* newNode = createNode(data); // Создаём новый узел
    if (list->head == NULL) {          // Если список пуст
        list->head = newNode;          // Устанавливаем head на новый узел
        return;
    }
    Node* temp = list->head;          // Временный указатель
    while (temp->next != NULL) {      // Проходим до конца списка
        temp = temp->next;
    }
    temp->next = newNode;              // Добавляем новый узел в конец
}

В этой функции мы сначала проверяем, пуст ли список. Если да, то новый узел становится первым. В противном случае мы проходим по списку, пока не найдём последний узел, и добавляем новый узел в конец.

Удаление узла из списка

Теперь, когда мы можем добавлять узлы, давайте добавим возможность их удаления. Удаление узла может быть выполнено по значению или по индексу. Начнём с удаления узла по значению.

void deleteNode(LinkedList* list, int key) {
    Node* temp = list->head;          // Временный указатель
    Node* prev = NULL;                // Указатель на предыдущий узел
    // Если узел для удаления - первый
    if (temp != NULL && temp->data == key) {
        list->head = temp->next;      // Обновляем head
        free(temp);                   // Освобождаем память
        return;
    }
    // Проходим по списку
    while (temp != NULL && temp->data != key) {
        prev = temp;                  // Сохраняем предыдущий узел
        temp = temp->next;            // Переходим к следующему
    }
    // Если узел не найден
    if (temp == NULL) return;
    prev->next = temp->next;          // Удаляем узел
    free(temp);                       // Освобождаем память
}

Эта функция проходит по списку, ищет узел с указанным значением и удаляет его. Мы также обрабатываем случай, когда удаляемый узел – это первый узел списка.

Вывод списка

Чтобы увидеть, как работает наш односвязный список, давайте добавим функцию для его вывода. Это поможет нам убедиться, что все операции выполняются корректно.

void printList(LinkedList* list) {
    Node* temp = list->head;          // Временный указатель
    while (temp != NULL) {            // Проходим по списку
        printf("%d -> ", temp->data); // Выводим данные
        temp = temp->next;            // Переходим к следующему
    }
    printf("NULLn");                  // Завершаем вывод
}

Функция printList проходит по всему списку и выводит данные каждого узла, заканчивая вывод NULL, чтобы указать на конец списка.

Пример использования односвязного списка

Теперь давайте соберём все наши функции вместе и создадим небольшой пример использования односвязного списка. Это поможет вам увидеть, как всё работает в реальном времени.

int main() {
    LinkedList list;                  // Создаём новый список
    list.head = NULL;                 // Изначально он пуст

    insertAtBeginning(&list, 10);     // Добавляем узлы
    insertAtBeginning(&list, 20);
    insertAtEnd(&list, 30);
    insertAtEnd(&list, 40);

    printf("Содержимое списка: ");
    printList(&list);                 // Выводим список

    deleteNode(&list, 20);            // Удаляем узел
    printf("После удаления узла 20: ");
    printList(&list);                 // Выводим список снова

    return 0;                         // Завершаем программу
}

В этом примере мы создаём односвязный список, добавляем несколько узлов, выводим их содержимое, удаляем один узел и снова выводим содержимое списка. Это наглядно демонстрирует, как работает наша реализация.

Заключение

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

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

Не бойтесь экспериментировать и улучшать свою реализацию! Удачи в программировании!