在双向链表中移动 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

正如我在评论中提到的，我发现这是一种不太可能的数据结构，获得了 none 真正双向链表的好处。同样在评论中，我询问了插入或移动项目时 before 与 after 的区别。此版本假设的意思是将给定节点 after 移动，并指出我们可能还需要 before 版本的函数。

公平警告，它是丑陋的命令式代码，在其函数内随心所欲地改变数据结构。（虽然不是，当然是在功能边界上；我不是野蛮人！）

您在评论中说您已经拥有 insert 和 delete 功能。如果是这样，您也许可以按照我在这里的方式编写 move 的简单版本，只需在目标节点之后插入已删除节点的更改副本即可。

我不会尝试将插入的节点放在数组中的任何特定位置；我从数据结构中假设将它放在最后不是问题。如果是这样，我们也必须开始处理索引。不难，就是丑

此代码没有错误检查，将其留作 reader 的练习。如果您使用不在列表中的 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')
)

Answer 2

我会做这样的事情，希望对你有帮助...

移动双链表中的项目并不理想，因为那时您需要移动所有链接...

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>

在双向链表中移动 Ramda.js

Move in doubly linked list Ramda.js

arrays

doubly-linked-list

ramda.js