Doubly Linked List

Definition

In computer science, 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/data_structures/linked_list.js

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

Usage

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.

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]