解説「リスト構造」について、双方向リストのプログラムを説明します。
要素 | 配列 | 前ポインタ | 後ポインタ |
0 | AAA | 最小 | 3 |
1 | DDD | 3 | 4 |
2 | FFF | 4 | 最大 |
3 | BBB | 0 | 1 |
4 | EEE | 1 | 2 |
右のような双方向のポインタを付けた「リスト構造」を生成します。それに新しい要素の追加や既存要素の削除するときのポインタの変更について考えます。
解説では、配列の添え字は1からになっていますが、Javascriptの仕様では0からになっていますので、一つずつずれています。そのため、最小の要素を0ではなく「最小」とし、最大の要素を「最大」としています。
上のリスト構造のデータを加工します。
命令 機能
insert(+) 追加:要素を追加する。同一値の要素がある場合は発生順にする。
delete(-) 削除:最初に見つかった同一値の要素を削除する(実際には削除せずポインタを「削除」とする)。
上図は、前要素と後要素の間に新要素を挿入するときの、ポインタの変化を示しています。事前は青のポインタになっていますが、新要素が入ることにより、赤のように変更します(逆に新要素を削除するときは、赤のポインタを青のように変更します)。
配列での前要素と後要素の間に新要素を挿入するのではなく、新要素値に関係なく、右図のように配列の末尾に挿入するのです(配列長が1増加します)。そして、事前の青のポインタを赤のように変更することにより順序を示すのです。
これらの図では、最小値要素値<新要素値<最大値要素値 の場合、すなわち、前要素と後要素が存在している場合を示していますが、新要素値<最小値要素値なら前要素は存在しないし、新要素値>最大値要素値なら後要素は存在しません。
また、新要素値は既存要素値と同じ場合もあります。ここでは発生順とし、新要素のほうが大きいとします。
このような場合を考慮すると、追加のアルゴリズムは次のソースコードのようになります。
function 追加(新要素値) { // 配列の末尾に新要素を入れる、配列長を1増加 var 末尾要素 = 配列長; 配列[末尾要素] = 新要素値; 配列長++; // ポインタおよび最小値要素、最大値要素の変更 if (新要素値 >= 配列[最大値要素]) { // 現在の最大値以上 後ポインタ[最大値要素] = 末尾要素; 前ポインタ[末尾要素] = 最大値要素; 後ポインタ[末尾要素] = "最大"; 最大値要素 = 末尾要素; } else if (新要素値 < 配列[最小値要素]) { // 現在の最小値よりも小 前ポインタ[最小値要素] = 末尾要素; 前ポインタ[末尾要素] = "最小"; 後ポインタ[末尾要素] = 最小値要素; 最小値要素 = 末尾要素; } else { // 最小値≦新要素値<最大値要素 var 後要素 = 最小値要素; // 新要素値<後要素値となる後要素を探す while (新要素値 >= 配列[後要素]) { 後要素 = 後ポインタ[後要素]; } var 前要素 = 前ポインタ[後要素]; // この時点で前要素値≦新要素値<後要素値になう。=の場合があるが発生順とする 後ポインタ[前要素] = 末尾要素; 前ポインタ[末尾要素] = 前要素; 前ポインタ[後要素] = 末尾要素; 後ポインタ[末尾要素] = 後要素; } }
(注)次の変数がグローバル変数として定義されているものとします。
配列 = ["AAA", "DDD", "FFF", "BBB", "EEE"];
前ポインタ = [];
後ポインタ = [];
最小値要素;
最大値要素;
配列長;
最小値要素と最小値要素がなくても、前ポインタや後ポインタを走査して「最小」「最大」の要素を探せばよいのですが、よく用いられる情報ですし、配列が大きいと時間がかかります。そのため、操作手順の中でこの値を更新するのが適切です。
配列長は、配列.length と同値ですので、あえてグローバル変数にする必要はありません。
新規にリスト構造を生成する操作は、追加操作とほぼ同じです。
最初の1件目(要素0)は、
前ポインタ[0] = "最小";
後ポインタ[0] = "最大";
最小値要素 = 0;
最大値要素 = 0;
とし、2件目以降は追加操作を繰り返せばよいのです。
削除をしても、配列からその要素を削除して、それ以降の要素を詰めて配列長を減らすのでは、処理が複雑になるし、処理時間もかかります。そうではなく、削除要素に削除フラグを付けるだけで、配列はそのままにしておくのが通常です。
ここでは、削除フラグとして前ポインタと後ポインタを「削除」とすることにしていますが、別な項目を設けることもあります。
削除要素値が複数個あるとき、すべてを削除するのか、どの一つを削除するのか、多様なオプションが考えられますが、ここでは配列の前方のある要素、すなわち最も先に入った要素を削除することにしました。
アルゴリズムは、配列を走査して削除されておらず削除要素値と一致する要素(削除要素)を確定し、右図の赤のポイントを青のように変更します。ソースコードを示します。
function 削除(削除要素値) { for (var 要素=0; 要素<配列長; 要素++) { if ( (前ポインタ[要素] != "削除") && (削除要素値 == 配列[要素]) ) { var 削除要素 = 要素; // 削除すべき要素が見つかった。 var 前要素 = 前ポインタ[削除要素]; var 後要素 = 後ポインタ[削除要素]; if (前要素 == "最小") { 前ポインタ[後要素] = "最小"; 最小値要素 = 後要素; } else if (後要素 == "最大") { 後ポインタ[前要素] = "最大"; 最大値要素 = 前要素; } else { 後ポインタ[前要素] = 後ポインタ[削除要素]; 前ポインタ[後要素] = 前ポインタ[削除要素]; } 前ポインタ[削除要素] = "削除"; 後ポインタ[削除要素] = "削除"; return; // 一つの要素を削除したら打ち切る。 } } alert("エラー " + 削除要素値 + " は存在しません"); }
昇順(小さい順)に取り出す例を示します(降順も同様です)。
function 昇順取出() {
昇順結果 = "最小";
var 要素 = 最小値要素;
while (後ポインタ[要素] != "最大") {
// 要素、配列[要素] を取り出す。
要素 = 後ポインタ[要素];
}
// 最大値要素、配列[最大値要素] を取り出す。
}
赤の部分が必須です。その理由は、最後の要素をwhileループ内部に組み入れる適切な方法がないからです。