PrepBro
← Назад к вопросам

Как связать 100 элементов двунаправленного списка?

1.0 Junior🔥 161 комментариев
#Структуры данных и алгоритмы

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI29 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Связывание элементов двунаправленного списка

Двунаправленный связный список (doubly linked list) — это структура данных, где каждый элемент содержит данные и два указателя: на предыдущий и следующий элемент. Вот как связать 100 элементов такого списка.

Структура узла

Сначала определим базовую структуру:

struct Node {
    int data;
    Node* prev;
    Node* next;
    
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

Способ 1: Создание в цикле

Самый простой подход — создать первый узел, затем в цикле добавлять новые элементы в конец списка:

Node* createDoubleLinkedList(int count) {
    if (count <= 0) return nullptr;
    
    Node* head = new Node(1);
    Node* current = head;
    
    for (int i = 2; i <= count; ++i) {
        Node* newNode = new Node(i);
        current->next = newNode;      // Связываем текущий на новый
        newNode->prev = current;       // Связываем новый на текущий
        current = newNode;             // Переходим к новому узлу
    }
    
    return head;
}

Для 100 элементов вызов:

Node* list = createDoubleLinkedList(100);

Способ 2: Использование класса-контейнера

Профессиональный подход — создать класс-обёртку:

class DoubleLinkedList {
private:
    Node* head;
    Node* tail;
    int size;
    
public:
    DoubleLinkedList() : head(nullptr), tail(nullptr), size(0) {}
    
    void appendValue(int val) {
        Node* newNode = new Node(val);
        
        if (head == nullptr) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
        size++;
    }
    
    void createSequence(int count) {
        for (int i = 1; i <= count; ++i) {
            appendValue(i);
        }
    }
    
    Node* getHead() const { return head; }
    int getSize() const { return size; }
};

Использование:

DoubleLinkedList list;
list.createSequence(100);

Способ 3: Круговой двунаправленный список

Если нужен циклический список (последний элемент ссылается на первый):

Node* createCircularDoubleLinkedList(int count) {
    if (count <= 0) return nullptr;
    
    Node* head = new Node(1);
    Node* current = head;
    
    for (int i = 2; i <= count; ++i) {
        Node* newNode = new Node(i);
        current->next = newNode;
        newNode->prev = current;
        current = newNode;
    }
    
    // Замыкаем список в кольцо
    current->next = head;
    head->prev = current;
    
    return head;
}

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

Для проверки, что все 100 элементов связаны корректно:

void printForward(Node* head) {
    Node* current = head;
    int count = 0;
    while (current != nullptr && count < 100) {
        std::cout << current->data << " ";
        current = current->next;
        count++;
    }
    std::cout << std::endl;
}

void printBackward(Node* tail) {
    Node* current = tail;
    int count = 0;
    while (current != nullptr && count < 100) {
        std::cout << current->data << " ";
        current = current->prev;
        count++;
    }
    std::cout << std::endl;
}

Ключевые моменты

  • Два указателя: каждый узел должен иметь указатели на оба соседа
  • Индексация: в цикле от 2 до 100 (первый узел создан отдельно)
  • Проверка nullptr: важно инициализировать prev и next при создании
  • Сложность: создание O(n), навигация O(1) в обе стороны
  • Очистка памяти: не забудьте освободить узлы через delete

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

Как связать 100 элементов двунаправленного списка? | PrepBro