単一リンクリスト C++ にノードを挿入する

胡金庫 2023年10月12日

C++ C++ Data Structure

リンクリストの最後にノードを挿入する関数を実装する
リンクリスト内の特定のノードの後にノードを挿入する関数を実装する
リンクリストの先頭にノードを挿入する関数を実装する

この記事では、C++ の単一リンクリストに新しいノードを挿入する方法について説明します。

リンクリストの最後にノードを挿入する関数を実装する

リンクリストは、互いに順番に指すノードで構成される線形データ構造です。この記事では、単一リンクリスト構造に焦点を当て、それに応じて複数の挿入操作を実装します。

単一リンクリストには、データオブジェクトとリスト内の次のノードへのポインタがあります。リスト挿入操作をより適切に示すために、ListNode という名前のノード構造と 2つのヘルパー関数（freeNodes と printNodes）を定義しました。挿入操作時間の複雑さは、ノードを挿入する位置によって異なることに注意してください。たとえば、リストの最後が不明な場合、リストの最後への挿入には線形時間がかかります。

一方、最初に新しいノードを挿入するには、常に一定の時間がかかります。次のコードは、リストを作成するためのコア関数として扱うことができる insertNodeEnd 関数を示しています。リストの先頭を最初のパラメーターとして取り、新しいノードに格納する必要のある文字列データを取ります。この関数は、リストの最初の要素を作成し、その最後に新しい要素を追加できます。この関数は、空きストアメモリに新しいノードを割り当てます。したがって、プログラムが終了する前にすべてのメモリを解放するには、freeNodes 関数が必要です。

#include <iostream>
#include <string>
#include <utility>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

struct ListNode {
  struct ListNode *next{};
  string data;
};

struct ListNode *insertNodeEnd(struct ListNode *root, string data) {
  auto new_node = new ListNode;
  if (root) {
    while (root->next) root = root->next;

    new_node->next = nullptr;
    new_node->data = std::move(data);
    root->next = new_node;

    return root->next;
  }
  new_node->next = nullptr;
  new_node->data = std::move(data);
  return new_node;
}

void freeNodes(struct ListNode *root) {
  struct ListNode *tmp = nullptr;
  while (root) {
    tmp = root;
    root = root->next;
    delete tmp;
  }
}

void printNodes(struct ListNode *node) {
  auto count = 0;
  while (node) {
    cout << "node " << count << " - data: " << node->data << endl;
    node = node->next;
    count++;
  }
}

int main() {
  struct ListNode *head = nullptr;

  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  head = insertNodeEnd(head, data_set.at(0));
  for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
    insertNodeEnd(head, *it);
  }
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  insertNodeEnd(head, "Utopic");
  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

出力：

node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
 -----------------------------------
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Utopic

リンクリスト内の特定のノードの後にノードを挿入する関数を実装する

リストの中央にノードを挿入するには、通常、一定の時間に加えて、特定の位置を見つけるために使用される検索アルゴリズムの時間計算量が必要です。ただし、検索関数は個別に実装されていると想定し、insertNodeAfter 関数を作成して、ターゲットノードの位置を最初の引数として指定する必要があるようにします。

insertNodeEnd 関数は新しく追加されたノードへのポインタを返すため、その戻り値を利用して insertNodeAfter の動作を示します。任意の位置を挿入するための個別の検索機能が必要であり、リンクリストでより高速な検索操作を実装するために外部データ構造が必要になる場合もあることに注意してください。

#include <iostream>
#include <string>
#include <utility>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

struct ListNode {
  struct ListNode *next{};
  string data;
};

struct ListNode *insertNodeEnd(struct ListNode *root, string data) {
  auto new_node = new ListNode;
  if (root) {
    while (root->next) root = root->next;

    new_node->next = nullptr;
    new_node->data = std::move(data);
    root->next = new_node;

    return root->next;
  }
  new_node->next = nullptr;
  new_node->data = std::move(data);
  return new_node;
}

struct ListNode *insertNodeAfter(struct ListNode *prev, string data) {
  if (!prev) return nullptr;

