C++で配列からリンクリストを作成する方法を徹底解説

このチュートリアルでは、C++を使って与えられた配列からリンクリスト（連結リスト）を作成する方法を学びます。配列の各要素を順番にノードとして連結していく、データ構造の学習において基本となる重要なテクニックです。

解決の手順

問題を解くための流れは以下の通りです。

• ダミーデータで配列を初期化する

• ノード用の構造体（struct）を定義する

• 配列を反復処理しながら次の操作を行う

  • 要素のデータを持つ新しいノードを作成する

  • 作成したノードをリンクリストに挿入する

• 完成したリンクリストを出力する

コード例

それでは、実際のコードを見ていきましょう。

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   Node* next;
};
struct Node* newNode(int data) {
   Node* node = new Node;
   node->data = data;
   node->next = NULL;
   return node;
}
void insertNewNode(Node** root, int data) {
   Node* node = newNode(data);
   Node* ptr;
   if (*root == NULL) {
      *root = node;
   }
   else {
      ptr = *root;
      while (ptr->next != NULL) {
         ptr = ptr->next;
      }
      ptr->next = node;
   }
}
void printLinkedList(Node* root) {
   while (root != NULL) {
      cout << root->data << " -> ";
      root = root->next;
   }
   cout << "NULL" << endl;
}
Node* createLinkedList(int arr[], int n) {
   Node *root = NULL;
   for (int i = 0; i < n; i++) {
      insertNewNode(&root, arr[i]);
   }
   return root;
}
int main() {
   int arr[] = { 1, 2, 3, 4, 5 }, n = 5;
   Node* root = createLinkedList(arr, n);
   printLinkedList(root);
   return 0;
}

コードのポイント

• newNode関数：新しいノードを動的に確保し、データとポインタを初期化します。

• insertNewNode関数：リストが空の場合は先頭にノードを設定し、空でない場合は末尾まで走査してから新しいノードを連結します。

• printLinkedList関数：先頭からNULLに到達するまで各ノードのデータを順に出力します。

出力結果

上記のコードを実行すると、次のような結果が得られます。

1 -> 2 -> 3 -> 4 -> 5 -> NULL

まとめ

このように、配列の要素を1つずつ取り出してノードを作成し、末尾に挿入していくことで、簡単にリンクリストを構築できます。なお、この実装では毎回末尾まで走査するため計算量はO(n²)になりますが、末尾へのポインタ（tail）を保持しておけばO(n)に改善できます。チュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。