我在那日界线上奔跑之JS---链表

日界线是指日期的分界线，国际规定180度经线，但这不是一条直线，是一条曲线
又是一个别人开心ipo痛哭的日子呜呜呜

先讲个故事，公元1世纪犹太战争，犹太人被包围了，不想被俘虏的“勇士”宁可自杀，首领指着最近的一个说

‘从你开始往后数，数到第三个，他就自杀，再从他下一个开始数，数到第三个自杀，后面的一样，开始吧’

其中聪明的两个人想办法插队，不想就这样死了（其中一个就是约瑟夫）

呵呵这是在告诉我“最困难的一刻，只要去想，总有解决的办法”

来吧，看聪明的ipo怎么解决的

通用的，n个人，第m个自杀，留下的是第几个呢

 /*
    实例
    使用循环链表解决约瑟夫环问题
     */
    function lastTwo(n, m) {
        var list = new LList();
        list.insert(1, "head");
        for (var i = 2; i <= n; i++) {
            list.insert(i, i - 1);
        }
        var currNode = list.head.next;
        var removeNode = null;
        while (list.length >= m) {
            removeNode = move(currNode, m);
            list.remove(removeNode.value);
            currNode = removeNode.next;
        }
        return list.display();
    }

    function move(currNode, m) {
        for (var i = 1; i < m; i++) {
            if (currNode.value === "head") {
                i -= 1;
            }
            currNode = currNode.next;
        }
        return currNode;
    }
    lastTwo(3, 3);

实现原理是什么的，慢慢从基础理解

单向链表

主要阐述了链表是怎么一回事：节点+链

上代码：

function Node(elem) {
//两个类：Node当前节点数据以及下一个节点的引用,LList头节点以及操作链表的方法
    this.elem = elem;
    this.next = null;
}

function LList() {
    this.head = new Node("head");
    this.find = find;
    this.findPrevious = findPrevious;
    this.insert = insert;
    this.remove = remove;
    this.display = display;
}

function find(item) {
    var currNode = this.head;
    while (currNode.elem !== item) {
        currNode = currNode.next;
    }
    return currNode;
}

function findPrevious(item) {
    var currNode = this.head;
    while (currNode.next !== null && currNode.next.elem !== item) {
        currNode = currNode.next;
    }
    return currNode;
}

function insert(newElem, item) {
    var newNode = new Node(newElem);
    var currNode = this.find(item);
    newNode.next = currNode.next;
    currNode.next = newNode;
}

function remove(item) {
    var prevNode = this.findPrevious(item);
    if (prevNode.next !== null) {
        prevNode.next = prevNode.next.next;
    }
}

function display() {
    var currNode = this.head;
    while (currNode.next !== null) {
        console.log(currNode.next.elem);
        currNode = currNode.next;
    }
}
/*
创建一个实例
 */
var cities = new LList();
cities.insert("Conway", "head");
cities.insert("Russellville", "Conway");
cities.display();

今天进行了如下优化，封装，继承

/*
        链表=节点+链
        节点=节点值+next(节点的引用指向后继)
        链=头结点声明初始化+方法+属性
         */
(function(window) {
    function Node(value) {
        this.value = value;
        this.next = null;
    }

    var uList = function() {
        this.head = new Node("head");
        this.length = 0;
    };
    uList.prototype.find = function(value) {
        if (value === "head") {
            return this.head;
        }
        var currNode = this.head.next;
        while (currNode !== null) {
            if (currNode.value === value) {
                return currNode;
            } else {
                currNode = currNode.next;
            }
        }
        return -1;
    };
    uList.prototype.insert = function(newValue, currValue) {
        var newNode = new Node(newValue);
        var currNode = this.find(currValue);
        if (currNode !== -1) {
            newNode.next = currNode.next;
            currNode.next = newNode;
        } else {
            alert("未找到要插入的位置元素");
        }
    };
    uList.prototype.findPrevious = function(value) {
        if (value === "head") {
            return -1;
        }
        var currNode = this.head;
        while (currNode.next !== null) {
            if (currNode.next.value === value) {
                return currNode;
            } else {
                currNode = currNode.next;
            }
        }
        return -1;
    };
    uList.prototype.remove = function(value) {
        var currNode = this.find(value);
        if (currNode !== -1) {
            var preNode = this.findPrevious(value);
            if (preNode !== -1) {
                preNode.next = currNode.next;
            } else {
                alert("未找到删除的元素");
            }
        } else {
            alert("未找到删除的元素");
        }
    };
    uList.prototype.display = function() {
        var currNode = this.head.next;
        while (currNode !== null) {
            console.log(currNode.value);
            currNode = currNode.next;
        }
    };

    var List = function() {
        uList.call(List);
    };
    List.prototype = new uList();
    window.List = List;
})(window);
/*
试一下
 */
var mylist = new List();
mylist.insert(1, "head");
mylist.display();