  auto new_node = new ListNode;
  new_node->next = nullptr;
  new_node->data = std::move(data);
  prev->next = new_node;
  return new_node;
}

void freeNodes(struct ListNode *root) {
  struct ListNode *tmp = nullptr;
  while (root) {
    tmp = root;
    root = root->next;
    delete tmp;
  }
}

void printNodes(struct ListNode *node) {
  auto count = 0;
  while (node) {
    cout << "node " << count << " - data: " << node->data << endl;
    node = node->next;
    count++;
  }
}

int main() {
  struct ListNode *head = nullptr;

  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  head = insertNodeEnd(head, data_set.at(0));
  for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
    insertNodeEnd(head, *it);
  }
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  auto iter = insertNodeEnd(head, "Utopic");
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  insertNodeAfter(iter, "Xenial");
  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

出力：

node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
 -----------------------------------
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Utopic
 -----------------------------------
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Utopic
node 5 - data: Xenial

リンクリストの先頭にノードを挿入する関数を実装する

単一リンクリストのもう 1つの便利な挿入操作は、最初に新しいノードを追加することです。この関数は、リスト自体にアクセスするためにリストの先頭が常に格納されるため、実行時間が最も長くなります O(1)。insertNodeFront 関数は、ノードに格納する必要のあるルートポインタと string オブジェクトへの参照を取得します。このプロセスは、フロント挿入だけでなく、新しいリンクリストを初期化するために使用できるように実装されています。

または、root 引数が nullptr でない場合に、関数を書き直して新しいノードを割り当てることもできます。それ以外の場合は、nullptr を返して、関数が失敗したことを示します。これらの関数のインターフェースは、プログラマーのニーズと ListNode の構造によって異なります。

#include <iostream>
#include <string>
#include <utility>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

struct ListNode {
  struct ListNode *next{};
  string data;
};

struct ListNode *insertNodeEnd(struct ListNode *root, string data) {
  auto new_node = new ListNode;
  if (root) {
    while (root->next) root = root->next;

    new_node->next = nullptr;
    new_node->data = std::move(data);
    root->next = new_node;

    return root->next;
  }
  new_node->next = nullptr;
  new_node->data = std::move(data);
  return new_node;
}

struct ListNode *insertNodeFront(struct ListNode *&root, string data) {
  auto new_node = new ListNode;
  if (root) {
    new_node->next = root;
    new_node->data = std::move(data);
    root = new_node;
    return root;
  }
  new_node->next = nullptr;
  new_node->data = std::move(data);
  return new_node;
}

void freeNodes(struct ListNode *root) {
  struct ListNode *tmp = nullptr;
  while (root) {
    tmp = root;
    root = root->next;
    delete tmp;
  }
}

void printNodes(struct ListNode *node) {
  auto count = 0;
  while (node) {
    cout << "node " << count << " - data: " << node->data << endl;
    node = node->next;
    count++;
  }
}

int main() {
  struct ListNode *head = nullptr;

  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  head = insertNodeEnd(head, data_set.at(0));
  for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
    insertNodeEnd(head, *it);
  }
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  insertNodeFront(head, "Bionic");
  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

出力：

node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
 -----------------------------------
node 0 - data: Bionic
node 1 - data: Precise
node 2 - data: Quantal
node 3 - data: Saucy
node 4 - data: Raring

著者： 胡金庫

DelftStack.comの創設者です。Jinku はロボティクスと自動車産業で8年以上働いています。自動テスト、リモートサーバーからのデータ収集、耐久テストからのレポート作成が必要となったとき、彼はコーディングスキルを磨きました。彼は電気/電子工学のバックグラウンドを持っていますが、組み込みエレクトロニクス、組み込みプログラミング、フロントエンド/バックエンドプログラミングへの関心を広げています。

LinkedIn Facebook

リンクリストの最後にノードを挿入する関数を実装する

リンクリスト内の特定のノードの後に​​ノードを挿入する関数を実装する

リンクリストの先頭にノードを挿入する関数を実装する

関連記事 - C++ Data Structure

リンクリスト内の特定のノードの後にノードを挿入する関数を実装する