Невозможно получить доступ к узлу привязки связанного списка

Question

Я пытаюсь реализовать двусвязный список в C ++ и столкнулся с проблемой.

#include <iostream>
#include <string>

struct Node
{
    std::string data;
    Node* prev_link;
    Node* next_link;
    Node(const std::string& data,Node* prev_link=nullptr, Node* next_link=nullptr)
        : data{data},prev_link{prev_link},next_link{next_link} {}// constructor
};

Node* insert(Node* new_node,Node* old_node);// insert node before old node
Node* head(Node* node);// returns a pointer to the head i.e. the left end of the linked list
void print_list(Node* node);//takes the head pointer and executes iterative print
void kill_list(Node* tail_node);// deallocates memory by deleting the list

Node* insert(Node* new_node,Node* old_node)
{
    if(new_node == nullptr) return old_node;
    if(old_node == nullptr) return new_node;
    new_node->next_link = old_node;// p of old node connect to new node
    if(old_node->prev_link) old_node->prev_link->next_link = new_node;//n of old' node connect to new node if old' node exists
    new_node->prev_link = old_node->prev_link;//p of new node connect to old` node
    new_node->next_link = old_node;//n of new node connect to old node
    return new_node;
}

Node* head(Node* node)
{
    while(node->next_link != nullptr) node = node->next_link;
    return node;    
}

void print_list(Node* node)
{
    while(node)
    {
        std::cout << node->data;
        if(node = node->next_link) std::cout << "<->";// if next node is not an end node 
    }

}

void kill_list(Node* tail_node)
{
    Node* temp;
    while (tail_node)
    {
        temp = (tail_node->prev_link)?tail_node->prev_link:tail_node->next_link;
        delete tail_node;
        tail_node = temp;
    }
    std::cout << '\n' <<"List destroyed" << std::endl;
}

int main()
{
    Node* alphabets = new Node("A");
    alphabets = insert(new Node("B"),alphabets);
    alphabets = insert(new Node("C"),alphabets);
    print_list(alphabets);
    std::cout << '\n';
    std::cout << "Head:" << head(alphabets)->data << std::endl;
    std::cout << "Adjacent:" << head(alphabets)->prev_link->data << std::endl;
    kill_list(alphabets);
}

вывод:

C <-> B <-> A

Head: A

fi sh: «./test1» завершается сигналом SIGSEGV (Ошибка границы адреса)

Функция head () возвращает указатель на голову узел (в данном случае это A). Связанный список, а также головной узел напечатаны правильно, но я не могу получить доступ к узлу, смежному с головным узлом. Не могу понять, что я делаю не так. Любая помощь будет оценена.

Answer 1

Ваша ошибка в том, что для соседа A есть нулевой указатель. В вашей функции вставки есть оператор if

if(old_node->prev_link) old_node->prev_link->next_link = new_node

Однако, в случае A, нет prev_link, но вы все равно хотите присвоить B. Поэтому замена на:

old_node->prev_link = new_node;

устраняет проблему. Однако вы можете перепроверить, чтобы это соответствовало вашему желаемому логику c.

Answer 2

Проблема связана с тем, что prev_link не установлен для заголовка (prev ссылка равна нулю для каждого узла), есть ошибка в функции вставки, вы никогда не устанавливали prev_link старого узла.