## 2015年7月22日水曜日

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(); ```

``` \$ jslint sample2.js sample2.js is OK. \$ js sample2.js Conway Russellville Carlisle Alma Conway Carlisle Russellville Alma Conway Alma Carlisle Russellville \$ ```