This is a continuation of a series introducing data structures in javascript. A linked list is a
data structure consisting of a group of nodes that represent a sequence. Each element in a linked
list has a data field and a field that points to the the next node in the linked list. A doubly
linked list also includes a field that points to the previous node in the linked list.
The first step in creating a doubly linked list in javascript is to define a custom type. A doubly
linked list should be defined with a length property, a ‘head’ property which points to the first
element in the list, and a ‘tail’ property which points to the last element in the list.
function DoublyLinkedList() {
this.length = 0;
this.head = null;
this.tail = null;
}
Adding an item to the list is simply a matter of updating the ‘tail’ property with the new item and
updating the previous ‘tail’ item to have a ‘next’ value of the new node. If the length of the list
is zero, the ‘head’ and ‘tail’ properties are set to the node that is being added; making it the
first item in the list.
DoublyLinkedList.prototype = {
add: function(value) {
var node = {
value: value,
next: null,
previous: null,
}
if (this.length == 0) {
this.head = node;
this.tail = node;
}
else {
this.tail.next = node;
node.previous = this.tail;
this.tail = node;
}
this.length++;
},
};
To retrieve a value from the list, it requires that you traverse the list to find the node for a
given index. If an index is provided that does not exist in the list, then a null value should be
returned.
DoublyLinkedList.prototype = {
getNode: function(index) {
if ( index > this.Length - 1 || index < 0 ) {
return null;
}
var node = this.head;
var i = 0;
while (i++ < index) {
node = node.next;
}
return node;
},
displayNode: function(index) {
var node = this.getNode(index);
if (node != null) {
document.writeln('value = ' + node.value + '<br />');
document.writeln('previous = ' + (node.previous != null ? node.previous.value : 'null') + '<br />');
document.writeln('next = ' + (node.next != null ? node.next.value : 'null') + '<br />' );
return;
}
alert('invalid index!');
},
};
Note that displayNode is just a convenience function for the purpose of this demonstration. In any
case, you should check that the previous or next node is not null before attempting to access the
value.
The final core operation of implementing a doubly linked list is providing the ability to remove an
element. Removing an element from the list is a bit tricky because the previous node and next node
will need to have their properties updated. Any remove operation should handle the case where the
element to be removed is the first or last one. In both of these cases, you will need to update the
‘tail’ and ‘head’ property appropriately. Removing all other elements involves a similar lookup that
is done in the getNode() function. The length should also be manually updated.
DoublyLinkedList.prototype = {
remove: function(index) {
if ( index > this.Length - 1 || index < 0 ) {
return null;
}
var node = this.head;
var i = 0;
if (index == 0) {
this.head = node.next;
// check if we removed the only one in the list
if (this.head == null) {
this.tail = null;
}
else {
this.head.previous = null;
}
}
else if (index == this.length - 1) {
node = this.tail;
this.tail = node.previous;
this.tail.next = null;
}
else {
while (i++ < index) {
node = node.next;
}
node.previous.next = node.next;
node.next.previous = node.previous;
}
this.length--;
},
};
For convenience, the following is the complete implementation with sample usage.
function DoublyLinkedList() {
this.length = 0;
this.head = null;
this.tail = null;
}
DoublyLinkedList.prototype = {
add: function(value) {
var node = {
value: value,
next: null,
previous: null,
}
if (this.length == 0) {
this.head = node;
this.tail = node;
}
else {
this.tail.next = node;
node.previous = this.tail;
this.tail = node;
}
this.length++;
},
getNode: function(index) {
if ( index > this.Length - 1 || index < 0 ) {
return null;
}
var node = this.head;
var i = 0;
while (i++ < index) {
node = node.next;
}
return node;
},
displayNode: function(index) {
var node = this.getNode(index);
if (node != null) {
document.writeln('value = ' + node.value + '<br />');
document.writeln('previous = ' + (node.previous != null ? node.previous.value : 'null') + '<br />');
document.writeln('next = ' + (node.next != null ? node.next.value : 'null') + '<br />' );
return;
}
alert('invalid index!');
},
remove: function(index) {
if ( index > this.Length - 1 || index < 0 ) {
return null;
}
var node = this.head;
var i = 0;
if (index == 0) {
this.head = node.next;
// check if we removed the only one in the list
if (this.head == null) {
this.tail = null;
}
else {
this.head.previous = null;
}
}
else if (index == this.length - 1) {
node = this.tail;
this.tail = node.previous;
this.tail.next = null;
}
else {
while (i++ < index) {
node = node.next;
}
node.previous.next = node.next;
node.next.previous = node.previous;
}
this.length--;
},
};
var list = new DoublyLinkedList();
list.add("zero");
list.add("one");
list.add("two");
list.add("three");
list.displayNode(2); // prints value = two, previous = one, next = 3
list.remove(2);
list.displayNode(2); // prints value = three, previous = one, next = null
Code Blog 