单链表的实现

周末跟同学聊起他面试的事，被问起单链表翻转。当时想了个算法，遍历链表节点，就地翻转。

后面上网查了下，有三种：

1,弄个新链表，把旧链表每个节点都insertFirst。

2，弄个数组，存储旧链表，然后遍历一轮，翻转。

3，遍历链表的节点，就地翻转，性能最快。

后来，想找个JS单链表的类，没找到想要的。。。双向链表居多。被迫无赖，自己写了个。

!function(window) {
    var Util = window.Util =  {};
    var Node = Util.Node = function(data){
        //data contains
        this.data = data;
        //next node
        this.next = null;
    }

    Util.LinkedList = function(){
        this.head = null;
    }

    var fn = Util.LinkedList.prototype;
    /**
     * insert data to the head
     * @param data
     * @returns {boolean}
     */
    fn.insertFirst = function(data){
        var node= new Node(data);
        if(this.isEmpty()) {
            this.head = node;
            return true;
        }
        node.next = this.head;
        //change head to the new node
        this.head = node;
        return true;
    }
    /**
     * insert data to the last
     * @param data
     * @returns {boolean}
     */
    fn.insertLast = function(data){
        var node = new Node(data);
        if(this.isEmpty()) {
            //node = head;
            this.head = node;
            return true;
        }
        var p = this.head;
        var pre = this.head;
        //get the last node
        while(!this.isEnd(p)) {
            pre = p;
            p = p.next;
        }
        p.next = node;
        return false;
    }
    /**
     * insert newData before oldData
     * @param oldData
     * @param newData
     * @returns {boolean}
     */
    fn.insertBefore = function(oldData,newData){
        var preNode = this.find(oldData,true);

        if(preNode==null) {
            return false;
        }
        var newNode = new Node(newData);
        if(preNode == this.head) {
            this.insertFirst(newData);
        }else {
            var pNode = preNode.next;
            newNode.next = pNode;
            preNode.next = newNode;
        }
        return true;
    }
    /**
     * insert newData after oldData
     * @param oldData
     * @param newData
     * @returns {boolean}
     */
    fn.insertAfter = function(oldData,newData){
            var preNode = this.find(oldData);
            if(preNode == null) {
                return false;
            }
            var newNode = new Node(newData);
            var pNode = preNode.next;
            newNode.next = pNode;
            preNode.next = newNode;//pNode;
            return true;
    }
    /**
     * remove node
     * @param data
     */
    fn.remove = function(data){
        if(this.isEmpty()) {
            return false;
        }
        var preNode = this.find(data,true);
        if(preNode == this.head) {
            this.head = this.head.next;
        }else {
            var pNode = preNode.next;
            preNode.next = pNode.next;
        }
        return true;
    }
    /**
     * update data
     * @param oldData
     * @param newData
     * @returns {boolean}
     */
    fn.update = function(oldData,newData){
        var pNode = this.find(oldData);
        if(pNode != null) {
            pNode.data = newData;
            return true;
        }
        return false;
    }

    fn.find = function(data,flag){
        var p = this.head,
            pre = this.head;
        while(!this.isEnd(p) && p.data != data) {
            pre = p;
            p = p.next;
        }
        if(flag) return pre;
        else return p;
    }
    /**
     * is empty?
     */
    fn.isEmpty = function(){
        return !this.head;
    }
    /**
     * is the last node?
     * @param node
     */
    fn.isEnd = function(node){
        if(!node)
            return false;
        return !node.next;
    }

    fn.toString = function(){
        var pNode = this.head,
            str = "";
        while(pNode!=null) {
            str += pNode.data;
            pNode = pNode.next;
        }
        return str;
    }

    fn.reverse = function(){
        var node = this.head,
            pre,
            nextNext;
        while(node){
            nextNext = node.next;
            node.next = pre;
            pre = node;
            node = nextNext;
        }
        this.head = pre;
        return this;
    }
}(window);
////test code
//function trace(msg){
//    console.log(msg);
//}
//var linkedList = new Util.LinkedList();
//trace(linkedList.isEmpty() == true);
//linkedList.insertFirst(1);
//trace(linkedList.isEmpty() == false);
//linkedList.insertBefore(1,2);
//trace(linkedList.toString() == "21");
//linkedList.insertLast(3);
//trace(linkedList.toString() == "213");
//trace(linkedList.isEnd(linkedList.find(3)) == true);
//linkedList.remove(3);
//trace(linkedList.isEnd(linkedList.find(2)) == false);
//trace(linkedList.isEnd(linkedList.find(1)) == true);
//trace(linkedList.head.data == 2);
//linkedList.insertFirst(1);
//linkedList.insertFirst(2);
//linkedList.insertFirst(3);
//trace(linkedList.toString() == "32121");
//trace(linkedList.reverse().toString() == "12123");
//linkedList.update(2,4);
//trace(linkedList.toString() == "14123");
//linkedList.insertAfter(4,5);
//trace(linkedList.toString() == "145123");
//linkedList.insertBefore(5,6);
//trace(linkedList.toString() == "1465123");

温习一下感觉不错，出来社会几年，回头看这些东西简单多了。想当年学这些数据结构，都不知道学来干嘛。整本书看完，都还给老师了。

只记得当时那本书是严蔚敏写的，其中有一句话，令我很受教。所有程序都建立在数据和数据操作之上。延伸出来，MVC，MV,MVVM，这些框架，一开始就是model。

不管做什么，第一步我都开始弄数据。时间轴的节点就是链表，组件与组件之间就是一棵树。

单链表的实现

推荐阅读