日界線是指日期的分界線，國際規定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);