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;
}

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

[simterm]

$ gcc c_list.c -o c_list
$ ./c_list 
1
2
3
4

[/simterm]

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

...
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;
    }
}
...

Результат:

[simterm]

$ ./c_list 
Value: 1
Address: 0xa03384e030
Value: 2
Address: 0xa03384e050
Value: 3
Address: 0xa03384e070
Value: 4
Address: (nil)

[/simterm]

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

Для того, что бы вывести все элементы списка мы используем указатель 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;

}
...

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

[simterm]

$ ./c_list 
Value: 1
Address: 0xe55a509030
Value: 2
Address: 0xe55a509050
Value: 3
Address: 0xe55a509070
Value: 4
Address: (nil)

List finished, adding new value 5...

Value: 1
Address: 0xe55a509030
Value: 2
Address: 0xe55a509050
Value: 3
Address: 0xe55a509070
Value: 4
Address: 0xe55a5094a0
Value: 5
Address: (nil)

[/simterm]

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

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

создать новый элемент и добавить ему значение
связать новый элемент со списком, что бы он указывал на head
установить 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;

}

Результат:

[simterm]

$ ./c_list 
Value: 1
Address: 0xbb58b59030
Value: 2
Address: 0xbb58b59050
Value: 3
Address: 0xbb58b59070
Value: 4
Address: (nil)

List finished, adding new value 5...

Value: 1
Address: 0xbb58b59030
Value: 2
Address: 0xbb58b59050
Value: 3
Address: 0xbb58b59070
Value: 4
Address: 0xbb58b594a0
Value: 5
Address: (nil)

List finished, adding new value to begin of the list...

Value: 0
Address: 0xbb58b59010
Value: 1
Address: 0xbb58b59030
Value: 2
Address: 0xbb58b59050
Value: 3
Address: 0xbb58b59070
Value: 4
Address: 0xbb58b594a0
Value: 5
Address: (nil)

[/simterm]

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

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

получить элемент next, на который указывает указатель head и сохранить его
освободить элемент head
установить 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);
...

Результат:

[simterm]

$ ./c_list 
...
List finished, adding new value to begin of the list...

Value: 0
Address: 0x1e83d6a010
Value: 1
Address: 0x1e83d6a030
Value: 2
Address: 0x1e83d6a050
Value: 3
Address: 0x1e83d6a070
Value: 4
Address: 0x1e83d6a4a0
Value: 5
Address: (nil)

Removing 1th element...

Value: 1
Address: 0x1e83d6a030
Value: 2
Address: 0x1e83d6a050
Value: 3
Address: 0x1e83d6a070
Value: 4
Address: 0x1e83d6a4a0
Value: 5
Address: (nil)

[/simterm]

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

Удаление последнего элемента списка схоже с добавлением в конец списка, но с одним отличием: т.к. нам требуется изменить предпоследний элемент – нам требуется отследить два элемента впереди и проверить не является ли следующий элемент в этих двух последним (т.е. с указателем на 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);
...

Результат:

[simterm]

$ ./c_list                                                                                                                                                                            
...
Removing 1th element...

Value: 1
Address: 0xe6560fd030
Value: 2
Address: 0xe6560fd050
Value: 3
Address: 0xe6560fd070
Value: 4
Address: 0xe6560fd4a0
Value: 5
Address: (nil)

Removing last item...

Value: 1
Address: 0xe6560fd030
Value: 2
Address: 0xe6560fd050
Value: 3
Address: 0xe6560fd070
Value: 4
Address: (nil)

[/simterm]

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

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

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

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

...
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);
...

Результат:

[simterm]

$ ./c_list                                                                                                                                                                            
...
Removing last item...

Value: 1
Address: 0x17e28f030
Value: 2
Address: 0x17e28f050
Value: 3
Address: 0x17e28f070
Value: 4
Address: (nil)

Removing item with index 2...

Value: 1
Address: 0x17e28f030
Value: 2
Address: 0x17e28f070
Value: 4
Address: (nil)

[/simterm]

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

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

Пн	Вт	Ср	Чт	Пт	Сб	Вс
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

Описание

Реализация

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

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

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

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

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

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

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

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