如何在 javascript 中创建链表？

Question

如果我想用这个初始数据创建一个链表

    const linkedListData = {
  linkedList: {
    head: "1",
    nodes: [
      { id: "1", next: "1-2", value: 1 },
      { id: "1-2", next: "1-3", value: 1 },
      { id: "1-3", next: "2", value: 1 },
      { id: "2", next: "3", value: 3 },
      { id: "3", next: "3-2", value: 4 },
      { id: "3-2", next: "3-3", value: 4 },
      { id: "3-3", next: "4", value: 4 },
      { id: "4", next: "5", value: 5 },
      { id: "5", next: "5-2", value: 6 },
      { id: "5-2", next: null, value: 6 },
    ],
  },
};

但是结果 linkedList 应该是这样的

    const linkedListDataV2 = {
  value: 1,
  next: {
    value: 1,
    next: {
      value: 1,
      next: {
        value: 3,
      },
      next: {
        value: 4,
        next: {
          value: 4,
          next: {
            value: 4,
            next: {
              value: 5,
              next: {
                value: 6,
                next: {
                  value: 6,
                  next: null
                }
              }
            }
          }
        }
      }
    }
  }
}

是否有任何现有算法可以让我在 javascript 中创建 linkedList？原因是我正在尝试在 vs code 中调试一些链表算法，但我需要找到一种方法来轻松创建链表而不是手动创建它们。

Answer 1

您可以获取一个对象并将节点分配给实际节点和下一个节点。结果通过头部标识符获取列表。

这种方法也适用于未排序的数据。

const
    linkedList = { head: "1", nodes: [{ id: "1", next: "1-2", value: 1 }, { id: "1-2", next: "1-3", value: 1 }, { id: "1-3", next: "2", value: 1 }, { id: "2", next: "3", value: 3 }, { id: "3", next: "3-2", value: 4 }, { id: "3-2", next: "3-3", value: 4 }, { id: "3-3", next: "4", value: 4 }, { id: "4", next: "5", value: 5 }, { id: "5", next: "5-2", value: 6 }, { id: "5-2", next: null, value: 6 }] },
    list = linkedList.nodes.reduce((r, { id, next, value }) => {
        r[id] ??= {};
        r[id].value = value;
        r[id].next = r[next] ??= {};
        return r;
    }, {})[linkedList.head];

console.log(list);

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

Answer 2

循环版本（而不是使用 reduce）。与尼娜的回答在精神上相似，并且可能更容易理解。

const linkedListData = {
  linkedList: {
    head: "1",
    nodes: [
      { id: "1", next: "1-2", value: 1 },
      { id: "1-2", next: "1-3", value: 1 },
      { id: "1-3", next: "2", value: 1 },
      { id: "2", next: "3", value: 3 },
      { id: "3", next: "3-2", value: 4 },
      { id: "3-2", next: "3-3", value: 4 },
      { id: "3-3", next: "4", value: 4 },
      { id: "4", next: "5", value: 5 },
      { id: "5", next: "5-2", value: 6 },
      { id: "5-2", next: null, value: 6 },
    ],
  },
};

function nodesToList(nodes, headId) {
  // maps id -> {next: nextId, value: value}
  const byId = new Map(nodes.map(
    n => [n.id, {value: n.value, next: n.next}]));    
  // maps id -> {next: node, value: value}
  for (let n of byId.values()) {
    n.next = n.next == null ? null : byId.get(n.next);
  }
  // and now, just return the head
  return byId.get(headId)
}

console.log(nodesToList(
    linkedListData.linkedList.nodes, 
    linkedListData.linkedList.head));

如何在 javascript 中创建链表？

How to create linked list in javascript?

javascript

algorithm