模板中的C++双重链接列表

Question

ListNode代码：

template <typename T>
struct ListNode {
public:
T data;
ListNode *prev, *next;
ListNode() {
prev = nullptr;
next = nullptr;
}
ListNode(T Data, ListNode *Prev, ListNode *Next) {
data = Data;
prev = Prev;
next = Next;
}
};

双重链接列表代码：

#include <iostream>
#include <stdexcept>
using namespace std;
template <typename T>
class List {
protected:
ListNode<T> *head, *tail;
public:
List<T>() {
head = NULL;
tail = NULL;
}
~List<T>() {
while (head != NULL) {
pop_front();
}
}
bool empty() const {
if (head == NULL)
return true;
else
return false;
}
void push_front(T data) {
if (head != NULL) {
head = new ListNode<T>(data, NULL, head);
head -> next -> prev = head;
}
else {
head = new ListNode<T>(data, NULL, NULL);
tail = head; 
}       
}
void push_back(T data) {
if (tail != NULL) {
tail = new ListNode<T>(data, tail, NULL);
tail -> prev -> next = tail;
}
else {
tail = new ListNode<T>(data, NULL, NULL);   
head = tail;
}  
}
void pop_front() {
if (head != NULL) {
ListNode<T> *temp = head;
head = head -> next;
delete temp;
}
else
throw out_of_range("This list is empty.");
}
void pop_back() {
if (tail != NULL) {
ListNode<T> *temp = tail;
tail = tail -> prev;
delete temp;
}
else
throw out_of_range("This list is empty.");
}
friend std::ostream& operator << (std::ostream& out, const List<T>& list) {
out << list.head -> data;
ListNode<T> *temp = list.head -> next;
while (temp != NULL) {
out <<  ", " << temp -> data;
temp = temp -> next;
}
return out; 
} 
};

Doubly LinkedList需要执行push_front、push_back、pop_front，pop_back、pop_front和pop_back以及bool-empty。

outstream需要使用"分离数据

我把它发给了在线评委，但我收到了运行时错误。

我不知道这个代码有什么错。

如何使其正确？

感谢大家的帮助。

Answer 1

您的问题出现在pop_back()函数中。

void pop_back() {
if (tail != NULL) {
ListNode<T> *temp = tail;
tail = tail -> prev;
delete temp;
}
else
throw out_of_range("This list is empty.");
}

你将尾部设置为新的尾部，但你忘记将新的tail->next更新为nullptr，所以它仍然指向你在delete temp;行中释放的old尾部，你所需要做的就是在ListNode<T> *temp = tail;之后添加这行tail->prev->next = nullptr;。

所以它看起来是这样的：

void pop_back() {
if (tail != NULL) {
ListNode<T> * temp = tail;
tail->prev->next = nullptr;
tail = tail->prev;
delete temp;
}
else
throw out_of_range("This list is empty.");
}
also as a

请注意，如果您使用的是c++11及以上版本，您可以使用auto关键字，它会将ListNode<T>保存为auto*。您也可以保留*并使用auto，但我认为添加*更可读，因此很明显它是一个指针。