HOWTO · C++
C++ でのリンクリストのコンストラクターのコピー
C++ を使用したリンクリストデータ構造でのコピーコンストラクタの使用に関する簡単なプログラミングチュートリアル。
この簡単な記事は、ディープコピーコンストラクターを持つリンクリストの C++ ベースの実装に関するものです。
C++ でコンストラクタをコピーする
同じクラスの別のオブジェクトを使用してオブジェクトを初期化するために、コピーコンストラクターが呼び出されます。コピーコンストラクタは、次のような複数の状況で呼び出されます。
- オブジェクトが別のオブジェクトを使用してコピーされた場合。
- オブジェクトが関数から値として返される場合。
- オブジェクトが値として関数に渡されるとき。
すべてのクラスには、常にデフォルトのコピーコンストラクターがありますが、ディープコピーは実行せず、シャローコピーを実行します。ポインタのアドレスのみがシャローコピーでコピーされ、両方のオブジェクト（つまり、呼び出し元と渡されたオブジェクト）が同じメモリを指します。
逆に、ディープコピーでは、データメンバーの値が宛先オブジェクトのデータメンバーにコピーされます。
C++ のリンクリスト
リンクリストのデータ構造は、動的に拡張できるデータノードの形式でデータを格納します。連続したメモリを必要としないため、メモリ内のどこにでも効率的に保存できます。
C++ でのリンクリストの実装
リンクリストの実装を始めましょう。まず、データノードを取得するためのクラスを作成する必要があります。
template <class T>
class Node {
public:
T info;
Node<T>* next;
Node() { next = 0; }
Node(T val) {
info = val;
next = 0;
}
};
Node クラスには 2つのメンバーがあります。1つはデータ（つまり、info）を格納するためのもので、もう 1つは次のノードのアドレスを格納するためのクラス自体へのポインタです。クラスはテンプレート化されているため、任意のデータ型のリストを作成できます。
上記の実装は 2つのコンストラクターを提供します。1つはデフォルトのコンストラクターで、もう 1つはパラメーター化されています。
リンクリストのテンプレートクラスを見てみましょう。
template <class T>
class LSLL {
private:
Node<T>* head;
public:
LSLL() { head = 0; }
};
クラス LSLL には、リンクリストの最初のノードのアドレスを保持するために使用される Node クラスへのポインタが 1つだけあります。
あるリンクリストオブジェクトを別のオブジェクトに深くコピーする機能をユーザーに提供するには、以下に示すように、ユーザー定義のコピーコンストラクター実装を提供する必要があります。
LSLL(LSLL& PassedObj) {
if (PassedObj.head == NULL) {
head = NULL;
} else {
// copy all nodes of PassedObj to the caller object
// attach first node to the head of the caller object
Node<T>* newNode = new Node<T>();
newNode->info = PassedObj.head->info;
newNode->next = NULL;
head = newNode;
// Now deep-copy all the remaining nodes of the Passed linked list object
Node<T>* PassedItr = PassedObj.head->next;
Node<T>* CallerItr = head;
while (PassedItr != NULL) {
CallerItr->next = new Node<T>();
CallerItr->next->info = PassedItr->info;
CallerItr->next->next = NULL;
CallerItr = CallerItr->next; // move to newly added node
PassedItr = PassedItr->next; // move one node further
}
}
}
上記のコードセグメントは、渡されたオブジェクトの最初のノードのディープコピーを作成し、それを呼び出し元リストオブジェクトのヘッドにアタッチします。その後、渡されたオブジェクトの残りのすべてのノードが深くコピーされ、呼び出し元のリンクリストノードにアタッチされます。
実装全体の認知的見解を持ってみましょう：
#include <iostream>
using namespace std;
template <class T>
class Node {
public:
T info;
Node<T>* next;
Node() { next = NULL; }
Node(T val) {
info = val;
next = NULL;
}
};
template <class T>
class LSLL {
private:
Node<T>* head;
public:
LSLL() { head = NULL; }
LSLL(LSLL& PassedObj) {
if (PassedObj.head == NULL) {
head = NULL;
} else {
// copy all nodes of PassedObj to the caller object
// attach first node to the head of the caller object
Node<T>* newNode = new Node<T>();
newNode->info = PassedObj.head->info;
newNode->next = NULL;
head = newNode;
// Now deep-copy all the remaining nodes of the Passed linked list object
Node<T>* PassedItr = PassedObj.head->next;
Node<T>* CallerItr = head;
while (PassedItr != NULL) {
CallerItr->next = new Node<T>();
CallerItr->next->info = PassedItr->info;
CallerItr->next->next = NULL;
CallerItr = CallerItr->next; // move to newly added node
PassedItr = PassedItr->next; // move one node further
}
}
}
void insertAtHead(T val) {
Node<T>* x = new Node<T>(val);
x->next = head;
head = x;
}
void displayAll() {
Node<T>* x = head;
{
while (x != 0) {
cout << x->info << endl;
x = x->next;
}
}
}
int isEmpty() {
if (head == 0) return 1;
return 0;
}
void insetAtTail(T val) {
Node<T>* x = head;
if (isEmpty()) {
insertAtHead(val);
return;
}
while (x->next != 0) {
x = x->next;
}
x->next = new Node<T>(val);
}
void insertAfter(T key, T val) {
if (isEmpty()) return;
Node<T>* x = head;
while (x != 0 && x->info == key) x = x->next;
if (!x) return;
Node<T>* temp = new Node<T>(val);
temp->next = x->next;
x->next = x;
}
};
int main() {
LSLL<int> list;
list.insertAtHead(200);
list.insertAtHead(100);
list.insetAtTail(300);
list.displayAll();
LSLL<int> list2(list);
cout << "List2: " << endl;
list2.displayAll();
return 0;
}
メインドライバーコードは、最初に list オブジェクトを作成し、それに 3つのノードを挿入して、displayAll 関数を呼び出します。その後、新しいリンクリストオブジェクト list2 を作成し、引数として list を使用してパラメーター化されたコピーコンストラクターを呼び出します。
list2 オブジェクトは呼び出し元オブジェクトであり、list は渡されたオブジェクトであることに注意してください。
出力：
100
200
300
List2:
100
200
300
