LinkedList in JavaScript, how to append changes to list?

Question

I'm running into a referential issue with variables in JavaScript, and I've been banging my head against the wall trying to figure this out.

I'm preparing to teach a class on data structures, and I'm reviewing the material after not looking at it for at least 10 years.

I know Linked Lists in theory, but for some reason, I'm struggling to come up with code that actually works in JavaScript (I chose JavaScript because that's what my class knows best)

This is my code:

let LinkedList  = {
    head: {},
    tail: {}
};

let Node = {
    data: {},
    next: {}
}

function isObjectEmpty(obj1) {
    return Object.keys(obj1).length === 0 && obj1.constructor === Object;
}

function count(node, counter) {
    if (node.next) {
        return 1 + count(node.next, counter);
    }
    return counter;
}

/**
 * Adds data to LinkedList
 * @param {LinkedList} list
 * @param {Node} data
 */
function add_node(list, data) {
    let temp = Object.assign({}, Node);
    temp.data = data;
    temp.next = {};

    if (Object.keys(list.head).length === 0) {
        list.head = temp;
        list.tail = temp;
    } else {
        list.tail.next = temp;
        list.tail = temp;
    }
    return list;
}
function insert(l, n, position) {
    if (position <= 0) {
        position = 0;
    } else {
        position = position - 1;
    }

    var list = Object.assign({}, l);
    var node = Object.assign({}, Node);
    node.data = n;

    // this only counts elements on the list.
    var elements = count(list.head, 0);

    if (position > elements) {
        return list;
    }

    var currentPosition = list.head;
    var counter = 0;

    while (!isObjectEmpty(currentPosition)) {
        if (position === counter) {
            var tmp = currentPosition;
            currentPosition = node;
            currentPosition.next = tmp.next;
            return list;
        }
        currentPosition = currentPosition.next;
        counter++;
    }

    return list;
}

// how to use the function
let songs = [
{id: '1', name: 'Kamikaze', artist: 'Eminem', releaseDate: '2018-08-31'},
{id: '2', name: 'despacito', artist: 'Luis Fonsi', releaseDate: '2018-08-31'},
{id: '3', name: 'La tortura', artist: 'Shakira', releaseDate: '2018-08-31'},
{id: '4', name: 'Roar', artist: 'Roar', releaseDate: '2018-08-31'},
 ];

let list = Object.assign({}, LinkedList);
    songs.forEach((song) => {
        add_node(list, song); // nothing special, just builds the linkedlist
     });

list = insert(list, {id: '5', name: 'Havana', artist:'who knows', releaseDate:'2018-01-01'}, 3); 
console.log(list); // new object isn't there.

This function is supposed to insert an element in an arbitrary position in the linked list. It kinda works. The problem is that the returned list keeps the reference to the old object before the re-association.

If you put a debugger in this block:

    if (position === counter) {
        var tmp = currentPosition;
        currentPosition = node;
        currentPosition.next = tmp.next;
        return list;
    }

You can see that I'm actually successfully inserting the new node where I want to.

But if you console.log the list structure, you'll see that the newly inserted Node is nowhere to be found.

I'm not sure where I'm failing or why the list keeps the old references and doesn't follow the new "path".

Any pointers in the right direction is greatly appreciated.

Those Object.assign calls are bogus, it doesn't clone the nested objects. — Bergi
– Bergi, Commented Sep 2, 2018 at 20:55
Can you please also add an example of how you would call the function? — Bergi
– Bergi, Commented Sep 2, 2018 at 20:55
What is esObjetoVacio? And shouldn't you have a null check there? — Bergi
– Bergi, Commented Sep 2, 2018 at 20:56
@Bergi I just added more code, that should be a full example reproducing the issue. — ILikeTacos
– ILikeTacos, Commented Sep 2, 2018 at 21:03
Can you try this let temp = JSON.parse(JSON.stringify(Node)); instead of let temp = Object.assign({}, Node);? for each of Object.assign. May be the object reference is messing things up. — binariedMe
– binariedMe, Commented Sep 2, 2018 at 21:06

Bergi · Accepted Answer · 2018-09-03 12:48:07Z

If you put a debugger in this block:
if (position === counter) {
    var tmp = currentPosition;
    currentPosition = node;
    currentPosition.next = tmp.next;
    return list;
}
You can see that I'm actually successfully inserting the new node where I want to

No, you don't. If we drop the tmp and currentPosition assignment confusion, that bit of code is equivalent to

if (position === counter) {
    node.next = currentPosition.next;
    return list;
}

All that happens is that you are copying the tail of the list onto the new node, but you never really insert the node as the next of the one currently in the list. It's missing a

currentPosition.next = node;

A couple of other points:

