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 linkedlist has a data field and a field that points to the the next node in the linked list. A doublylinked 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 doublylinked list should be defined with a length property, a 'head' property which points to the firstelement in the list, and a 'tail' property which points to the last element in the list.[sourcecode language="javascript"]function DoublyLinkedList() { this.length = 0; this.head = null; this.tail = null;}[/sourcecode]Adding an item to the list is simply a matter of updating the 'tail' property with the new item andupdating the previous 'tail' item to have a 'next' value of the new node. If the length of the listis zero, the 'head' and 'tail' properties are set to the node that is being added; making it thefirst item in the list.[sourcecode language="javascript"]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++; },};[/sourcecode]To retrieve a value from the list, it requires that you traverse the list to find the node for agiven index. If an index is provided that does not exist in the list, then a null value should bereturned.[sourcecode language="javascript"]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!'); },};[/sourcecode]Note that displayNode is just a convenience function for the purpose of this demonstration. In anycase, you should check that the previous or next node is not null before attempting to access thevalue.The final core operation of implementing a doubly linked list is providing the ability to remove anelement. Removing an element from the list is a bit tricky because the previous node and next nodewill need to have their properties updated. Any remove operation should handle the case where theelement 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 thatis done in the getNode() function. The length should also be manually updated.[sourcecode language="javascript"]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--; },};[/sourcecode]For convenience, the following is the complete implementation with sample usage.[sourcecode language="javascript"]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 = 3list.remove(2);list.displayNode(2); // prints value = three, previous = one, next = null[/sourcecode]