How to create linked list in javascript?

Question

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.

Nina Scholz · Accepted Answer · 2022-04-24 20:44:58Z

2

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

edited Apr 24, 2022 at 20:44

answered Apr 24, 2022 at 19:49

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

tucuxi · Accepted Answer · 2022-04-24 20:01:08Z

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

Collectives™ on Stack Overflow

How to create linked list in javascript?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related