How to create linked list in javascript?-CodePudding

If I want to create a linkedList with this initial data

    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 },
    ],
  },
};

But the result linkedList should look like

    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
                }
              }
            }
          }
        }
      }
    }
  }
}

Are there any existing algorithms where I can create a linkedList in javascript? The reason is I am trying to debug some linked list algorithms in vs code but I need to find a way to easily create a linked list instead of manually creating them.

CodePudding user response：

You could take an object and assign the nodes to actual and next node. As result take the list by the head identifier.

This approach works for unsorted data as well.

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; }

CodePudding user response：

A looping version (instead of using reduce). Similar in spirit to Nina's answer, and possibly easier to follow.

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));