取消引用的双链接列表头为空

Question

我的头指针应该是空的，因为我不希望在创建链接列表时它有任何值。

我知道不能取消对空值的引用，但我只想将它的下一个节点指向新的节点。有人能解释一下我如何指向头部节点指针吗？

void dlist::push_front(int value) {
    node *p = new node();
    node *tempH = head();
    tempH->next = p; //break
    /***********************************************************
    my head pointer is suposed to be null, because I don't want
    it to have any value when I make my linked list.

    I know that you can't dereference something that is null,
    but I just want to point it's next node to something new.
    can someone explane how I could point the head node pointer?
    ************************************************************/
    p->value = value;
    p->next = tempH->next;
    p->prev = tempH;
    p->next->prev = p;
    p->prev->next = p;
}

#pragma once
#include <ostream>

class dlist {
public:
    dlist() {}

    // Implement the destructor, to delete all the nodes
    //~dlist();

    struct node {
        int value;
        node* next;
        node* prev;
    };

    node* head() const { return _head; }
    node* tail() const { return _tail; }
    void push_front(int value);
private:
    node* _head = nullptr;
    node* _tail = nullptr;
};

Answer 1

这里最实用的解决方案就是在头部和尾部使用哨兵节点。或者，只有一个哨兵节点，代表两者。sentinel节点的元素可以保持未初始化状态，您只需要为它们包含的下一个和上一个指针使用这些节点。要测试是否已到达列表的末尾，您需要测试指针是否指向sentinel节点，而不是测试空指针。

如果您希望列表元素较小，或者列表非常大，则可以使用普通节点作为哨兵。你会在空间上浪费一点内存来放置那些不会被使用的元素，但这可能没什么大不了的。如果你真的关心内存效率（比如，你正在写一个库），你可以有这样的东西：

template<typename T> class dlist {

    struct node_header {
        node_header* next;
        node_header* prev;
    };

    struct node : public node_header {
        T element;
    };

    // Convert a node_header pointer to a node pointer
    node* node_from_header(node_header* p) {
        return static_cast<node*>(p);
    }
};

使用这种方法，您的哨兵节点是一个node_header，所有实际的包含元素的节点都是节点s。您的内部算法都在node_headers上工作，直到您需要实际检索节点的元素，此时您可以使用node_from_header（）来检索完整的包含元素的节点。

如果您绝对不想使用sentinel节点，则必须重写代码以直接使用头指针，而不是通过函数检索它，并添加用于处理空头指针的特殊情况代码。这不是一个好的选择。

Answer 2

在列表构造函数中，只需将head指针设置为null。

dlist::dlist() {
  _head = nullptr;
}

此外，如果你最终删除了列表中的最后一项，你还需要将_head=nullptr；

在取消引用之前，请务必检查head是否为null。

 if(_head == nullptr){
     _head = new node(...);
 }

如果要添加到未初始化的列表中，插入函数将负责将第一个节点分配给头部。

如果需要对列表进行排序，则需要考虑在新节点应先于头部节点的情况下头部的变化。