我正在学习数据结构，我用append方法创建了一个链表，如下所示：
#include<iostream>
class List{
public:
using value_type = double;
using reference = value_type&;
using const_reference = value_type const &;
List()
: head_(nullptr)
, tail_(nullptr)
{}
void append(const_reference data){
Node* node = new Node;
node->data = data;
node->next = nullptr;
if(head_ == nullptr){
head_ = node;
return;
}
if(tail_ == nullptr){
tail_ = node;
head_->next = tail_;
return;
}
tail_->next = node;
Node* temporary = tail_;
tail_ = node;
node = temporary;
}
void print(){
Node* temporary = head_;
while(temporary != nullptr){
std::cout << temporary->data << '-';
temporary = temporary->next;
}
}
struct Node{
value_type data;
Node* next;
};
Node* head_;
Node* tail_;
};
int main(){
List list;
list.append(1);
list.append(2);
list.append(3);
list.append(4);
list.print();
return 0;
}但后来阅读到它的来龙去脉时，我发现是这样的：
void Append (Node* head, int data) {
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
Node* new_node = new Node(data);
current->next = new_node;
}我不是一个Maven，我不认为遍历所有节点，只是在最后附加一些东西是有效的，我错了吗？
1条答案
按热度按时间lf5gs5x21#
你的代码可以工作。虽然实现的有点不正统，但它甚至是高效的。因为，它使用尾指针直接在末尾追加一个元素。
所以，很好。
你展示的另一个代码片段适用于 * 没有 * 尾指针的单向链表。是的，对于这个用例来说，这是有点低效。但是，这样的链表也有它的用例，它们在这些用例中表现得很好。在C++标准库中，这样的链表被称为forward_list。
更常用的是
std::list。这是一个双向链接的list。你可以很容易地在两个方向上遍历这样一个列表，这也是它的主要优点。它使用了一个头和尾指针，但不是像你实现的那样。它使用了一个sentinel，也就是一个特殊的节点，它总是存在并包含，也就是说，头和尾指针。所以，你使用的是一个混合型，它只允许向前遍历，你的优化使用尾指针直接访问最后一个元素。但是如果你想在列表中间做一些事情，那么你必须从开始向前遍历它。
因此，带有next和previous指针的节点可能更可取，但这取决于您的用例。
为了便于学习，我在下面给你看一个双向链接表，也许你能从中得到一些想法。