摘要：我對(duì)鏈表的學(xué)習(xí)什么是鏈表要存儲(chǔ)多個(gè)元素，數(shù)組可能是最常用的數(shù)據(jù)結(jié)構(gòu)。鏈表的學(xué)習(xí)創(chuàng)建一個(gè)鏈表各種方法表示要加入列表的項(xiàng)，它包含一個(gè)屬性以及一個(gè)屬性，表示要添加到列表的值，表示指向列表下一個(gè)節(jié)點(diǎn)項(xiàng)的指針。

要存儲(chǔ)多個(gè)元素，數(shù)組可能是最常用的數(shù)據(jù)結(jié)構(gòu)。這種數(shù)據(jù)結(jié)構(gòu)非常方便，但是有一個(gè)缺點(diǎn)：從數(shù)組的起點(diǎn)或者中間插入或移除項(xiàng)的成本非常高，因?yàn)樾枰苿?dòng)元素（比如你插入一個(gè)元素后面的所有的元素都移動(dòng)了“位置”）。

鏈表存儲(chǔ)有序的元素集合，但是不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。每個(gè)元素都是由一個(gè)存儲(chǔ)元素本身的節(jié)點(diǎn)和一個(gè)指向下一元素的引用（也叫指針或者鏈接）組成。

相比于數(shù)組來(lái)說(shuō)，鏈表的好處在于添加或者刪除元素的時(shí)候不需要移動(dòng)其他元素。但是操作鏈表需要使用指針。數(shù)組的一個(gè)優(yōu)點(diǎn)是可以直接訪問(wèn)任何位置的任何元素，但是要是想訪問(wèn)鏈表中的某一元素，則是必須從起點(diǎn)開(kāi)始迭代直到找到目標(biāo)元素。

創(chuàng)建一個(gè)鏈表

function LinkedList() {
    var Node = function(element) {
        this.element = element;
        this.next = null;
    }

    //各種方法
}

Node表示要加入列表的項(xiàng)，它包含一個(gè)element屬性以及一個(gè)next屬性，element表示要添加到列表的值，next表示指向列表下一個(gè)節(jié)點(diǎn)項(xiàng)的指針。

當(dāng)一個(gè)Node元素被創(chuàng)建時(shí)，它的next指針總是null

向鏈表尾部追加元素

列表為空，添加的是第一個(gè)元素。列表不為空，向其追加元素。

要循環(huán)訪問(wèn)列表中的所有元素，就需要有一個(gè)起點(diǎn)，就是head

this.append = function(element) {
    var node = new Node(element), //傳入值創(chuàng)建Node項(xiàng)
        current;

    if(head === null) { //如果為空鏈表
        head = node; //設(shè)置node為head（head為第一個(gè)節(jié)點(diǎn)的引用）
    } else {
        current = head; //從表頭開(kāi)始
        while(current.next) { 
            //循環(huán)列表，找到最后一項(xiàng)（列表最后一個(gè)節(jié)點(diǎn)的下一個(gè)元素始終是null）
            current = current.next;
        }
        //使當(dāng)前最后一項(xiàng)的指針指向node
        current.next = node;
    }
    length++; //更新列表長(zhǎng)度
};

使用append

var list = new LinkedList();
list.append(15);
list.append(10);

從鏈表移除元素

輸入位置，從特定位置移除一個(gè)元素

this.removeAt = function(position) {
    if(position > -1 && position < length) { //有效性檢測(cè)
        var current = head, //用current來(lái)循環(huán)列表
        previous,
        index = 0;

        if(position === 0) {
            head = current.next; //移除第一個(gè)元素，直接把head指向下一個(gè)元素
        } else {
            while(index++ < position) { //循環(huán)列表找到滿足條件的那個(gè)元素
                previous = current; //
                current = current.next; //把下一個(gè)變量覆給current
            }
            //跳過(guò)current，將當(dāng)前要移除的元素的上一個(gè)與下一項(xiàng)直接連接起來(lái)。
            previous.next = current.next;
        }
        length --;
        return current.element;
    } else {
        return null;
    }
}

在任意位置插入一個(gè)元素