Don't use isObjectEmpty and empty objects to represent "no node". Use null instead. If for some didactic reason you don't want to introduce null, use a boolean .isNode property on the objects to distinguish a node with data from an empty one.
Avoid Object.assign. Your usage is really unidiomatic. In
```
let temp = Object.assign({}, Node);
temp.data = data;
temp.next = {};
```
you are directly overwriting the values that you just copied from Node - better simplify to using an object literal:
```
let temp = {data, next: {}};
```
In var list = Object.assign({}, l); you don't really want to create a new object at all. You are going to mutate the passed in list, so you should just keep that. (If you wanted to make pure functions with immutable data structures, you would have to make all the nodes immutable as well, and for inserting clone the entire list until the desired position).
If your intention for Object.assign was to create new objects that later might involve other properties (or methods) that you weren't going to overwrite, use factory functions instead.
Don't count the list beforehand. Do the insertion in a single pass, and if you reach the end of the list before the position to inert then return.

function makeLinkedList() {
    return { head: null, tail: null };
}

function makeNode(data, next = null) {
    return { data, next };
}

function append(list, node) {
    if (list.head) {
        list.tail.next = node;
    } else {
        list.head = node;
    }
    list.tail = node;
}

function insert(list, data, position) {
    if (position < 0) throw new Error("position must be nonnegative");

    let newNode = makeNode(data);
    let prev = null, cur = list.head;
    while (cur != null && position > 0) {
        prev = cur;
        cur = cur.next;
        position--;
    }
    if (cur == null && position > 0) throw new Error("position must be <= list length")
    if (cur == null) {
        list.tail = newNode;
    } else {
        newNode.next = cur;
    }
    if (prev == null) {
        list.head = newNode;
    } else {
        prev.next = newNode;
    }
}

Thanks a lot for the code review!! Your points on Object.assign make a lot of sense, I was trying to make the list immutable and write pure functions but I overlooked the other issue. Greatly appreciated!
@ILikeTacos If you make an immutable list, this will greatly simplify the implementation as you don't need the list object any more - you can instead represent the list by its head node. You don't need the tail reference then. I also would recommend to use recursive append and insert functions then instead of iterative ones.

Nina Scholz · Accepted Answer · 2018-09-03 09:14:59Z

You could use a version without Object.assign and work with objects as list and nodes who are created by same named function. This function could be replaced later with instanciable functions for more OOP styled approach.

This proposal takes a node and inset it, depending on the function, at the end of the list or at any place in the list. If no node exists in the list, it is inserted at the beginning of the linked list.

function linkedList() {
    return { head: null, tail: null };
}

function node(data, next) {
    return { data, next };
}

function insertTail(list, node) {
    if (list.head) {
        list.tail.next = node;
        list.tail = list.tail.next;
    } else {
        list.head = node;
        list.tail = node;
    }
    return list;
}

function insertPos(list, node, n) {
    var temp = list.head,
        previous;

    if (!temp) {
        return insertTail(list, node);
    }

    while (temp.next && n--) {
        previous = temp;
        temp = temp.next;
    }

    node.next = temp;
    previous.next = node;

    return list;
}

var songs = [{ id: '1', name: 'Kamikaze', artist: 'Eminem', releaseDate: '2018-08-31' }, { id: '2', name: 'despacito', artist: 'Luis Fonsi', releaseDate: '2018-08-31' }, { id: '3', name: 'La tortura', artist: 'Shakira', releaseDate: '2018-08-31' }, { id: '4', name: 'Roar', artist: 'Roar', releaseDate: '2018-08-31' }],
    list = linkedList();

songs.forEach(song => insertTail(list, node(song)));
console.log(list);

insertPos(list, node({ id: '5', name: 'Havana', artist: 'who knows', releaseDate: '2018-01-01' }), 3);
console.log(list);

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

David784 · Accepted Answer · 2018-09-03 14:13:06Z

1

Couple of problems. First, you're replacing a node, not strictly inserting. I think you want your .next to be the tmp node, not tmp.next.

currentPosition.next = tmp;

Second, you need to keep a reference to the node immediately before the insertion point, so that you can set its next value to the newly inserted node:

previousNode.next = node //<- node being the one you're inserting

that's why you're not seeing the difference in your linked list.

*Edit (putting it all together):

var prevNode = null;
while (!isObjectEmpty(currentPosition)) {
  if (position === counter) {
    var tmp = currentPosition;
    currentPosition = node;
    currentPosition.next = tmp;
    if (prevNode === null) list.head = currentPosition;
    else prevNode.next = currentPosition;
    return list;
  }
  prevNode = currentPosition;
  currentPosition = currentPosition.next;
  counter++;
}

To make it safe for inserting into the initial position, we have to have the ability to set the list.head. Otherwise we set the previous node's next property.

edited Sep 3, 2018 at 14:13

answered Sep 2, 2018 at 21:08

David784

7,5243 gold badges24 silver badges35 bronze badges

2 Comments

ILikeTacos Over a year ago

but where would I put the previousNode.next? I think I follow what you're saying, and yes I agree, currentPosition.next should be set to tmp not to tmp.next I'm just having trouble following the previousNode comment. I also thought of keeping a reference to a previous element, just wasn't sure how to incorporate it into the solution.

David784 Over a year ago

I added some code to show how you could have a reference to the previous node, so that you could change its next link to point to the new item that you're inserting.

Collectives™ on Stack Overflow

LinkedList in JavaScript, how to append changes to list?

3 Answers 3

2 Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related