Связанные списки - лучший и самый простой пример динамической структуры данных, которая использует указатели для своей реализации. Однако понимание указателей имеет решающее значение для понимания того, как работают связанные списки, поэтому, если вы пропустили руководство по указателям, вам следует вернуться и повторить его. Вы также должны быть знакомы с динамическим распределением памяти и структурами.
По сути, связанные списки функционируют как массив, который может увеличиваться и уменьшаться по мере необходимости из любой точки массива.
Связанные списки имеют несколько преимуществ перед массивами:
Однако у связанных списков есть и несколько недостатков:
Связанный список - это набор динамически выделяемых узлов, организованных таким образом, что каждый узел содержит одно значение и один указатель. Указатель всегда указывает на следующий член списка. Если указатель 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;
}
Лучшими вариантами использования связанных списков являются стеки и очереди, которые мы сейчас реализуем:
Чтобы добавить в начало списка, нам потребуется сделать следующее:
Это фактически создаст новый заголовок в списке с новым значением и оставит остальную часть списка связанной с ним.
Поскольку мы используем функцию для выполнения этой операции, мы хотим иметь возможность изменять переменную 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;
}
Чтобы извлечь переменную, нам нужно отменить это действие:
Вот код:
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;
}
Чтобы удалить конкретный элемент из списка, либо по его индексу от начала списка, либо по его значению, нам нужно будет просмотреть все элементы, постоянно заглядывая вперед, чтобы узнать, достигли ли мы узла до этого элемента. мы хотим удалить. Это потому, что нам нужно изменить местоположение, на которое указывает предыдущий узел.
Вот алгоритм:
Есть несколько крайних случаев, о которых нам нужно позаботиться, поэтому убедитесь, что вы понимаете код.
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.