ポインタについて質問です。

Question

aizu online judgeにて双方向連結リストの他の方の回答をみて疑問があります。

#include<stdio.h>
#include <iostream>
#include <string.h>
#include <cstdlib>

using namespace std;

struct Node{
    int data;
    Node* prev;
    Node* next;
};

class ConnectedList{
public:
    ConnectedList(){
        motherNode = new Node();
        motherNode->data = -1;
        motherNode->prev = motherNode;
        motherNode->next = motherNode;
    };
    ~ConnectedList(){
        Node* tmpNode = motherNode->next;
        Node* nextNode;
        while(tmpNode != motherNode){
            nextNode = tmpNode->next;
            delete tmpNode;
            tmpNode = nextNode;
        }
        delete motherNode;
    };
    void insertNode(int x){
        Node* tmpNode = motherNode->next;
        motherNode->next = new Node();
        motherNode->next->data = x;
        motherNode->next->next = tmpNode;
        motherNode->next->prev = motherNode;
        tmpNode->prev = motherNode->next;
    };
    void deleteNode(int x){
        Node* tmpNode = motherNode->next;
        while(tmpNode != motherNode && tmpNode->data != x){
            tmpNode = tmpNode->next;
        }
        if(tmpNode != motherNode){
            tmpNode->prev->next = tmpNode->next;
            tmpNode->next->prev = tmpNode->prev;
            delete tmpNode;
        }
    };

    void deleteFirst(){
        Node* tmpNode = motherNode->next;
        motherNode->next = motherNode->next->next;
        motherNode->next->prev = motherNode;
        delete tmpNode;
    };

    void deleteLast(){
        Node* tmpNode = motherNode->prev;
        motherNode->prev = motherNode->prev->prev;
        motherNode->prev->next = motherNode;
        delete tmpNode;
    };

    void showList(){
        Node* tmpNode = motherNode->next;
        printf("%d",tmpNode->data);
        tmpNode = tmpNode->next;
        while(tmpNode != motherNode){
            printf(" %d",tmpNode->data);
            tmpNode = tmpNode->next;
        }
        printf("\n");
    }

private:
    Node* motherNode;
};

deleteLastをする時、motherNode->prev = motherNode->prev->prevで削除してますが、insertNodeした時のどこの箇所でmotherNode->prevにアドレスが入ったのでしょうか？
よろしくお願い致します。

Comments

[y_waiwai]

> 初回はなぜtmpNode->prevとmotherNode->prevのアドレスが同じなのでしょうか？
そういう記述はないようですが

Answer 1

これは実装上双方向循環リストになってますね。
初期状態ではmotherNodeのnext, prev共にmotherNode, 1個Insertで2Node間で循環,以降同様です。
1個目のNodeの追加時にtmpNodeがmotherNodeなのでmotherNode->prevが追加されたNodeになっています。

ところでこれ、問題は知らないですがInsertが頭にしかできない仕様ですね…

Comments

[退会済みユーザー]

あとこれ、deleteNodeは対策してるけどdeleteFirstとLastでmotherNodeがdeleteされる可能性ありますね…
出題上問題ないのかもしれませんが。

Answer 2

...<->[1]<->[2]<->...

[1]と[2]の間に[0]を挿入する場合

Node* tmpNode = motherNode->next;   // tmpNode = [2]
motherNode->next = new Node();      // [1]->[]
motherNode->next->data = x;         // [1]->[0]
motherNode->next->next = tmpNode;   // [1]->[0]->[2]
motherNode->next->prev = motherNode;// [1]<->[0]->[2]
tmpNode->prev = motherNode->next;   // [1]<->[0]<->[2]