移动双链接列表Ramda.js

Question

当我开始使用双链接列表时，管理prev_id & next_id变得更加困难。

const dll = [
  {id: '14', prev_id: null, next_id: '41'}, // <- source
  {id: '41', prev_id: '14', next_id: '22'}, 
  {id: '22', prev_id: '41', next_id: '45'},
  {id: '45', prev_id: '22', next_id: null}, // <- destination
]

例如，我希望将对象14移到末尾，因此数组应该变成：

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

要更改对象的prev_id和next_id，我需要做的最困难的事情是什么？

我的尝试：

​

.as-console-wrapper { max-height: 100% !important; top: 0; }

<script type="text/javascript" charset="utf8" src="//cdn.jsdelivr.net/npm/ramda@0.27.0/dist/ramda.min.js"></script>
<script>
  const {move} = R

  const dll = [
    {id: '14', prev_id: null, next_id: '41'}, //<- source
    {id: '41', prev_id: '14', next_id: '22'}, //<- destination
    {id: '22', prev_id: '41', next_id: '45'}, 
    {id: '45', prev_id: '22', next_id: null}, 
  ]

  const fromId = '14'
  const toId = '41' 

  const fromItem = dll.find(item => item.id === fromId)
  const toItem = dll.find(item => item.id === toId)

  const updated = dll.map(item => {
    if (item.id === fromId) {
      return {...item, prev_id: toId, next_id: toItem.next_id}
    } else if (item.prev_id === fromId) {
      return {...item, prev_id: fromItem.prev_id}
    } else if (item.id === toItem.next_id) {
      return {...item, prev_id: fromId} 
    } else if (item.id === toId) {
      return {...item, next_id: fromId}    
    } else {
      return item
    }
  })

  console.log(JSON.stringify(move(0, 1, updated), null, 2))
</script>

​

Answer 1

我会做这样的事，希望能帮上忙.

在双链接列表中移动一个项目是不理想的，因为你需要转移所有的链接.

​

const move = (id, toIndex, list) => {
  const fromIndex = R.findIndex(
    R.whereEq({ id }), 
    list,
  );
  
  return R.move(fromIndex, toIndex, list);
};

// R.nth would cause cyclic dbl-list
const pickId = (i, list) => R.propOr(null, 'id', list[i]);

const shiftLinks = (item, i, list) => R.mergeRight(item, {
  prev: pickId(R.dec(i), list),
  next: pickId(R.inc(i), list),
});

const moveById = R.pipe(
  move,
  R.addIndex(R.map)(shiftLinks),
);  


// ==
const data = [
  {id: 'first', prev: null, next: 'second'}, 
  {id: 'second', prev: 'first', next: 'third'},
  {id: 'third', prev: 'second', next: 'fourth'},
  {id: 'fourth', prev: 'third', next: null},
];
console.log(
  // id: 'second', toIndex: 3, data: data
  moveById('second', 3, data),
);

<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.27.0/ramda.js" integrity="sha256-buL0byPvI/XRDFscnSc/e0q+sLA65O9y+rbF+0O/4FE=" crossorigin="anonymous"></script>

​

Answer 2

正如我在评论中提到的，我发现这是一个不太可能的数据结构，并没有从一个真正的双链接列表中获得任何好处。另外，在我询问之前和之后插入或移动项目时的评论中。该版本假定所指的是在给定节点之后移动，并在函数的版本之前记录我们可能还想要的位置。

公平的警告，它是丑陋的命令式代码，在其功能中任意改变数据结构。(当然不是，当然是在功能上；我不是野蛮人！)

您在评论中说，您已经拥有了insert和delete函数。如果是这样的话，您可能可以像我这里所做的那样编写一个简单的move版本，只需在目标节点之后插入一个修改过的删除节点副本。

我不尝试将插入的节点放置在数组中的任何特定位置；从数据结构来看，我假设将其放在末尾并不是一个问题。如果是这样的话，我们也得开始处理指数了。这并不难，但很丑。

这段代码没有错误检查，这是留给读者的练习。如果您使用不在列表中的id，我们将不对所发生的事情负责。它可能被零除，发射导弹，或者偷走你的男朋友。我已经警告过你了。

​

// or Ramda's `clone`, or whatever
const clone = (o) => JSON .parse (JSON .stringify (o))

const removeNode = (dll, id) => {
  const list = clone (dll)
  const byId  = (i) => list .find (({id}) => id === i)
  const node = byId (id)
  const prevNode = node .prev_id ? byId (node .prev_id) : null
  const nextNode = node .next_id ? byId (node .next_id) : null
  if (prevNode) prevNode .next_id = node .next_id
  if (nextNode) nextNode .prev_id = node .prev_id
  return list.filter(node => node .id !== id)
}

const insertAfter = (dll, id, item) => {
  const list = clone (dll)
  const byId  = (i) => list .find (({id}) => id === i)
  const node = byId (id)
  const nextNode = node .next_id ? byId (node .next_id) : null
  node .next_id = item .id
  if (nextNode) nextNode .prev_id = item .id
  return [...list, {
    ...item, 
    prev_id: node .id,
    next_id: nextNode ? nextNode .id : null
  }]
}

const moveAfter = (dll, fromId, afterId) => {
  const node = dll .find (({id}) => id == fromId)
  return insertAfter (removeNode (dll, fromId), afterId, node)
}

// and insertBefore, moveBefore

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

console.log (
  moveAfter (dll, '14', '41')
)

​