介紹

鏈表是一種在物理存儲單元上非連續(xù)、非順序的存儲結構數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序實現(xiàn)的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，
結點可以在運行時動態(tài)生成。每個結點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結點地址的指針域。

鏈表.jpg

和順序表的區(qū)別：

數(shù)組是需要一塊連續(xù)的內(nèi)存空間來存儲，對內(nèi)存的要求比較高。
而鏈表卻相反，它并不需要一塊連續(xù)的內(nèi)存空間。鏈表是通過指針將一組零散的內(nèi)存塊串聯(lián)在一起。

順序表

可以快速的查找某個元素，但是在插入和刪除時就要移動大量元素。原因就在于相鄰元素的存儲位置也具有鄰居關系。他們的編號是 0，1，2，3，4，...，n，它們在內(nèi)存中的位置也是緊挨著的，
中間沒有空隙，所以就無法快速添加元素。而當刪除后，當中就會留出空隙，自然需要彌補。

鏈表

無法快速的查找元素，但是我們在插入和刪除的過程中只需修改指針，就可以完成

鏈表數(shù)組對比.jpg

代碼實現(xiàn)

    //定義單個鏈表節(jié)點
    class ListNode {
      constructor(val) {
          this.val = val // 數(shù)據(jù)
          this.next = null
      }
    }

class LinkList {
    constructor() {
        this.length = 0
        this.head = null
    }

    // 向鏈表中添加節(jié)點
    append(element) {
        let node = new LinkNode(element)
        if (this.head == null) this.head = node
        let lastNode = this.getElementAt(this.length - 1)
        lastNode.next = node
        this.length++
    }

    // 在鏈表的指定位置插入節(jié)點
    insert(position, element) {
        if (position < 0 || position > this.length) return false
        let node = new LinkNode(element)

        if (position === 0) {
            node.next = this.head
            this.head = node
        } else {
            let pre = this.getElementAt(position - 1)
            node.next = pre.next
            pre.next = node
        }
        this.length++
        return true
    }

    // 刪除鏈表中指定位置的元素，并返回這個元素的值
    removeAt(position) {
        if (position < 0 || position >= this.length) return null;
        let cur = this.head
        if (position === 0) {
            this.head = cur.next
        } else {
            let pre = this.getElementAt(position - 1)
            cur = pre.next
            pre.next = cur.next
        }
        this.length--
        return cur.element
    }

    // 刪除鏈表中對應的元素
    remove(element) {
        let idx = this.indexOf(element)
        return this.removeAt(idx)
    }

    // 在鏈表中查找給定元素的索引
    indexOf(element) {
        let cur = this.head
        for(let i = 0; i<this.length; i++) {
            if(cur.element === element) return i
            cur = cur.next
        }

        return -1
    }

    // 返回鏈表中索引所對應的元素
    getElementAt(position) {
        if (position < 0 || position > this.length) return null
        let cur = this.head
        while (position--) {
            cur = cur.next;
        }

        return cur
    }

    // 判斷鏈表是否為空
    isEmpty() {
        return this.length === 0
    }


    // 返回鏈表的長度
    size() {
        return this.length
    }

    // 返回鏈表的頭元素
    getHead() {
        return this.head
    }

    // 清空鏈表
    clear() {
        this.head = null
        this.length = 0
    }

    // 輔助方法，按指定格式輸出鏈表中的所有元素，方便測試驗證結果
    toString() {
        let cur = this.head
        let str = ''

        while (cur) {
            let next = cur.next;
            next = next ? next.element : 'null';
            str += `{element: ${cur.element}, next: ${next}}`
            cur = cur.next
        }

        return str
    }
}