Связанные списки


Вступление

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

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

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

  1. Элементы могут быть добавлены или удалены из середины списка
  2. Нет необходимости определять начальный размер

Однако у связанных списков есть и несколько недостатков:

  1. Не существует «случайного» доступа - невозможно достичь n-го элемента в массиве без предварительной итерации по всем элементам до этого элемента. Это означает, что мы должны начать с начала списка и подсчитать, сколько раз мы продвигаемся по списку, пока не дойдем до желаемого элемента.
  2. Требуются динамическое выделение памяти и указатели, что усложняет код и увеличивает риск утечек памяти и ошибок сегментов.
  3. Связанные списки имеют гораздо большие накладные расходы по сравнению с массивами, поскольку элементы связанного списка выделяются динамически (что менее эффективно с точки зрения использования памяти), и каждый элемент в списке также должен хранить дополнительный указатель.

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

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

Связанный список хранится с использованием локальной переменной-указателя, которая указывает на первый элемент списка. Если этот указатель также имеет значение NULL, то список считается пустым.

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

Определим узел связанного списка:

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

Обратите внимание, что мы определяем структуру рекурсивным образом, что возможно в C. Давайте назовем наш тип узла node_t.

Теперь мы можем использовать узлы. Давайте создадим локальную переменную, которая указывает на первый элемент списка (названный head).

node_t * head = NULL;
head = (node_t *) malloc(sizeof(node_t));
if (head == NULL) {
    return 1;
}

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

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

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

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

Это может продолжаться и продолжаться, но на самом деле нам следует перейти к последнему элементу списка, пока nextпеременная не станет такой NULL.

Перебор списка

Давайте создадим функцию, которая печатает все элементы списка. Для этого нам нужно использовать currentуказатель, который будет отслеживать узел, который мы в данный момент печатаем. После печати значения узла мы устанавливаем current указатель на следующий узел и снова печатаем, пока не дойдем до конца списка (следующий узел - NULL).

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

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

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

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

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 = (node_t *) malloc(sizeof(node_t));
    current->next->val = val;
    current->next->next = NULL;
}

Лучшими вариантами использования связанных списков являются стеки и очереди, которые мы сейчас реализуем:

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

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

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

Это фактически создаст новый заголовок в списке с новым значением и оставит остальную часть списка связанной с ним.

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

void push(node_t ** head, int val) {
    node_t * new_node;
    new_node = (node_t *) malloc(sizeof(node_t));

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

Удаление первого пункта (выскакивание из списка)

Чтобы извлечь переменную, нам нужно отменить это действие:

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

Вот код:

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

Удаление последнего пункта списка

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

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 second to last node in the list */
    node_t * current = head;
    while (current->next->next != NULL) {
        current = current->next;
    }

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

}

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

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

Вот алгоритм:

  1. Перейти к узлу перед узлом, который мы хотим удалить
  2. Сохраните узел, который мы хотим удалить, во временном указателе
  3. Установите следующий указатель предыдущего узла так, чтобы он указывал на узел после узла, который мы хотим удалить.
  4. Удалите узел с помощью временного указателя

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

int remove_by_index(node_t ** head, int n) {
    int i = 0;
    int retval = -1;
    node_t * current = *head;
    node_t * temp_node = NULL;

    if (n == 0) {
        return pop(head);
    }

    for (i = 0; i < n-1; i++) {
        if (current->next == NULL) {
            return -1;
        }
        current = current->next;
    }

    temp_node = current->next;
    retval = temp_node->val;
    current->next = temp_node->next;
    free(temp_node);

    return retval;

}

Упражнение

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