ダブルリンクリストの逆参照はnullです

Question

私のリンク先リストを作成するときに、 に値を持たせたくないので、私のヘッドポインタはnullになっているはずです。

ヌルであるものを参照解除することはできませんが、 ですが、次のノードで新しいものを指し示したいと思います。 ヘッドノードポインタをどのように指すことができるか説明できる人はいますか？あなたのリストのコンストラクタで

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

、単にヌルへのヘッドポインタを設定します。あなたは、リストの最後の項目を削除してしまう場合

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

さらに、あなたも_head = nullptrを行う必要があります。

逆参照する前に頭がヌルかどうかを必ず確認してください。

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

あなたの挿入機能を使用すると、初期化されていないリストに追加している場合には、頭に最初のノードを割り当てるための責任を負うことになります。

リストをソートする必要がある場合は、新しいノードがヘッドノードの前にある場合にヘッドを変更する必要があります。

Answer 2

最も実用的な解決策は、頭と尾にセンチネルノードを使用することです。または、ただ一つのセンチネル節、それは両方のために立つ。センチネルノードの要素は初期化されずに残すことができます。それらのノードには、それらに含まれる次のポインタと前のポインタのためのノードだけが必要です。リストの終わりに達したかどうかをテストするために、ヌルポインタをテストする代わりに、ポインタがセンチネルノードを指しているかどうかをテストします。

リスト要素を小さくするか、リストを非常に大きくする必要がある場合は、通常のノードをセンチネルとして使用できます。あなたは使用されない要素のためにスペース上に少しのメモリを無駄にしますが、それはおそらく大きな問題ではありません。あなたが本当に（たとえば、あなたがライブラリを書いている）メモリ効率を気にしている場合、あなたはこのような何か持つことができます。このアプローチでは

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、すべて実際、元素含有でありますノードはnodeです。ノードの要素を実際に取得する必要があるまで、内部アルゴリズムはすべてnode_headerで動作します。その時点で、node_from_header()を使用して完全な要素を含むノードを取得します。

センチネルノードを絶対に使用したくない場合は、関数を使用してヘッドポインタを直接検索するのではなく、nullヘッドポインタを処理するための特別なコードを追加する必要があります。それはかなりの選択肢ではありません。