function Node(elem, prev, next) {

    this.elem = elem;

    this.prev = prev ? prev : null;

    this.next = next ? prev : null;

}

function LinkedList() {

    this.length = 0;

    this.head = null;

    var that = this;

    if (arguments.length > 0) {

        var a = arguments[0];

        if (a instanceof Array) {

            a.forEach(function(elem) {

                that.push(elem);

            });

        }

    }

}

LinkedList.prototype.push = function(elem) {

    var newNode = new Node(elem);

    if (this.length === 0) {

        this.head = newNode;

        this.head.prev = newNode;

        this.head.next = newNode;

    } else {

        newNode.next = this.head;

        newNode.prev = this.head.prev;

        this.head.prev.next = newNode; // !!! CAUTION !!!

        this.head.prev = newNode;

    }

    ++this.length;

    return this.length;

};

// alias for push

LinkedList.prototype.append = function(elem) {

    return this.push(elem);

};

LinkedList.prototype.unshift = function(elem) {

    var newNode = new Node(elem);

    if (this.length === 0) {

        this.head = newNode;

        this.head.prev = newNode;

        this.head.next = newNode;

    } else {

        newNode.next = this.head;

        newNode.prev = this.head.prev;

        this.head.prev.next = newNode; // !!! CAUTION !!!

        this.head.prev = newNode;

    }

    this.head = newNode;

    ++this.length;

    return this.length;

};

LinkedList.prototype.shift = function() {

    if (this.length === 0) {

        return null;

    }

    var head = this.head,

        node = new Node(head.elem);

    head.next.prev = head.prev;

    head.prev.next = head.next;

    delete(head);

    this.head = head.next;

    --this.length;

    return node.elem;

};

LinkedList.prototype.pop = function() {

    if (this.length === 0) {

        return null;

    }

    var tail = this.head.prev,

        node = new Node(tail.elem);

    tail.prev.next = tail.next;

    tail.next.prev = tail.prev;

    delete(tail);

    --this.length;

    return node.elem;

};

LinkedList.prototype._get = function(index) {

    if (index < 0 || index >= this.length) {

        throw new DOMException("LinkedList index out of bounds!");

    }

    if (index===0) {

        return this.head;

    }

    var pivot = Math.round(this.length / 2);

    var p = null, i;

    if (index <= pivot) {

        p = this.head; // head => tail

        for (i = 0; i < index; i++) {

            p = p.next;

        }

    } else {

        p = this.head.prev; // tail => head

        for (i = this.length - 1; i > index; i--) {

            p = p.prev;

        }

    }

    return p;

};

LinkedList.prototype._delete = function(node) {

    var retNode = new Node(node.elem);

    node.prev.next = node.next;

    node.next.prev = node.prev;

    var p = node.next;

    if (node===this.head) {

        this.head = p;

    }

    node = null;

    this.length--;

    return {

        p: 0 <this.length ? p : null,

        v: retNode.elem

    }

};

LinkedList.prototype._insertBefore = function(node, elem) {

    var newNode = new Node(elem);

    newNode.next = node;

    newNode.prev = node.prev;

    node.prev.next = newNode;

    node.prev = newNode;

    ++this.length;

    return newNode;

};

LinkedList.prototype.get = function(index) {

    var p = this._get(index);

    return p.elem;

};

LinkedList.prototype.splice = function(start,deleteCount,items) {

    var p = this._get(start), o, list = new LinkedList();

    while (deleteCount--) {

        o = this._delete(p);

        p = o.p;

        list.push(o.v);

        if (null===p) {break;}

    }

    var that = this;

    if (typeof items !== "undefined") {

        var i = 0;

        if (items instanceof Array) {

            for (i = 0; i < items.length; i++) {

                p = that._insertBefore(p, items[i]);

            }

        } else if (items instanceof LinkedList) {

            for (i = 0; i < items.length; i++) {

                p = that._insertBefore(p, items.get(i));

            }

        } else {

            that._insertBefore(p, items);

        }

    }

    return list;

};

LinkedList.prototype.forEach = function(callback) {

    var p = this.head,

        index = 0;

    do {

        callback(p.elem, index);

        p = p.next;

        index++;

    } while (p != this.head);

    return this;

};

LinkedList.prototype.map = function(callback) {

    var newList = new this.__proto__.constructor();

    this.forEach(function(elem) {

        newList.push(callback(elem));

    });

    return newList;

};

