Двойной связанный список, вставьте в позицию - PullRequest
Новая
       9

Двойной связанный список, вставьте в позицию

0 голосов
/ 24 сентября 2018

Я готовлюсь к предстоящим собеседованиям и практикую написание некоторых общих структур данных для практики.Пока что все мои функции работают отлично, за исключением insert_at_position.Когда я пытаюсь вставить в начальный узел значение 1, я получаю два значения для 1, и я не уверен, почему.

Вот полный код: 

#include <iostream>
#include <utility>
#include <memory>

struct Node {
    int data;
    std::unique_ptr<Node> next = nullptr;
    Node* previous = nullptr;

    Node(const int& x, std::unique_ptr<Node>&& p = nullptr, Node* previous = nullptr) :
        data(x),
        next(std::move(p)),
        previous(previous){}
};
std::unique_ptr<Node> head = nullptr;
Node* tail = nullptr;

void print() {
    for (auto loop = head.get(); loop != nullptr; loop = loop-> next.get()) {
        std::cout << loop->data << " ";
    }
    std::cout << "\n";
}

void push_back(const int& theData) {
    std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);
    newNode->previous = tail;

    if (head == nullptr) {
        head = std::move(newNode);
        tail = head.get();
    }

    else {
        tail->next = std::move(newNode);
        tail = tail->next.get();
    }
}

void push_front(const int& theData) {
    head = std::make_unique<Node>(theData, std::move(head), nullptr);

    if (head->next == nullptr) {
        tail = head.get();
    }
}

void insert_at_position(int pos, const int& theData) {
    if (pos == 1) {
        push_front(theData);
        return;
    }

    auto current = head.get();
    std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);

    for (int i = 1; i < pos; i++) {
        current = current->next.get();
    }

    if (current->next != nullptr) {
        newNode->next = std::move(current->next);
        newNode->previous = std::move(current->previous);
        current->next = std::move(newNode);
        current->previous = newNode.get();
    }

    else {
        push_back(theData);
        return;
    }
}

void pop_front() {
    head = std::move(head->next);

    if (!tail) {
        tail = head.get();
    }
}

void pop_back() {
    if (!head) return;

    auto current = head.get();
    Node* prev = nullptr;

    while (current->next != nullptr) {
        prev = current;
        current = current->next.get();
    }
    tail = prev;
    prev->next = nullptr;
}

void erase(int pos) {
    if (pos == 1) {
        pop_front();
        return;
    }

    auto current = head.get();
    Node* previous = nullptr;

    for (int i = 1; i < pos; i++) {
        previous = current;
        current = current->next.get();
    }
    previous->next = std::move(current->next);
}





int main() {

    push_back(2);
    push_back(4);
    push_back(6);
    print();

    push_front(1);
    print();

    pop_front();
    print();

    pop_back();
    print();

    insert_at_position(1, 1);
    print();

    insert_at_position(4, 8);
    print();

    insert_at_position(2, 3);
    print();

    erase(1);
    print();

    erase(2);
    print();

    std::cin.get();

}

В частности, эта строка вmain: insert_at_position(1, 1); дает мне 1 1 2 4, когда должно быть просто 1 2 4

...