鏈表

React源碼中使用了鏈表的結(jié)構(gòu)來(lái)存儲(chǔ)，今天使用js實(shí)現(xiàn)一下
什么是鏈表？
綠皮火車車箱，類型地下黨，只知上級(jí)下級(jí)，不知其他

鏈表的優(yōu)點(diǎn)：是存儲(chǔ)動(dòng)態(tài)靈活，可隨機(jī)存儲(chǔ)， 不像數(shù)組在內(nèi)存中存儲(chǔ)需要連續(xù)的空間
特性：內(nèi)存不連續(xù)性和無(wú)索引
讀?。篛(n), 插入／刪除:O(1)，適用于插入和刪除較多的場(chǎng)景

代碼實(shí)現(xiàn)：

var Node = function(ele) {
            this.ele = ele
            this.next = null
        }
        function LinkList(){
            this.length = 0
            this.head = null
        }
        /**添加*/
        LinkList.prototype.append = function(ele) {
                var node = new Node(ele)
                var current // 找到尾節(jié)點(diǎn)即node.next為null時(shí)

                if(this.head === null) {
                    this.head = node
                }else {
                    current = this.head
                    //  找到尾節(jié)點(diǎn)
                    while(current.next) {
                        current = current.next
                    }
                    current.next = node
                }
                this.length++
            }
        /**插入*/
        LinkList.prototype.insert = function(pos, ele) {
                if(pos > -1 && pos <= this.length) {
                    var node = new Node(ele)

                    var current = this.head
                    var index = 0
                    var previous
                    if(pos === 0) {
                        node.next = current
                        this.head = node
                    }else{
                        // 從head開(kāi)始 循環(huán)遍歷依次向下查找，
                        // 找到pos位置的前一個(gè)節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)
                        while(index++ < pos){
                            previous = current
                            current = current.next
                        }
                        previous.next = node
                        node.next = current
                    }
                    this.length++
                    return true
                }else{
                    return false
                }
            }

        /**根據(jù)pos刪除*/    
        LinkList.prototype.removeByPos = function(pos) {
                if(pos > -1 && pos < this.length) {
                    var current = this.head
                    var index = 0
                    var previous
                    if(pos == 0) {
                        this.head = current.next
                    }else {
                        // 從head開(kāi)始 循環(huán)遍歷依次向下查找，
                        // 找到pos位置的前一個(gè)節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)
                        while(index++ < pos) {
                            previous = current
                            current = current.next
                        }
                        previous.next = current.next
                    }
                    this.length--
                    return current.ele
                }else {
                    return null
                }
            }       

        /**返回位置*/
        LinkList.prototype.indexOf = function(ele){
                var current = this.head
                var index = 0
                while(current){
                    if(ele === current.ele){
                        return index
                    }
                    index++
                    current = current.next
                }
                return -1
            }

        var link = new LinkList()
        link.append('hell') 
        link.append('yoyo')
        link.insert(0, 'first')
        console.log(link)
        // {
        //   "length": 3,
        //   "head": {
        //     "ele": "first",
        //     "next": {
        //       "ele": "hell",
        //       "next": {
        //         "ele": "yoyo",
        //         "next": null
        //       }
        //     }
        //   }
        // }