Doubly Linked List in javascript

Question

I was building linked list in javascript. I dont understand one part.

function Node(element) {
	this.element = element;
	this.next = null;
	this.previous = null;
}

function LList() {
	this.head = new Node("head");
	
	this.find = find;
	this.findLast = findLast;

	this.remove = remove;
	this.insert = insert;
	this.display = display;
	this.dispReverse = dispReverse;
		
}

function find(item) {
	var currNode = this.head;
	while(currNode.element != item) {
		currNode = currNode.next;
	}

	return currNode;
}


function display(list) {
	var currNode = this.head.next;
	while (currNode != null) {
		console.log(currNode.element);
		currNode = currNode.next;
	}
}


function insert(newElement, item) {
	var newNode = new Node(newElement);
	var current = this.find(item);
	newNode.next = current.next;
	newNode.previous = current;
	current.next = newNode;


	// Why I dont need this part?
    // Since new node got inserted, on my thoughts,
    // the next node of the current node should point the new node as a previous one
    // current.next.previous = newNode;
	
}

function remove(item) {
	var currNode = this.find(item);
	if (currNode.next != null) {
		currNode.previous.next = currNode.next;
		currNode.next.previous = currNode.previous;
		currNode.next = null;
		currNode.previous = null;
	}
}

function findLast() {
	var currNode = this.head;
	while (currNode.next != null) {
		currNode = currNode.next;
	}

	return currNode;
}

function dispReverse() {

	var currNode = this.head;
	currNode = this.findLast();

	while(currNode.previous != null) {
		console.log(currNode.element);
		currNode = currNode.previous;
	}
}

var cities = new LList(); 
cities.insert("Conway", "head"); 
cities.insert("Russellville", "Conway"); 
cities.insert("Carlisle", "Russellville"); 
cities.insert("Alma", "Carlisle"); 
cities.display();

cities.remove("Carlisle");
cities.display();
cities.dispReverse();


/*
Output should look like this: 

Conway
Russellville
Carlisle
Alma

Conway
Russellville
Alma

Alma
Russellville
Conway
*/

Problem is the insert function!
Let's say if I have A B C node already.
And I want to insert K after B.

Currently, the next and previous of B are C and A for each.
The previous element of C is B.

Once I put K after B,
A B K C
(1) the next element of K will be C
(2) the previous element of K will be B.
(3) The next element of B is K
(4) previous element of C is K.

On the code I wrote in Insert function, each line of the codes below should process the upper statements.
(1) newNode.next = current.next;
(2) newNode.previous = current;
(3) current.next = newNode;
(4) current.next.previous = newNode;

But when I run this whole code including (4), error has occurred.
I don understand why...
Without the (4) line of codes, it works.

Is there anyone who can help me understand this?

Did you try to debug via some console.log ? Can you provide us the exact error ? Sounds like a reference problem to me — stephane-ruhlmann
@FelixKling Oh I think I didnt explain clearly. Inside the insert function there is comment like this. // current.next.previous = newNode; I think this is a proper code to be included in the insert function but when I put that inside the function and run it, error happens! — Sunyoung Kim
@stephane-ruhlmann As I mentioned up there, the code above works just fine. What I wonder is I think [current.next.previous = newNode;] should be included inside the insert function. Now I made it as a comment with '//'. So it didn't make an error. — Sunyoung Kim
Ok I get it, still an object reference issue to me, see answer below — stephane-ruhlmann

jmlane jmlane · Accepted Answer · 2015-07-08T06:47:39

You need to do step 4 before step 3:

current.next.previous = newNode
current.next = newNode

As it is, the reference of current.next (C) is being set to newNode (K) before you lookup the "old" current.next's previous property ( current.next.previous when points to B). Your reference to the current node is changed as soon as you assign it a new value. This is why current.next.previous is actually returning newNode.previous instead of the node reference you expect.

Doubly Linked List in javascript

2 Answers