c++ - 链表回推操作需要 'back pointer'

Question

我正在尝试找出以下代码来实现链表的 push_back 函数，但我不太确定为什么我们需要 back_ptr->next 和back_ptr 都指向 p。我相信 back_ptr->next 可以只指向 NULL 因为它的工作，实现它有什么好处吗？

void LinkedList::push_back(int element) {
    Node *p = new Node;
    p->element = elememt;
    p->next = 0;
    if (empty()) {
        front_ptr = back_ptr = p;
    } else {
        back_ptr->next = p;
        back_ptr = p;
    }
}

下面是LinkedList类的原型(prototype)。 back_ptr 用于指向列表的末尾以实现复制构造函数(push_back 使复制列表变得容易得多)。

class LinkedList {
    void push_back(int element);
    // other member functions

    private:
    struct Node {
        Node *next;
        int element;
    };
    Node *front_ptr;
    Node *back_ptr;
};

Answer 1

push_back(1);
push_back(2);
Node *p = new Node;
p->element = 3;
p->next = nullptr;

 front_ptr      back_ptr         p
     ↓             ↓             ↓
┌────┬────┐   ┌────┬────┐   ┌────┬────┐
| #1 |next| → | #2 |next|   | #3 |next| → nullptr
└────┴────┘   └────┴────┘↘  └────┴────┘
                          nullptr

back_ptr->next = p;

 front_ptr      back_ptr         p
     ↓             ↓             ↓
┌────┬────┐   ┌────┬────┐   ┌────┬────┐
| #1 |next| → | #2 |next| → | #3 |next| → nullptr
└────┴────┘   └────┴────┘   └────┴────┘

back_ptr = p;

 front_ptr             back_ptr  p
     ↓                         ↘ ↓
┌────┬────┐   ┌────┬────┐   ┌────┬────┐
| #1 |next| → | #2 |next| → | #3 |next| → nullptr
└────┴────┘   └────┴────┘   └────┴────┘