LinkedList in JavaScript, how to append changes to list?

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.

console.log

list

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.

Object.assign

esObjetoVacio

null

3 Answers
3

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

tmp

currentPosition

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

next

currentPosition.next = node;


A couple of other points:

isObjectEmpty

null

null

.isNode

Avoid Object.assign. Your usage is really unidiomatic. In

Object.assign

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:

Node

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

var list = Object.assign(, l);

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.

Object.assign

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.

count

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;




list

tail

append

insert

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.

Object.assign

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;

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.

.next

tmp

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:

next

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.

list.head

next

previousNode.next

currentPosition.next

tmp

tmp.next

previousNode

next

Thanks for contributing an answer to Stack Overflow!

But avoid …

To learn more, see our tips on writing great answers.

Some of your past answers have not been well-received, and you're in danger of being blocked from answering.

Please pay close attention to the following guidance:

But avoid …

To learn more, see our tips on writing great answers.

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.