HOWTO · C++
C++ でリンクリストを並べ替える
このプログラミングチュートリアルでは、C++ のリンクリストデータ構造での並べ替え操作の実装について説明します。
このページの内容
単方向リンクリストを昇順に並べ替えるには、隣り合う値を比較し、順序が逆になっている値を交換します。リンクはそのまま保つため、この方法ではノードをつなぎ直すのではなく、ノードが保持する値を並べ替えます。以下の実装ではバブルソートを使い、実行に必要なドライバーも含めています。
単方向リンクリストが保持するもの
単方向リンクリストは、ノードが連なった構造です。各ノードは1つの値と次のノードへのポインターを保持し、最後のノードのポインターは nullptr を指します。リストの head ポインターは先頭ノードを示します。配列とは異なり、ノードがメモリ上で連続して配置されている必要はありません。目的のノードへ進むには、head から始めて next ポインターを順にたどります。
この構造では先頭への挿入は定数時間で行えますが、後方の位置を探すにはリストをたどる必要があります。そのため、並べ替えでもリンクをたどってノードを訪れます。このコードではリストをテンプレートにしているため、ソートで使う比較と値の交換に対応する型であれば、さまざまな型を格納できます。
C++で最小限の単方向リンクリストを作る
各ノードは値とリンクをまとめて初期化します。リストはノードを所有し、デストラクターで解放します。また、コピーを無効にして、2つのリストが同じノードを誤って削除するのを防ぎます。insertAtHead は現在の先頭より前に値を追加し、displayAll はリストをたどる順に値を表示します。
リンクリストを昇順に並べ替える
バブルソートでは、隣り合う値の組を順に調べていきます。現在の値が次の値より大きい場合は、std::swap で2つの値を交換します。1回の走査が終わると、まだ位置が確定していない値のうち最大のものが右端へ移動しています。last はその境界を示し、次の走査では確定済みの末尾部分を飛ばします。交換が一度も起きなかったら終了します。空のリストではすぐに戻り、ノードが1つだけのリストでは比較は不要です。
最悪時の時間計算量は O(n²)、追加領域は O(1) です。ノード間のリンクは保たれ、各ノードが保持する値が変わります。T は operator> による比較と値の交換に対応している必要があります。この実装はノードをつなぎ直して並べ替えるものではありません。
例をコンパイルして実行する
このプログラム全体を sort.cpp として保存します。ドライバーは 50、16、45 を先頭に挿入するため、ソート前にリストをたどると 45、16、50 の順に表示されます。その後、昇順に並べ替えて結果を表示します。コード内の表示ラベルと出力例は、バイト単位の一致要件に従って英語のままです。
#include <iostream>
#include <utility>
template <class T>
struct Node {
T data;
Node<T>* next;
explicit Node(const T& value) : data(value), next(nullptr) {}
};
template <class T>
class SinglyLinkedList {
private:
Node<T>* head;
public:
SinglyLinkedList() : head(nullptr) {}
SinglyLinkedList(const SinglyLinkedList&) = delete;
SinglyLinkedList& operator=(const SinglyLinkedList&) = delete;
~SinglyLinkedList() {
while (head != nullptr) {
Node<T>* next = head->next;
delete head;
head = next;
}
}
void insertAtHead(const T& value) {
Node<T>* node = new Node<T>(value);
node->next = head;
head = node;
}
void displayAll() const {
const Node<T>* current = head;
while (current != nullptr) {
std::cout << current->data << '\n';
current = current->next;
}
}
void sortLinkedList() {
if (head == nullptr) {
return;
}
Node<T>* last = nullptr;
bool swapped;
do {
swapped = false;
Node<T>* current = head;
while (current->next != last) {
if (current->data > current->next->data) {
using std::swap;
swap(current->data, current->next->data);
swapped = true;
}
current = current->next;
}
last = current;
} while (swapped);
}
};
int main() {
SinglyLinkedList<int> list;
list.insertAtHead(50);
list.insertAtHead(16);
list.insertAtHead(45);
std::cout << "Before sorting:\n";
list.displayAll();
list.sortLinkedList();
std::cout << "After sorting:\n";
list.displayAll();
}
確認済みの実行では、次のように表示されます。
Before sorting:
45
16
50
After sorting:
16
45
50
ファイルを置いたディレクトリで、C++11以降に対応したコンパイラーを使ってコンパイルし、実行します。
g++ -std=c++11 -Wall -Wextra -pedantic sort.cpp -o sort
./sort
表示処理は値を1行ずつ出力するため、上記の出力と一致します。
