Doubly Linked List

Definition

A linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.

In a doubly linked list, each node contains, besides the next-node link, a second link field pointing to the previous node in the sequence. The two links may be called forward(s) and backwards, or next and prev(ious).

Source: Wikipedia

Code: https://github.com/felipernb/algorithms.js/blob/master/src/data_structures/linked_list.js

Tests: https://github.com/felipernb/algorithms.js/blob/master/test/data_structures/linked_list.js

How to use

Import

var LinkedList = require('algorithms').DataStructure.LinkedList;

Initialization

var list = new LinkedList();

LinkedList.prototype.add(element, i)

Adds an element to the list in the ith position. If the position is not specified, the element is added to the end of the list. O(1) if adding to the end, O(n) if adding to the nth position.

list.add(1); // (1)
list.add(2); // (1)->(2)
list.add(3, 1) // (1)->(3)->(2)

LinkedList.head and LinkedList.tail

Pointers to the Nodes in the ends of the list

list.add(1); // (1)
list.add(2); // (1)->(2)
list.add(3, 1) // (1)->(3)->(2)
list.head; // {value: 1, prev: null, next: [Object (Node)]}
list.tail; // {value: 2, prev: [Object (Node)], next: null}

LinkedList.prototype.isEmpty() and LinkedList.length

Indicate whether the list is empty and the list's size

var list = new LinkedList();
list.isEmpty(); // true
list.length; // 0
list.add(1); // (1)
list.isEmpty(); // false
list.length; // 1

LinkedList.prototype.get(i)

Fetch the value of the element in the ith position in O(n), the list index is 0 based

var list = new LinkedList();
list.add(1);
list.add(2);
list.get(1); // 2
list.get(0); // 1

LinkedList.prototype.getNode(i)

Fetch the node in the ith position in O(n), the list index is 0 based

var list = new LinkedList();
list.add(1);
list.add(2);
list.get(1); // {value: 2, next: null, prev: [Object (Node)]}
list.get(0); // {value: 1, next: [Object (Node)], prev: null}

LinkedList.prototype.del(i)

Deletes the node in the ith position, with 0 based indices

list.add(1); // (1)
list.add(2); // (1)->(2)
list.add(3, 1) // (1)->(3)->(2)

list.del(1); // (1)->(2);
list.del(0); // (2);
list.del(0); // []

Linked.prototype.map(callback)

Runs the callback function to all values in the list

list.add(1);
list.add(2);
list.add(3);
list.add(4);
var a = [];
list.map(function (element) {
  a.push(element);
});

console.info(a); // [1,2,3,4]