二重リンクリスト

スポンサーリンク
スポンサーリンク
ライフスタイル関連のコンテンツ
お金 | 仕事 | 勉強 | プライベート | 健康 | 心
プログラミング関連のコンテンツ
C言語/C++入門 | Ruby入門 | Python入門 | プログラミング全般

二重リンクリストは、next_ptr（次の要素を指すポインタ）と、もう1つprev_ptr（前の要素を指すポインタ）を持ちます。
シングルリンクリストは、リンクリストに書いたとおりですので、これを改造した二重リンクリストのデータ構造を表すクラスが以下。

スポンサーリンク

class doublelist {
public:
    class doublelist_elem {
    public:
        int data;    // この要素のデータ
    private:
        doublelist_elem *next_ptr;    // 次の要素へのポインタ
        doublelist_elem *prev_ptr;    // 前の要素へのポインタ
 
        friend class doublelist;
    };
 
public:
    doublelist_elem *first_ptr;    // リストの先頭
 
    // 二重リンクリストの初期化。コンストラクタ
    doublelist() {first_ptr = NULL;}
 
    // 要素を追加
    void enter(int item);
};

「doublelist_elem *prev_ptr;」と、前の要素へのポインタが追加されています。
「8, 12, 68」というリンクリストのデータ構造だったとして、ここに32という要素を追加する場合・・・

１．まず、挿入ポイントを現在の先頭要素へと設定し、
２．挿入ポイントを１つずつ次に進め、
３．追加する新しいデータが挿入ポイントより小さくなった箇所が、挿入ポイントの前に新しいデータを追加すべき箇所であると、特定できます。

要素を追加する「void enter(int item);」を定義します。

// 挿入ポイントを特定し挿入
void doublelist::enter(int item) {
    doublelist_elem *insert_ptr;    // この要素の前に挿入する
    
    insert_ptr = first_ptr;            // 挿入ポイントを先頭に設定
    while (true) {
        insert_ptr = insert_ptr->next_ptr;    // 挿入ポイントを1つ次に進める
 
        // リストの終端か
        if (insert_ptr == NULL)
            break;
 
        // 挿入ポイントか?
        if (item <= insert_ptr->data)
            break;
    }
 
    // 新しい要素の追加
    doublelist_elem = *new_ptr;
    new_ptr = new doublelist_elem;
 
    // 新しい要素に次へのポインタ設定
    new_ptr->next_ptr = insert_ptr;
 
    // 新しい要素に前へのポインタ設定
    new_ptr->prev_ptr = insert_ptr->prev_ptr;
 
    // 新しい要素の1つ前となる要素に、新しい要素をポイントさせる
    insert_ptr->prev_ptr->next_ptr = new_ptr;
 
    // 新しい要素の1つ次となる要素に、新しい要素をポイントさせる
    insert_ptr->prev_ptr = new_ptr;
}

要素を挿入する際には、4つのリンク（ポイント）を設定する必要があります。

スポンサーリンク
スポンサーリンク
 
スポンサーリンク