ポインタを使った連結リストに対する疑問

Question

このようなコードがあって、
for (int i = 1; i < 10; i++) {
p->next = new LinkedList(i);
p = p->next;
}の部分が納得するような納得しないような変な感じがしました。
headポインタと同じところを示すから、一つずつiをあげていけば配列をしますのは分かります。
しかし、p=p->nextの部分がなんだか気持ち悪くて、
ポインタを配列みたいに使うなら、実際に配列にいれたらいいじゃないかと思ってしまいました。
ここの部分を丁寧に説明していただけると、とても助かります。
よろしくお願いします

p->next = new LinkedList(i);
p = p->next;
の部分が具体的にどうなるのか手順を提示してくれると、とても助かります

コード
#include <iostream>

using namespace std;

class LinkedList {
public:
    LinkedList *next;
    int data;
    LinkedList(int data);
    ~LinkedList();
};

LinkedList::LinkedList(int data) {
    this->next = NULL;
    this->data = data;
    cout << "new: " << this->data << ": " << this << endl;
}

LinkedList::~LinkedList() {
    cout << "delete: " << this->data << ": " << this << endl;
}

int main(int argc, char *argv[]) {
    LinkedList *head = new LinkedList(0);
    LinkedList *p = head;
    for (int i = 1; i < 10; i++) {
        p->next = new LinkedList(i);
        p = p->next;
    }
    for (p = head; p != NULL; p = p->next) {
        cout << "p->data=" << p->data << endl;
    }
    for (p = head; p != NULL;) {
        LinkedList *tmp = p->next;
        delete p;
        p = tmp;
    }
    return 0;
}

Answer 1

メリット／デメリットは概ね皆さんの回答の通りですが、もう１つ連結リストを使う重要なメリットとして、追加／削除コストが低いことが上げられます。

配列のような構造の場合、例えば先頭に１つ要素を追加する時、配列に入っている有効な要素を全て１つ後ろへコピーする必要があります。
しかし、連結リストの場合、追加する要素のnextにheadポインタをコピーし、headポインタに追加する要素のアドレスを設定するだけですので、負荷が軽いのです。

先日のサンプルのように順序を気にしないような配列の場合は追加／削除コストは連結リストと大差ないですが、多くの場合順序は重要です。

Answer 2

連結リストのメリット：
・あらかじめ連続した最大領域のメモリを確保する必要が無い。
・必要な分だけメモリを確保して行くため、メモリの許す限りデータの追加が可能。

連結リストのデメリット：
・シーケンシャルアクセスしか出来ないため、使用目的によっては低速。
・リンクのための情報保持のための領域が別途必要で、同数のデータのためのメモリ用息は配列より多く必要になる。

配列のメリット：
・データの位置が計算でもとめることができ、ランダムアクセスが可能で高速。
・データの順番を保持する付加情報が不要。

配列のデメリット：
・あらかじめ最大の連続したメモリ領域を確保する必要がある。
・原則、途中で拡張ができない。

---

p->next = new LinkedList(i);
p = p->next;

今あるレコードの、次のレコードへのポインタ (p->next) に新たなレコードのポインタを格納
その後、最後のレコードを保持するポインタに新たなレコードのポインタ（最終レコードのポインタ）を格納するしています。

Answer 3

日本語が難しいですが、ポインタ配列に入れると要素の最大数に制限がかかるから避けています。連結リストとはそういうものです。
インデックスがなく、前(または双方向であれば後ろ)の要素と連結されているだけです。

とはいえ、この例では10個固定なので配列でも良いですね。
もっと要素が増える可能性があると困ったことになります。
例えばスタックメモリの逼迫などです。
関数の中で宣言した変数はスタックメモリから確保され、newした場合はヒープメモリから確保されます。
この辺りは専門書をご参考ください。

Answer 4

まず、配列を使うなら予め配列の数を指定しなければならない。
p->next = new LinkedList(i);
にてメモリーを取りながらnextでリンクしていけばメモリーの許す最大まで配列が作れる。