JavaScript - Linked Lists(Doubly Linked List, back method)

Data Structures and Algorithms With Javascript
(O'Reilly Media)
Michael McMillan(著)

開発環境

• OS X Yosemite - Apple (OS)
• Emacs (Text Editor)
• JavaScript (プログラミング言語)
• SpiderMonkey (JavaScript engine)

Data Structures and Algorithms With Javascript (Michael McMillan(著)、O'Reilly Media)のChapter 6(Linked Lists)、Exercises 2.(No. 4245)を解いてみる。

Exercises 2.(No. 4245)

JavaScript(Emacs)

/*jslint         browser : true, continue : true,
  devel  : true, indent  : 4,    maxerr   : 50,
  newcap : true, nomen   : true, plusplus : false,
  regexp : true, sloppy  : true, vars     : false,
  white  : true
*/

/*global print, kjs*/
var Node = function (element) {
        this.element = element;
        this.next = null;
    },
    LinkedList = function () {
        this.head = new Node('head');
    },
    DNode = function (element) {
        this.element = element;
        this.next = null;
        this.previous = null;
    },
    DLinkedList = function () {
        this.head = new DNode('head');
    };

LinkedList.prototype.find = function (item) {
    var curr_node = this.head;
    while (curr_node.element !== item) {
        curr_node = curr_node.next;
    }
    return curr_node;
};
LinkedList.prototype.insert = function (new_element, item) {
    var new_node = new Node(new_element),
        current = this.find(item);
    new_node.nex = current.next;
    current.next = new_node;
};
LinkedList.prototype.display = function () {
    var curr_node = this.head;
    while (curr_node.next !== null) {
        print(curr_node.next.element);
        curr_node = curr_node.next;
    }
};
LinkedList.prototype.findPrevious = function (item) {
    var curr_node = this.head;
    while (curr_node !== null && curr_node.next.element !== item) {
        curr_node = curr_node.next;
    }
    return curr_node;
};
LinkedList.prototype.remove = function (item) {
    var prev_node = this.findPrevious(item);
    
    if (prev_node.next !== null) {
        prev_node.next = prev_node.next.next;
    }
};
DNode.prototype = new Node();
DNode.prototype.constructor = DNode;
DLinkedList.prototype = new LinkedList();
DLinkedList.prototype.constructor = DLinkedList;

DLinkedList.prototype.findLast = function () {
    var curr_node = this.head;

    while (curr_node.next !== null) {
        curr_node = curr_node.next;
    }
    return curr_node;
};
DLinkedList.prototype.dispReverse = function () {
    var curr_node = this.findLast();
    
    while (curr_node.previous !== null) {
        print(curr_node.element);        
        curr_node = curr_node.previous;
    }
};
DLinkedList.prototype.remove = function (item) {
    var curr_node = this.find(item);
    if (curr_node.next !== null) {
        curr_node.previous.next = curr_node.next;
        curr_node.next.previous = curr_node.previous;
        curr_node.next = null;
        curr_node.previous = null;
    }
};
DLinkedList.prototype.insert = function (new_element, item) {
    var new_node = new DNode(new_element),
        current = this.find(item);

    new_node.next = current.next;
    new_node.previous = current;
    current.next = new_node;
};
DLinkedList.prototype.back = function (n, item) {
    var curr_node = this.find(item),
        temp1,
        temp2,
        temp3;

    while (n !== 0 && curr_node.previous !== null) {
        temp1 = curr_node.previous.previous;
        temp2 = curr_node.previous;
        temp3 = curr_node.next;
        if (temp1 !== null) {
            temp1.next = curr_node;
        }
        curr_node.previous = temp1;
        curr_node.next = temp2;
        temp2.previous = curr_node;
        temp2.next = temp3;
        if (temp3 !== null) {
            temp3.previous = temp2;
        }
        n -= 1;
    }
    return curr_node;
};
var cities = new DLinkedList();
cities.insert('Conway', 'head');
cities.insert('Russellville', 'Conway');
cities.insert('Carlisle', 'Russellville');
cities.insert('Alma', 'Carlisle');
cities.display();
print();
cities.back(1, 'Carlisle');
cities.display();
print();
cities.back(2, 'Alma');
cities.display();

出力結果(Terminal, shell, SpiderMonkey)

$ jslint sample2.js

sample2.js is OK.
$ js sample2.js
Conway
Russellville
Carlisle
Alma

Conway
Carlisle
Russellville
Alma

Conway
Alma
Carlisle
Russellville
$