リストを次の値と前の値でソートする

Question

値がid, next, prevのオブジェクトがあります。 nextおよびprevの値は、idである。これらのオブジェクトはむしろ任意の順序です。リスト内に前のオブジェクトがないオブジェクトが位置1に来るように、次に最初のオブジェクトのIDが次の値になるなどの順序でそれらを取得したいと考えています。

• ソート機能は
• 接続することはできませんリスト内の異なる部分がある場合
は、これら2つの別々のリストになりますリストのリストを返す必要があります。 （いわば：私たちは2回の結末と2つの始まりを持っている）
• 0は前/
次のソート機能は、
• 擬似コードは大丈夫だろう複雑さの点では何のJavascriptの必要な可能な限り効率的にあってはならない意味します

let list = [ 
 
{"id": 181, "next": 182, "prev": 231}, 
 
{"id": 182, "next": 253, "prev": 181}, 
 
{"id": 230, "next": 231, "prev": 0}, 
 
{"id": 231, "next": 181, "prev": 230}, 
 
{"id": 253, "next": 254, "prev": 182}, 
 
{"id": 254, "next": 0, "prev": 253}, 
 
] 
 

 
console.log("unordered", list.map(x => x.id)) 
 
let falsesorted = sortByNextPrev(list); 
 
falsesorted.forEach(sub => { 
 
    console.log(sub.map(x => x.id)); 
 
}); 
 

 
function sortByNextPrev(list){ 
 
var sorted = list.reduce((acc,l) => { 
 
    let last = acc[acc.length-1]; 
 
    if(last.length === 0 || last[last.length-1].next === l.id){ 
 
     last.push(l) 
 
    } 
 
    else if(last[0].prev === l.id){ 
 
     last.unshift(l); 
 
    } 
 
    else{ 
 
     acc.push([l]); 
 
    } 
 
    return acc; 
 
},[[]]); 
 
return sorted; 
 
}

My機能明らかに私が望むものを達成していません。 私が達成しようとする順序は230,231,181,182,253,254です。

私はその周りに頭を包み込みましたが、効率的な解決策が見つかりませんでした。私は本当に愚かな機能を構築することができると思うが、私はむしろそうしたくない。

Answer 1

ルックアップ関数を使用し、最初の要素から順番に結果配列に入れます。ルックアップは、ソートされた配列でバイナリ検索を行うループで簡単に行うことも、ルックアップテーブルで最適化することもできます。

のは、最後のアプローチを選択してみましょう、私たちは、とにかく最初の要素を見つけるために、一回の反復を必要とする：

const byId = new Map(); 
const firsts = []; 
for (const el of list) { 
    byId.set(el.id, el); 
    if (!el.prev) firsts.push(el); 
} 
const results = firsts.map(first => { 
    const result = []; 
    for (let x = first; x != null; x = byId.get(x.next)) 
     result.push(x); 
    return result; 
});