C: связанные списки

Связанные списки являются второй по частоте использования структурой данных после массивов.

Они являются достаточно простой реализацией динамических структур данных, использующие указатели (pointers) для реализации.

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

Ниже рассмотрены примеры работы с односвязными (или однонаправленными) списками.

Описание

Кратко — связанный список работает как массив, который может расти и уменьшаться при необходимости из любой точки массива.

Связаные списки имеют несколько основных преимущств:

• элементы могут быть добавлены или удалены из середины списка
• нет необходимости объявления размера при инициализации

Но имеют и недостатки:

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

Реализация

Связанный список — это коллекция динамически выделяемых нод (элементов списка), организованных таким образом, что каждая нода содержит одно значение и один указатель. Указатель в ноде всегда указывает на следующий член списка. Если указатель == NULL — это последняя нода в списке.

    ------------------------------              ------------------------------
    |              |             |            \ |              |             |
    |     DATA     |     NEXT    |--------------|     DATA     |     NEXT    |
    |              |             |            / |              |             |
    ------------------------------              ------------------------------

Определение ноды

Давайте создадим ноду связанного списка:

typedef struct node {
    int val;
    struct node * next;
} node_t;

Обратите внимание, что структура тут создаётся в виде рекурсивного дерева.

Теперь — используем ноды.

Создаём локальную переменную с именем head, которая указывает на первый элемент списка:

    node_t * head = NULL;
    head = malloc(sizeof(node_t));

    if (head == NULL) {
        return 1;
    }

    head->val = 1;
    head->next = NULL;

Полностью код сейчас будет выглядеть следующим образом:

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

typedef struct node {
    int val;
    struct node * next;
} node_t;

int main() {

    node_t * head = NULL;
    head = malloc(sizeof(node_t));

    if (head == NULL) {
        return 1;
    }

    head->val = 1;
    head->next = NULL;

    return 0;

}

Тут мы создали первую переменную в нашем списке, со значением 1 и значением NULL для поля next, что бы закончить наполнение списка.

Аналогично — мы можем добавить ещё один элемент списка, и ещё один, и ещё — пока не закончим список с NULL в next, например:

...
node_t * head = NULL;
head = malloc(sizeof(node_t));
head->val = 1;
head->next = malloc(sizeof(node_t));
head->next->val = 2;
head->next->next = NULL;
...

Получение элементов списка

Давайте добавим функцию, которая будет выводить на экран все элементы спсика.

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

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

typedef struct node {
    int val;
    struct node * next;
} node_t;

void print_list(node_t * head) {
    node_t * current = head;

    while (current != NULL) {
        printf("%d\n", current->val);
        current = current->next;
    }
}

int main() {

    node_t * head = NULL;
    head = malloc(sizeof(node_t));

    if (head == NULL) {
        return 1;
    }

    head->val = 1;
    head->next = malloc(sizeof(node_t));
    head->next->val = 2;
    head->next->next = malloc(sizeof(node_t));
    head->next->next->val = 3;
    head->next->next->next = malloc(sizeof(node_t));
    head->next->next->next->val = 4;
    head->next->next->next->next = NULL;

    print_list(head);

    return 0;
}

Собираем, проверяем:

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

...
void print_list(node_t * head) {
    node_t * current = head;

    while (current != NULL) {
        printf("Value: %d\n", current->val);
        printf("Address: %p\n", (void *)current->next);
        current = current->next;
    }
}
...

Результат:

Добавление элемента в конец списка

Для того, что бы вывести все элементы списка мы используем указатель current. Он устанавливается на адрес переменной head и затем на каждом шаге — продвигается к следующему элементу, пока не достигнет next == NULL.

Добавим функцию push() для добавления нового элемента в конец списка:

...
void push(node_t * head, int val) {

    node_t * current = head;

    while (current->next != NULL) {
        current = current->next;
    }

    /* now we can add a new variable */
    current->next = malloc(sizeof(node_t));
    current->next->val = val;
    current->next->next = NULL;
}
...

Обновляем main():

