JavaScriptでnext・previousプロパティを持つオブジェクトを正しい順序に並べ替える方法

本記事では、複数ページからなるWebサイトの各ページを表すオブジェクトの配列を例に、「next」プロパティと「previous」プロパティを手がかりにして、ランダムな順序で配置された要素を正しい順序へ並べ替える方法を解説します。

各オブジェクトは、別のオブジェクトのidを参照する「next」プロパティ(最終ページを表すオブジェクトには存在しません)と、直前のオブジェクトのidを参照する「previous」プロパティ(先頭ページを表すオブジェクトには存在しません)を持っています。

以下が今回扱うサンプルのオブジェクト配列です。現時点ではすべてのオブジェクトがランダムな順序で配置されています。

let arr = [
    { id: "1325asdfasdasd", next: "5345341fgdfgdd", previous:"545234123fsdfd" },
    { id: "das987as9dya8s", next: "3j12k3b1231jkj" },
    { id: "89ad8sasds9d8s", previous: "1j3b12k3jbasdd" },
    { id: "5345341fgdfgdd", next: "1j3b12k3jbasdd", previous:"1325asdfasdasd" },
    { id: "1423123123asfd", next: "545234123fsdfd", previous:"3j12k3b1231jkj" },
    { id: "1j3b12k3jbasdd", next: "89ad8sasds9d8s", previous:"5345341fgdfgdd" },
    { id: "3j12k3b1231jkj", next: "1423123123asfd", previous:"das987as9dya8s" },
    { id: "545234123fsdfd", next: "1325asdfasdasd", previous:"1423123123asfd" },
];

目標は、「previous」を持たないオブジェクト(=先頭ページ)が最初に、「next」を持たないオブジェクト(=最終ページ)が最後に来るよう、next・previousの参照関係が正しくつながった状態に整列させることです。

この問題は、次の2つのステップで解決できます。

ステップ1:idをキーにしたMapの作成と先頭オブジェクトの特定

まず、配列全体を走査しながら、idをキー・オブジェクト自身を値としてMapに登録します。あわせて、「previous」を持たないオブジェクト(=連結リストの先頭)を別の変数に保存しておきます。

const objectMap = new Map();
let firstObject;
const sortedArray = [];
for(const obj of arr){
    objectMap.set(obj.id, obj);
    if(!obj.previous){
        firstObject = obj;
    }
}

Mapを使うことで、後続のステップでidから対応するオブジェクトをO(1)で高速に取得できるのがポイントです。

ステップ2:「next」をたどって新しい配列を構築する

次に、先頭オブジェクトから出発し、「next」プロパティが指すidを順番にMapから取り出しては結果配列へ追加していきます。「next」を持たないオブジェクト(=最終ページ)に到達した時点でループが終了します。

for(let start = firstObject; start; start = objectMap.get(start.next)){
    sortedArray.push(start);
};
console.log(sortedArray);

このアルゴリズムの計算量は、配列の走査と連結リストの辿り合わせてO(n)であり、要素数が増えても効率的に動作します。

それでは、コード全体と実際の出力結果を確認してみましょう。

完全なサンプルコード

let arr = [
    { id: "1325asdfasdasd", next: "5345341fgdfgdd", previous:"545234123fsdfd" },
    { id: "das987as9dya8s", next: "3j12k3b1231jkj" },
    { id: "89ad8sasds9d8s", previous: "1j3b12k3jbasdd" },
    { id: "5345341fgdfgdd", next: "1j3b12k3jbasdd", previous:"1325asdfasdasd" },
    { id: "1423123123asfd", next: "545234123fsdfd", previous:"3j12k3b1231jkj" },
    { id: "1j3b12k3jbasdd", next: "89ad8sasds9d8s", previous:"5345341fgdfgdd" },
    { id: "3j12k3b1231jkj", next: "1423123123asfd", previous:"das987as9dya8s" },
    { id: "545234123fsdfd", next: "1325asdfasdasd", previous:"1423123123asfd" },
];
const objectMap = new Map();
let firstObject;
const sortedArray = [];
for(const obj of arr){
    objectMap.set(obj.id, obj);
    if(!obj.previous){
        firstObject = obj;
    }
}
for(let start = firstObject; start; start = objectMap.get(start.next)){
    sortedArray.push(start);
};
console.log(sortedArray);

実行結果

上記のコードをコンソールで実行すると、以下のように正しい順序で並べ替えられた配列が出力されます。先頭のオブジェクトは「previous」を持たず、最後のオブジェクトは「next」を持たないことが確認できます。

[
    { id: 'das987as9dya8s', next: '3j12k3b1231jkj' },
    {
        id: '3j12k3b1231jkj',
        next: '1423123123asfd',
        previous: 'das987as9dya8s'
    },
{
    id: '1423123123asfd',
    next: '545234123fsdfd',
    previous: '3j12k3b1231jkj'
},
{
    id: '545234123fsdfd',
    next: '1325asdfasdasd',
    previous: '1423123123asfd'
},
{
    id: '1325asdfasdasd',
    next: '5345341fgdfgdd',
    previous: '545234123fsdfd'
},
{
    id: '5345341fgdfgdd',
    next: '1j3b12k3jbasdd',
    previous: '1325asdfasdasd'
},
{
    id: '1j3b12k3jbasdd',
    next: '89ad8sasds9d8s',
    previous: '5345341fgdfgdd'
},
{    id: '89ad8sasds9d8s', previous: '1j3b12k3jbasdd' }
]