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