Сортировать двусвязный список по следующему идентификатору Ramda. js

Question

Я хочу отсортировать двусвязный список по значению next_id.

Моя DLL:

const dll = [
  {id: '22', prev_id: '41', next_id: '45'},
  {id: '45', prev_id: '22', next_id: null},
  {id: '41', prev_id: '14', next_id: '22'},
  {id: '14', prev_id: null, next_id: '41'},
]

В результате:

const dll_result = [
  {id: '14', prev_id: null, next_id: '41'}, // next item - 41
  {id: '41', prev_id: '14', next_id: '22'}, // next item - 22
  {id: '22', prev_id: '41', next_id: '45'}, // next item - 45
  {id: '45', prev_id: '22', next_id: null},
]

Я понимаю, что сортировка DLL не имеет смысла, но в моем случае мне нужно чтобы последовательно визуализировать данные из массива, используя next_id.

PS Было бы неплохо узнать даже нативное решение, и тогда я мог бы попытаться преобразовать его в Ramda. js сам

Answer 1

Создайте индекс элементов am с помощью id, найдите 1-й элемент (prev_id === null), а затем выполните итерацию с определенным временем l oop и pu sh текущего объекта в массиве результатов. :

const findStart = R.find(R.propEq('prev_id', null))
const indexById = R.indexBy(R.prop('id'))

const sortByNextId = arr => {
  const index = indexById(arr)
  let current = findStart(arr)
  
  const sorted = []
  
  while(current) {
    sorted.push(current)
    current = index[current.next_id]
  }
  
  return sorted
}

const dll = [
  {id: '22', prev_id: '41', next_id: '45'},
  {id: '45', prev_id: '22', next_id: null},
  {id: '41', prev_id: '14', next_id: '22'},
  {id: '14', prev_id: null, next_id: '41'},
]

const result = sortByNextId(dll)

console.log(result)

<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.27.0/ramda.js"></script>

Answer 2

Собственный подход

Вы можете отсортировать по id и выбрать самый низкий id в качестве первого элемента желаемого выхода, затем вы можете выбрать следующие элементы * * * * найдя следующий узел, используя атрибут next_id.

const dll = [{id: '22', prev_id: '41', next_id: '45'},{id: '45', prev_id: '22', next_id: null},{id: '41', prev_id: '14', next_id: '22'},{id: '14', prev_id: null, next_id: '41'}],
      result = [[...dll].sort((a, b) => a.id - b.id).shift()];

dll.forEach(() => result.push(dll.find(({id}) => id === result[result.length - 1].next_id)));
console.log(result);