单向链表是最简单的链表，JS中把数组搞成对象，性能势必不行了，可以自己造个链表替代数组。不过随机访问一个元素还是数组好些。

双向链表
双向链表比单向链表相比node多了前置引用，方法删除操作修改next的同时要修改pre

function Node(elem){
    this.elem=elem;
    this.previous=null;
    this.next=null;
}
function LList(){
    this.head=new Node("head");
    this.find=find;
    this.findPrevious=findPrevious;
    this.insert=insert;
    this.remove=remove;
    this.display=display;
    this.displayReverse=displayReverse;
}
function find(elem){
    var currNode=this.head;
    while(currNode.elem!==elem&&currNode.next!==null){
        currNode=currNode.next;
    }
    return currNode;
}
function findPrevious(){
    var currNode=this.head;
    while(currNode.next!==null){
        currNode=currNode.next;
    }
    return currNode;
}
function insert(newElem,item){
    var currNode=this.find(item);
    var newNode=new Node(newElem);
    if(currNode.next!==null){
        currNode.next.previous=newNode;
        newNode.next=currNode.next;
    }
    newNode.previous=currNode;
    currNode.next=newNode;
}
function remove(elem){
    var currNode=this.find(elem);
    if(currNode.next!==null){
        currNode.next.previous=currNode.previous;
    }
    currNode.previous.next=currNode.next;
}
function display(){
    var currNode=this.head;
    while(currNode.next!==null){
        console.log(currNode.next.elem);
        currNode=currNode.next;
    }
}
function displayReverse(){
    var currNode=this.findPrevious();
    while(currNode.previous!==null){
        console.log(currNode.previous.elem);
        currNode=currNode.previous;
    }    
}

循环链表
循环链表与单向链表相比，强调最后一个节点的引用后继是head，所以初始化链表时头结点时后继是head本身

function Node(elem){
    this.elem=elem;
    this.next=null;
}
function LList(){
    this.head=new Node("head");
    this.head.next=this.head;
    this.find=find;
    this.insert=insert;
    this.findPrevious=findPrevious;
    this.remove=remove;
    this.display=display;
}
function find(elem){
    var currNode=this.head;
    while(currNode.next!==this.head&&currNode.elem!==elem){
        currNode=currNode.next;
    }
    return currNode;
}
function insert(newElem,item){
    var currNode=this.find(item);
    var newNode=new Node(newElem);
    if(currNode.next!==this.head){
        newNode.next=currNode.next;
        currNode.next=newNode;
    }else{
        currNode.next=newNode;
        newNode.next=this.head;
    }
}
function findPrevious(elem){
    var currNode=this.head;
    while(currNode.next.elem!==elem){
        currNode=currNode.next;
    }
    return currNode;
}
function remove(elem){
    var prevNode=this.findPrevious(elem);
    var currNode=this.find(elem);
    prevNode.next=currNode.next;
}
function display(){
    var currNode=this.head;
    while(currNode.next!==this.head){
        console.log(currNode.next.elem);
        currNode=currNode.next;
    }
}

优化一下就是文章开头的例子中用到的了

   (function(window) {
        function Node(value) {
            this.value = value;
            this.next = null;
        }

        function list() {
            this.head = new Node("head");
            this.head.next = this.head;
            this.length = 0;
        }
        list.prototype.find = function(elem) {
            if (elem === "head") {
                return this.head;
            }
            var curr = this.head.next;
            while (curr !== this.head) {
                if (curr.value === elem) {
                    return curr;
                } else {
                    curr = curr.next;
                }
            }
            return -1;
        };
        list.prototype.insert = function(newValue, currValue) {
            var newNode = new Node(newValue);
            var currNode = this.find(currValue);
            if (currNode === -1) {
                alert("未找到插入位置的元素");
            } else {
                newNode.next = currNode.next;
                currNode.next = newNode;
                this.length++;
            }
        };
        list.prototype.findPrevious = function(currValue) {
            if (this.head.next.value === currValue) {
                return this.head;
            }
            var curr = this.head.next;
            while (curr !== this.head) {
                if (curr.next.value === currValue) {
                    return curr;
                } else {
                    curr = curr.next;
                }
            }
            return -1;
        };
        list.prototype.remove = function(elem) {
            var curr = this.find(elem);
            if (curr === -1) {
                alert("找不到要删除的元素");
            } else {
                var pre = this.findPrevious(elem);
                if (pre === -1) {
                    alert("找不到要删除的元素");
                } else {
                    pre.next = curr.next;
                    this.length--;
                }
            }
        };
        list.prototype.display = function() {
            var curr = this.head;
            while (curr.next !== this.head) {
                console.log(curr.next.value);
                curr = curr.next;
            }
        };

        var LList = function() {
            list.call(LList);
        };
        LList.prototype = new list();
        window.LList = LList;
    })(window);