Двусвязный список — это тип связанного списка, в котором каждый узел имеет ссылки как на следующий узел, так и на предыдущий узел. Это позволяет эффективно выполнять операции вставки и удаления, а также обход списка в обоих направлениях (т. е. вперед и назад).
В двусвязном списке каждый узел обычно имеет два поля: data и next, в которых хранится значение узла и ссылка на следующий узел в списке соответственно. В дополнение к этим двум полям каждый узел в двусвязном списке также имеет другое поле с именем prev, в котором хранится ссылка на предыдущий узел в списке.
Вот пример узла двусвязного списка в C:
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
Чтобы создать двусвязный список, нам сначала нужно создать структуру Node и выделить для нее память с помощью функции malloc. Затем мы можем присвоить значения полям data, next и prev структуры Node.
Вот пример создания двусвязного списка и вставки в него некоторых узлов:
struct Node* head = NULL; struct Node* second = NULL; struct Node* third = NULL; // allocate memory for the nodes head = (struct Node*)malloc(sizeof(struct Node)); second = (struct Node*)malloc(sizeof(struct Node)); third = (struct Node*)malloc(sizeof(struct Node)); // set the data for the nodes head->data = 1; second->data = 2; third->data = 3; // set the next and prev pointers for the nodes head->next = second; head->prev = NULL; second->next = third; second->prev = head; third->next = NULL; third->prev = second;
В приведенном выше примере мы создали три узла и присвоили значения их data полям. Мы также устанавливаем указатели next и prev для каждого узла, связывая их вместе, чтобы сформировать двусвязный список. Узел head указывает на второй узел, который, в свою очередь, указывает на третий узел, образуя цепочку узлов. Указатели prev для каждого узла указывают на предыдущий узел в списке, что позволяет нам перемещаться по списку в обоих направлениях.
Чтобы пройти по двусвязному списку, мы можем начать с узла head и следовать указателям next, пока не достигнем конца списка. Мы также можем начать с последнего узла и следовать указателям prev, чтобы пройти по списку в обратном направлении.
Вот пример обхода двусвязного списка в обоих направлениях:
// traversing the list forwards
struct Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
// traversing the list backwards
current = third;
while (current != NULL) {
printf("%d ", current->data);
current = current->prev;
}
В приведенном выше примере мы начинаем с узла head и перемещаемся по списку вперед, следуя указателям next. По мере продвижения мы печатаем поле data каждого узла. Затем мы начинаем с узла third и перемещаемся по списку в обратном направлении, следуя указателям prev.
