Sort Doubly Linked List By Next Id Ramda.js

I want to sort doubly linked list by next_id value. My DLL: const dll = [ {id: '22', prev_id: '41', next_id: '45'}, {id: '45', prev_id: '22', next_id: null}, {id: '41', prev

Solution 1:

Create am index of items by id, find the 1st item (prev_id === null), and then iterate with a while loop, and push the current object into the result array:

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

constsortByNextId = 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)

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

Solution 2:

Native approach

You can sort by id and pick the lowest id as the first element of the desired output, then you can push the next elements by finding the next node using the attribute 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);