...
int main() {

    node_t * head = NULL;
    head = malloc(sizeof(node_t));

    if (head == NULL) {
        return 1;
    }

    head->val = 1;
    head->next = malloc(sizeof(node_t));
    head->next->val = 2;
    head->next->next = malloc(sizeof(node_t));
    head->next->next->val = 3;
    head->next->next->next = malloc(sizeof(node_t));
    head->next->next->next->val = 4;
    head->next->next->next->next = NULL;

    // print current list
    print_list(head);
    printf("\nList finished, adding new value 5...\n\n");
    
    // add "5" to the end
    push(head, 5);

    // print updated list
    print_list(head);

    return 0;

}
...

Собираем, проверяем:

Добавление элемента в начало списка (pop)

Для добавления нового элемента в начало списка нам потребуется:

1. создать новый элемент и добавить ему значение
2. связать новый элемент со списком, что бы он указывал на head
3. установить head нашего списка, что бы он указывал на новый элемент

(работу git-а не напоминает?)

Т.е. — мы создадим новый head списка с новым значением, а остальной список будет связан с этим head.

Т.к. мы используем фнукцию для этой операции — нам потребуется иметь возможность изменения переменной head. Для этого нам необходимо передать указатель на переменную указателя (двойной указатель, double pointer):

...
void push_start(node_t ** head, int val) {

    node_t * new_node;
    new_node = malloc(sizeof(node_t));

    new_node->val = val;
    new_node->next = *head;
    *head = new_node;
}
...

Обновляем main(), передаём head через указатель:

int main() {
    ...
    // add 0 to start
    push_start(&head, 0);

    // print updated list
    print_list(head);

    return 0;

}

Результат:

Удаление первого элемента

Что бы удалить переменную нам потребуется обратное действие:

1. получить элемент next, на который указывает указатель head и сохранить его
2. освободить элемент head
3. установить head на следующий элемент, который мы сохранили вначале

Выглядеть такая функция может следующим образом:

...
int pop(node_t ** head) {
    
    int retval = -1;
    node_t * next_node = NULL;
    
    if (*head == NULL) {
        return -1;
    }
    
    next_node = (*head)->next;
    retval = (*head)->val;
    free(*head);
    *head = next_node;
    
    return retval;
}
...

И её вызов в main():

...
    // pop 1st element
    printf("\nRemoving 1th element...\n\n");
    pop(&head);
...

Результат:

Удаление последнего элемента

Удаление последнего элемента списка схоже с добавлением в конец списка, но с одним отличием: т.к. нам требуется изменить предпоследний элемент — нам требуется отследить два элемента впереди и проверить не является ли следующий элемент в этих двух последним (т.е. с указателем на next == NULL).

Добавляем функцию:

...
int remove_last(node_t * head) {

    int retval = 0;

    /* if there is only one item in the list, remove it */
    if (head->next == NULL) {
        retval = head->val;
        free(head);
        return retval;
    }

    /* get to the last node in the list */
    node_t * current = head;
    while (current->next->next != NULL) {
        current = current->next;
    }

    /* now current points to the last item of the list, so let's remove current->next */
    retval = current->next->val;
    free(current->next);
    current->next = NULL;
    return retval;
}
...

Обновляем main():

...
    printf("\nRemoving last item...\n\n");
    remove_last(head);

    print_list(head);
...

Результат:

Удаление определённого элемента

Что бы удалить элемент по его индексу от начала списка или по значению — нам требуется пройтись по всему списку, проверяя следующий элемент — не является ли он искомым, который мы хотим удалить:

1. проверяем элементы до того, который требуется удалить
2. сохраняем ноду (элемент), который будем удалять, во временном указателе
3. сместить указатель предыдущей ноды на ноду следующую после той, которую будем удалять

Создаём функцию:

...
int remove_last(node_t * head) {

    int retval = 0;

    /* if there is only one item in the list, remove it */
    if (head->next == NULL) {
        retval = head->val;
        free(head);
        return retval;
    }

    /* get to the last node in the list */
    node_t * current = head;
    while (current->next->next != NULL) {
        current = current->next;
    }

    /* now current points to the last item of the list, so let's remove current->next */
    retval = current->next->val;
    free(current->next);
    current->next = NULL;
    return retval;
}
...

Обновляем main():

...
    printf("\nRemoving item with index 2...\n\n");
    remove_by_index(&head, 2);

    print_list(head);
...

Результат:

Полностью получившийся код можно посмотреть на Github.

Ссылки по теме

• Linked lists
• Linked List Program in C
• Singly linked lists in C
• C Programming Examples on Linked List