this.insert = function (position, element) {
    if(position >= 0 && position <= length) {
        var node = new Node(element),
            current = head; //通過(guò)current從head位置開(kāi)始迭代
            previous,
            index = 0;

        if(position === 0) { //第一個(gè)位置
            node.next = current; //此時(shí)current = head,指向head那么node就成了第一個(gè)
            head = node; //node指向?yàn)閔ead
        } else {
            while (index++ < position ) { //循環(huán)迭代到目標(biāo)位置
                previous = current; 
                current = current.next;
            }

            node.next = current; // node的下一個(gè)為current
            previous.next = node; // node的上一個(gè)位置為previous
        }
        length++;
        return true;
    } else {
        return false;
    }
}

把LinkedList對(duì)象轉(zhuǎn)換成一個(gè)字符串。

this.toString = function() {
    var current = head,
        string = "";
    while(current) { //循環(huán)訪問(wèn)列表
        string += current.element + (current.next ? "
" : "");
        current = current.next;
    }
    return string; //返回字符串
}

返回元素的位置

this.indexOf = function(element) {
    var current = head,
        index = 0;
    while(current) {
        if(element === current.element) {
            return index; //找到返回當(dāng)前位置
        }
        index ++;
        current = current.next;
    }
    return -1;    //找不到返回-1
}

輸入元素，移除該元素

this.remove = function(element) {
    var index = this.indexOf(element); //得到元素的位置
    return this.removeAt(index); //移除該元素
}

判斷是否為空 得到長(zhǎng)度 得到第一個(gè)元素

this.isEmpty = function () {
    return length === 0;
}

this.size = function () {
    return length;
}

this.getHead = function () {
    return head;
}

他和普通鏈表的區(qū)別，在雙向鏈表中，鏈接是雙向的，一個(gè)鏈向下一個(gè)元素一個(gè)鏈向上一個(gè)元素。在操作雙向鏈表的時(shí)候既要像普通鏈表一樣考慮next，也要考慮prev。

雙向列表提供了兩種迭代列表的方法：從頭到尾迭代，或者反過(guò)來(lái)。

創(chuàng)建一個(gè)雙向列表

function DoublyLinkedList() {
    var Node = function(element) {
        this.element = element;
        this.next = null;
        this.prev = null; //新指針
    };
    
    var length = 0;
    var head = null;
    var tail = null; //對(duì)列表最后一項(xiàng)的引用
    
    //各種方法
}

在任意位置插入一個(gè)新元素

this.insert = function(position, element) {
    if(position >= 0 && position <= length) {
        var node = new Node(element),
            current = head,
            previous,
            index = 0;
            
        if(position === 0) { //在第一個(gè)位置添加
            if(!head) { //如果head不存在即鏈表為空
                head = node;
                tail = node;
            } else { //鏈表不為空
                node.next = current;
                current.prev = node;
                head = node;
            }
        } else if(position === length) { //在最后一個(gè)位置添加
            current = tail;
            current.next = node;
            node.prev = current;
            tail = node;
        } else {
            while(index++ < position) { //在列表中間添加
                previous = current; //循環(huán)迭代
                current = current.next;
            }
            node.next = current;
            previous.next = node;
            
            current.prev = node;
            node.prev = previous;
        }
        length ++; //更新列表長(zhǎng)度
        
        return true;
    } else {
        return false;
    }
}

從任意位置移除元素

this.removeAt = function(position) {
    if(position > -1 && position < length) { //檢查越界值
        var current = head,
            previous,
            index = 0;
        if(position === 0) { //第一個(gè)位置
            head = current.next;
            
            if(length === 1) { //如果鏈表只有一項(xiàng)
                tail = null;
            } else { //也就相當(dāng)于把current.next.prev = null
                head.prev = null;
            }
        } else if(position === length -1) { //最后一項(xiàng)
            current = tail; //tail的引用賦給current變量
            tail = current.prev; //上一項(xiàng)指向tail
            tail.next = null; //最后一項(xiàng)的next都是指向null的
        } else {
            while(index++ < position) { //從中間位置移除
                previous = current;
                current = current.next;
            }
            
            previous.next = current.next; //直接跳過(guò)current連接上一項(xiàng)和下一項(xiàng)
            current.next.prev = previous;
        }
        length --;
        return current.element;
    } else {
        return null;
    }
}

單向循環(huán)鏈表和鏈表唯一去別在于：最后一個(gè)元素指向下一個(gè)元素的指針（tail.next）不是引用null而是指向第一個(gè)元素（head）

雙向循環(huán)鏈表有指向head的tail.next，也有指向tail的head.prev