Узел похож на подставку для напитков. А теперь представьте себе целую кучу этих подставок, разбросанных по столу:
Вы можете соединить их, используя, скажем, кусочки веревки и липких лент. лента.
Я не показываю обратные ссылки, которые были бы у вас в двусвязном списке, поскольку они добавляют беспорядок. Последующее обсуждение является общим как для односвязных, так и для двусвязных списков.
Очевидно, что все подставки (узлы) могут быть отключены и полностью изолированы, или могут быть связаны с «предшественником» и «преемником» - но такие обозначения совершенно произвольны. Если у вас 10 подставок, они могут формировать один связанный список, если все они связаны в «линию», или они могут формировать 10 связанных списков, если они не связаны, или они могут формировать любое другое количество связанных списков от 10 до 1. - это просто зависит от того, сколько подключено или нет.
Процесс объединения / конкатенации / разделения связанных списков - это просто программный c эквивалент добавления кусков строки для соединения подставок.
Основное различие между подставками в таблице и узлами связанного списка в C состоит в том, что типичные примеры не предоставляют «таблицу»: нет общего места, где все узлы связанного списка доступны для проверки. С подставками у нас есть воображаемый стол, на котором они опираются (здесь: стол - это предмет мебели, а не способ организации информации на странице).
Таким образом, вы, вероятно, попали в связанные списки и их узлы - вид больше похож на нижеприведенный: уродливая зеленая скатерть покрывает большинство узлов. Мы почти видим двух из них, торчащих снизу.
«Стол» определенно помогает визуализировать вещи - без скатерти. Общий код C, используемый для «обучения» связанных списков, выглядит точно так же, как эта уродливая зеленая скатерть:
#include <stdlib.h>
typedef struct Node { struct Node *prev, *next; } Node;
Node *appendNode(Node *prev) {
Node *newNode = calloc(1, sizeof(Node));
prev->next = newNode;
newNode->prev = prev;
return newNode;
}
int main()
{
Node *first = appendNode(NULL);
Node *last = first;
last = appendNode(last);
last = appendNode(last);
}
На данный момент мы «видим» только первый и последний узел в списке: это именно они которые «торчат» из-под скатерти. Я сделал скатерть немного прозрачной, но у нас действительно нет четкой «ручки» на среднем (втором) узле. Мы знаем, что он там, мы можем представить, что он там, но он доступен только по ссылкам с других узлов:
Конечно, это просто способ плохо преподавать предмет. Скатерть не нужна. Вы можете создать все узлы напрямую, без какого-либо динамического c выделения. Здесь мы создаем три узла без каких-либо ссылок:
#include <stdlib.h>
typedef struct Node { struct Node *prev, *next; } Node;
int main()
{
Node node1 = {}, node2 = {}, node3 = {};
}
Цель инициализации (= {}) такая же, как и цель динамического выделения узлов с использованием calloc, а не malloc: последнее, что нам нужно, это неинициализированные указатели. calloc инициализирует память нулевым значением, поэтому указатели в динамически выделяемых узлах имеют значение NULL. Инициализация вручную через = {} делает то же самое. Нет, внутри подтяжек ничего не нужно. Вы можете написать = {NULL, NULL}, но в этом нет необходимости. Язык C определен так, чтобы просто инициализировать все нулями, если в списке инициализации не указаны значения.
В противном случае было бы довольно легко забыть инициализировать указатели, и такие ошибки могут быть трудно отследить без надлежащих инструментов, которым никто не мешает преподавать во вводном материале. Если бы вы использовали, например, Asan (Address Sanitizer), разыменование неинициализированного указателя было бы немедленно обнаружено. Но держу пари, что никто не сказал вам об Asan, даже если он бесплатный и не сложный в использовании, поэтому мы должны отказаться от защитного программирования. Это всегда лучше, чем поиск ошибок.
Теперь, когда мы ясно видим три узла, мы можем их соединить:
#include <stdlib.h>
typedef struct Node { struct Node *prev, *next; } Node;
void connect(Node *from, Node *to)
{
from->next = to;
to->prev = from;
}
int main()
{
Node node1 = {}, node2 = {}, node3 = {};
connect(&node1, &node2);
connect(&node2, &node3);
}
Как видите, легко получить любое количество связанных Списки: если у вас есть три узла без каких-либо подключений, они образуют три очень одиноких связанных списка, каждый из которых содержит всего один элемент. Но когда вы соединяете их вместе, вы получаете единый связанный список, даже если существует такое же количество узлов.
Теперь вы можете добавить несколько дополнительных узлов в их собственный список:
#include <assert.h>
#include <stdlib.h>
typedef struct Node { struct Node *prev, *next; } Node;
void connect(Node *from, Node *to)
{
from->next = to;
to->prev = from;
}
int main()
{
Node node1 = {}, node2 = {}, node3 = {};
connect(&node1, &node2);
connect(&node2, &node3);
// Create a second list
Node node4 = {}, node5 = {};
connect(&node4, &node5);
На данный момент связанные списки выглядят следующим образом:
Предположим, мы теперь хотим «соединить» эту секунду между 2-м и 3-м узлами:
// Splice the new list between node2 and node3
connect(&node2, &node4);
connect(&node5, &node3);
// Verify that the spliced list has the shape we expect:
Node *const expected[] = {&node1, &node2, &node4, &node5, &node3, NULL};
for (Node *toCheck = &node1, **stencil = expected; ;)
{
assert(toCheck == *stencil);
if (!*stencil) break;
toCheck = toCheck->next;
++stencil;
}
}
И теперь это должно быть очень ясно, как в программе могут существовать несколько связанных списков. Было бы очень легко преобразовать этот односвязный список в 5 отдельных:
#include <assert.h>
#include <stdlib.h>
typedef struct Node { struct Node *prev, *next; } Node;
void connect(Node *from, Node *to)
{
from->next = to;
to->prev = from;
}
void unlink(Node *node)
{
node->prev = node->next = NULL;
}
int main()
{
Node node1 = {}, node2 = {}, node3 = {};
connect(&node1, &node2);
connect(&node2, &node3);
// Create a second list
Node node4 = {}, node5 = {};
connect(&node4, &node5);
// Splice the new list between node2 and node3
connect(&node2, &node4);
connect(&node5, &node3);
// Separate all the nodes
unlink(&node1);
unlink(&node2);
unlink(&node3);
unlink(&node4);
unlink(&node5);
// Verify that the nodes have no links
Node *const toCheck[] = {&node1, &node2, &node3, &node4, &node5, NULL};
for (Node *const *node = *toCheck; *node; ++node)
{
assert(!(*node)->prev); // idiomatic way of writing (*node->prev == NULL)
assert(!(*node)->next); // ditto
}
}
Теперь вы спросите: но, эй, все это хорошо, но что, если мы хотим иметь произвольное количество узлов? Не обязательно 5, но, скажем, 500? Что тогда? Должны ли мы написать 500 Node объявлений переменных?
Ну, вы могли бы просто иметь массив:
Node nodes[500];
Но это не очень гибко. Обычно вам нужен своего рода «дескриптор» списка - способ «захватить» конечные узлы в списке.
Конечно, это требует нового типа данных:
typedef struct List { Node *first, *last } List;
Теперь мы можем написать несколько функций, которые работают с таким «дескриптором»:
#include <assert.h>
#include <stdlib.h>
typedef struct Node { struct Node *prev, *next; } Node;
void connect(Node *from, Node *to)
{
from->next = to;
to->prev = from;
}
void unlink(Node *node)
{
node->prev = node->next = NULL;
}
typedef struct List { Node *first, *last; } List;
Node *appendNode(List *list) {
Node *node = calloc(1, sizeof(Node));
if (list->last)
connect(list->last, node);
else {
// the list is empty - there's no last node, and neither can there be a first one
assert(!list->first);
list->first = node;
}
list->last = node;
return node;
}
Node *prependNode(List *list) {
Node *node = calloc(1, sizeof(Node));
if (list->first)
connect(node, list->first);
else {
// the list is empty - there's no first node, and neither can there be a last one
assert(!list->last);
list->last= node;
}
list->first = node;
return node;
}
Отлично - теперь мы можем создать два списка:
int main()
{
List list1 = {};
appendNode(&list1);
appendNode(&list1);
appendNode(&list1);
List list2 = {};
appendNode(&list2);
appendNode(&list2);
На этом этапе мы разделили списки:
И теперь мы можем объединить их вместе:
// Splice the new list between second and third node in list1
Node *node2 = list1.last->prev;
Node *node4 = list2.first;
connect(node2, node4);
Node *node5 = list2.last;
Node *node3 = list1.last;
connect(node5, node3);
// Verify that the spliced list has the shape we expect:
Node *const expected[] = {list1.first, node2, node4, node5, node3, NULL};
for (Node *toCheck = list1.first, **stencil = expected; ;)
{
assert(toCheck == *stencil);
if (!*stencil) break;
toCheck = toCheck->next;
++stencil;
}
}
Конечно, на данный момент дескриптор list2 полезен только наполовину: он не представляет собой отдельный список. Если бы мы хотели быть точными, мы могли бы сказать, что следующие два инварианта применяются к «правильным» дескрипторам списков:
void checkHandle(const List *list)
{
assert(!list->first == !list->last);
// The list handle must either have no first and last element, or both (they may
// be equal - we don't check that here.
assert(!list->first || !list->first->prev);
// Either the list has no first element, or the first element has no predecessor.
assert(!list->last || !list->last->next);
// Either the list has no last element, or the last element has no successor.
}
В свете таких инвариантов нам нужно немедленно отсоединить list2 дескриптор элементов, так как они теперь являются частью другого списка:
// after verifying that the spliced list has the expected shape
list2->first = list2->last = NULL;
}