LinkedList.prototype.reduce = function(callback, initValue) {

    if (this === null) {

        throw new TypeError('LinkedList.prototype.reduce ' +

            'called on null or undefined');

    }

    if (typeof callback !== 'function') {

        throw new TypeError(callback + ' is not a function');

    }

    var acc = initValue,

        p = this.head;

    do {

        acc = callback(acc, p.elem);

        p = p.next;

    } while (p != this.head);

    return acc;

};

LinkedList.prototype.join = function(sep) {

    var s = "";

    if (this.length === 0) {

        return s;

    }

    if (this.length === 1) {

        return this.head.elem;

    }

    var p = this.head;

    do {

        s += p.elem.toString() + sep;

        p = p.next;

    } while (p != this.head.prev);

    s += p.elem.toString();

    return s;

};

LinkedList.prototype.toString = function() {

    return '[' + this.join(',') + ']';

};

LinkedList.prototype.insertBeforeIndex = function(index, elem) {

    if (index === 0) {

        this.unshift(elem);

        return this.length;

    }

    if (index >this.length) {

        throw new DOMException('index out of bounds');

    }

    if (index === this.length) {

        this.append(elem);

        return this.length;

    }

    var node = new Node(elem);

    if (index === this.length-1) {

        var tail = this.head.prev;

        node.next = tail;

        node.prev = tail.prev;

        tail.prev.next = node;

        tail.prev = node;

    } else {

        var p = this._get(index);

        node.next = p;

        node.prev = p.prev;

        p.prev.next = node;

        p.next.prev = node;

    }

    ++this.length;

    return this.length;

};

 1 // test

 2 var list = new LinkedList();

 3

 4 for (var i = 1; i < 10; i++) {

 5     list.push(i);

 6 }

 7 for (i = 0; i < list.length; i++) {

 8     console.log(list.get(i));    // 1,2,3,4,5,6,7,8,9

 9 }

10

11 // list.forEach(function(elem) {console.log(elem);});

12 var newList = list.map(function(elem) {

13     return elem - 1;

14 });

15 console.log(newList.toString()); //  0,1,2,3,4,5,6,7,8

16 newList.shift();

17 console.log(newList.toString()); // 1,2,3,4,5,6,7,8

18

19 var oList = new LinkedList();

20 oList.push({ x: 2 });

21 oList.push({ x: 2 });

22 oList.push({ x: 3 });

23

24 var mul = oList.reduce(function(a, c) {

25     return a * c.x;

26 }, 1);

27 console.log(mul); // 12

map,reduce

var a = [3, 12, 17, 16, 73, 32, 61, 46, 52, 49, 6, 5];

var list = new LinkedList(a);

console.log(list.toString());

console.log('array: ' + a.length + ' list: ' + list.length);

list.insertBeforeIndex(0, 99);

console.log(list.toString());

list.insertBeforeIndex(3, 99);

console.log(list.toString());

list.insertBeforeIndex(list.length, 100);

console.log(list.toString());

list.insertBeforeIndex(list.length-1, 98);

console.log(list.toString());

console.log(list.length);

insertBeforeIndex

function getTopN(a, n) {

    function _getMaxElem(a) {

        if (a.length === 0)

            throw "empty array";

        if (a.length === 1)

            return { index: 0, value: a[0] };

        var max = a.get(0), index = 0, c;

        for (var i = 0; i < a.length; i++) {

            c = a.get(i);

            if (c > max) {

                max = c;

                index = i;

            }

        }

        return {

            index: index,

            value: max

        }

    }

    var o = {}, b = [];

    while (n--) {

        o = _getMaxElem(a);

        b.push(o.value);

        a.splice(o.index, 1);

    }

    return b;

}

/**

 * 5 largest elements: [73,61,52,49,46]

 * -------------sorted------------------

 * [ 73, 61, 52, 49, 46, 32, 17, 16, 12, 6, 5, 3 ]

 */

var a = [3, 12, 17, 16, 73, 32, 61, 46, 52, 49, 6, 5];

var list = new LinkedList(a);

var top5 = getTopN(list, 5);

console.log('5 largest elements: [' + top5.toString() + ']');

console.log('-------------sorted------------------');

console.log(a.sort(function(a, b) { return b - a; }));