Вставка в конце двусвязного списка

Question

Вставка в конце двусвязного списка

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

void LinkedList::insertAtTail(const value_type& entry) {
Node *newNode = new Node(entry, NULL, tail);
tail->next = newNode;
tail = newNode;
++node_count;
}

Класс Node принимает значение, которое будет сохранено, значение для следующего указателя, на которое нужно указать, и значение для предыдущего указателя в этом порядке. Всякий раз, когда я пытаюсь вставить сюда узел, я получаю сообщение об ошибке, в котором говорится о необработанном исключении и нарушении доступа при записи в местоположение 0x00000008.

Я не совсем уверен, что здесь происходит, но я предполагаю, что это как-то связано с разыменованием нулевого указателя на основе сообщения об ошибке. Буду очень признателен за помощь в решении этой проблемы.

РЕДАКТИРОВАТЬ:

Я должен был уточнить рано, хвост является указателем, который указывает на последний узел в списке. Tail-> next обращается к следующей переменной этого последнего узла, которая перед выполнением функции указывает на NULL, но после ее выполнения должна указывать на созданный новый узел.

1

c++doubly-linked-list linked-list nodes

Решение

Другие решения

Предполагая, что ваш LinkedList имеет как голову, так и хвост, возможно, попробуйте:

void LinkedList::insertAtTail(const value_type& entry)
{
Node *newNode = new Node(entry, NULL, tail);
if (tail)
tail->next = newNode;
tail = newNode;
if (!head)
head = newNode;
++node_count;
}

Просто выстрел в темноте

1

Трудно сказать, что является причиной ошибки, не зная состояния списка до операция вставки (которая на самом деле присоединять а не вставлять, кстати).

Есть большая вероятность, что вы не разберетесь с первоначальным случаем добавления в пустой список. Основной алгоритм (пустой список обозначается нулевым указателем заголовка, все остальное не определено):

def append (entry):
# Common stuff no matter the current list state.

node = new Node()
node->payload = entry
node->next = NULL

# Make first entry in empty list.

if head = NULL:
node->prev = NULL
head = node
tail = node
return

# Otherwise, we are appending to existing list.

next->prev = tail
tail->next = node
tail = node

1

Источник

Accepted Answer

Где же tail указать изначально? Если он равен NULL, вы будете разыменовывать нулевой указатель при попытке вставить первый элемент.

Это поможет, если вы тестируете tail перед разыменованием это?

void LinkedList::insertAtTail(const value_type& entry) {
Node *newNode = new Node(entry, NULL, tail);
if (tail)
tail->next = newNode;
tail = newNode;
++node_count;
}

Если tail является нулевым и offsetof(Node, next) 8, что объясняет нарушение доступа, потому что tail->next будет по адресу 0x00000000 + 8, который является 0x00000008, поэтому назначение tail->next попытался бы записать в память по этому адресу, что является именно той ошибкой, которую вы видите.

8