數組

數組——最簡單的內存數據結構

數組存儲一系列同一種數據類型的值。（ Javascript 中不存在這種限制）

對數據的隨機訪問，數組是更好的選擇，否則幾乎可以完全用 「鏈表」 來代替

在很多編程語言中，數組的長度是固定的，當數組被填滿時，再要加入新元素就很困難。Javascript 中數組不存在這個問題。

但是 Javascript 中的數組被實現成了對象，與其他語言相比，效率低下。

數組的一些核心方法

方法 描述
push 方法將一個或多個元素添加到數組的末尾，并返回該數組的新長度。(改變原數組)
pop 方法從數組中刪除最后一個元素，并返回該元素的值。(改變原數組)
shift 方法從數組中刪除第一個元素，并返回該元素的值，如果數組為空則返回 undefined 。(改變原數組)
unshift 將一個或多個元素添加到數組的開頭，并返回該數組的新長度(改變原數組)
concat 連接兩個或多個數組，并返回結果（返回一個新數組，不影響原有的數組。）
every 對數組中的每個元素運行給定函數，如果該函數對每個元素都返回 true，則返回 true。若為一個空數組，，始終返回 true。 （不會改變原數組，[].every(callback)始終返回 true）
some 對數組中的每個元素運行給定函數，如果任一元素返回 true，則返回 true。若為一個空數組，，始終返回 false。（不會改變原數組，）
forEach 對數組中的每個元素運行給定函數。這個方法沒有返回值，沒有辦法中止或者跳出 forEach() 循環，除了拋出一個異常（foreach不直接改變原數組，但原數組可能會被 callback 函數該改變。）
map 對數組中的每個元素運行給定函數，返回每次函數調用的結果組成的數組（map不直接改變原數組，但原數組可能會被 callback 函數該改變。）
sort 按照Unicode位點對數組排序，支持傳入指定排序方法的函數作為參數（改變原數組）
reverse 方法將數組中元素的位置顛倒，并返回該數組（改變原數組）
join 將所有的數組元素連接成一個字符串
indexOf 返回第一個與給定參數相等的數組元素的索引，沒有找到則返回 -1
lastIndexOf 返回在數組中搜索到的與給定參數相等的元素的索引里最大的值，沒有找到則返回 -1
slice 傳入索引值，將數組里對應索引范圍內的元素（淺復制原數組中的元素）作為新數組返回（原始數組不會被改變）
splice 刪除或替換現有元素或者原地添加新的元素來修改數組,并以數組形式返回被修改的內容(改變原數組)
toString 將數組作為字符串返回
valueOf 和 toString 類似，將數組作為字符串返回

棧

棧是一種遵循后進先出（LIFO）原則的有序集合，新添加或待刪除的元素都保存在棧的同一端，稱作棧頂，另一端就叫棧底。在棧里，新元素都靠近棧頂，舊元素都接近棧底。

通俗來講，就是你向一個桶里放書本或者盤子，你要想取出最下面的書或者盤子，你必須要先把上面的都先取出來。

棧也被用在編程語言的編譯器和內存中保存變量、方法調用等，也被用于瀏覽器歷史記錄 (瀏覽器的返回按鈕)。

代碼實現

// 封裝棧
    function Stack() {
        // 棧的屬性
        this.items = []

        // 棧的操作
        // 1.將元素壓入棧
        Stack.prototype.push = function (element) {
            this.items.push(element)
        }
        // 2.從棧中取出元素
        Stack.prototype.pop = function () {
            return this.items.pop()
        }
        // 3.查看棧頂元素
        Stack.prototype.peek = function () {
            return this.items[this.items.length - 1]
        }
        // 4.判斷是否為空
        Stack.prototype.isEmpty = function () {
            return this.items.length === 0
        }
        // 5.獲取棧中元素的個數
        Stack.prototype.size = function () {
            return this.items.length
        }
        // 6.toString()方法
        Stack.prototype.toString = function () {
            let str = ''
            for (let i = 0; i< this.items.length; i++) {
                str += this.items[i] + ' '
            }
            return str
        }

    }

    // 棧的使用
    let s = new Stack()

隊列

隊列是遵循先進先出(FIFO，也稱為先來先服務)原則的一組有序的項。隊列在尾部添加新
元素，并從頂部移除元素。添加的元素必須排在隊列的末尾。

生活中常見的就是排隊

代碼實現

function Queue() {
        this.items = []
        // 1.將元素加入隊列
        Queue.prototype.enqueue = function (element) {
            this.items.push(element)
        }
        // 2.從隊列前端刪除元素
        Queue.prototype.dequeue = function () {
            return this.items.shift()
        }
        // 3.查看隊列前端元素
        Queue.prototype.front = function () {
            return this.items[0]
        }
        // 4.判斷是否為空
        Queue.prototype.isEmpty = function () {
            return this.items.length === 0
        }
        // 5.獲取隊列中元素的個數
        Queue.prototype.size = function () {
            return this.items.length
        }
        // 6.toString()方法
        Queue.prototype.toString = function () {
            let str = ''
            for (let i = 0; i< this.items.length; i++) {
                str += this.items[i] + ' '
            }
            return str
        }
    }
    
    // 隊列使用
    let Q = new Queue()

優先級隊列：

代碼實現

function PriorityQueue() {
        function QueueElement(element, priority) {
            this.element = element
            this.priority = priority
        }
        this.items = []

        PriorityQueue.prototype.enqueue = function (element, priority) {
            let queueElement = new QueueElement(element,priority)

            // 判斷隊列是否為空
            if (this.isEmpty()) {
                this.items.push(queueElement)
            } else {
                let added = false // 如果在隊列已有的元素中找到滿足條件的，則設為true，否則為false，直接插入隊列尾部
                for (let i = 0; i< this.items.length; i++) {
                    // 假設priority值越小，優先級越高，排序越靠前
                    if (queueElement.priority < this.items[i].priority) {
                        this.items.splice(i, 0, queueElement)
                        added = true
                        break
                    }
                }
                if (!added) {
                    this.items.push(queueElement)
                }
            }

        }
        
    }
    

鏈表

鏈表——存儲有序的元素集合，但在內存中不是連續放置的。

鏈表(單向鏈表)中的元素由存放元素本身「data」 的節點和一個指向下一個「next」 元素的指針組成。牢記這個特點

相比數組，鏈表添加或者移除元素不需要移動其他元素，但是需要使用指針。訪問元素每次都需要從表頭開始查找。

代碼實現:
單向鏈表

function LinkedList() {
        function Node(data) {
            this.data = data
            this.next = null

        }
        this.head = null // 表頭
        this.length = 0
        // 插入鏈表
        LinkedList.prototype.append = function (data) {
            // 判斷是否是添加的第一個節點
            let newNode = new Node(data)
            if (this.length == 0) {
                this.head = newNode
            } else {
                let current = this.head
                while (current.next) { 
                // 如果next存在，
                // 則當前節點不是鏈表最后一個
                // 所以繼續向后查找
                    current = current.next
                }
                // 如果next不存在
                 // 則當前節點是鏈表最后一個
                // 所以讓next指向新節點即可
                current.next = newNode
            }
            this.length++
        }
        // toString方法
        LinkedList.prototype.toString = function () {
            let current = this.head
            let listString = ''
            while (current) {
                listString += current.data + ' '
                current = current.next
            }
            return listString
        }
         // insert 方法
        LinkedList.prototype.insert = function (position, data) {
            if (position < 0 || position > this.length) return false
            let newNode = new Node(data)
            if (position == 0) {
                newNode.next = this.head
                this.head = newNode
            } else {
                let index = 0
                let current = this.head
                let prev = null
                while (index++ < position) {
                    prev = current
                    current = current.next
                }
                newNode.next = current
                prev.next = newNode
            }
            this.length++
            return true
        }
        // get方法
        LinkedList.prototype.get = function (position) {
            if (position < 0 || position >= this.length) return null
            let index = 0
            let current = this.head
            while (index++ < position){
                current = current.next
            }
            return current.data
        }
        LinkedList.prototype.indexOf = function (data) {
            let index = 0
            let current = this.head
            while (current) {
                if (current.data == data) {
                    return index
                } else {
                    current = current.next
                    index++
                }
            }

            return  -1
        }
        LinkedList.prototype.update = function (position, data) {
            if (position < 0 || position >= this.length) return false
            let index = 0
            let current = this.head
            while (index++ < position) {
                current = current.next
            }
            current.data = data
            return  true
        }
        LinkedList.prototype.removeAt = function (position) {
            if (position < 0 || position >= this.length) return null
            if (position == 0) {
                this.head = this.head.next
            } else {
                let index = 0
                let current = this.head
                let prev = null
                while (index++ < position) {
                    prev = current
                    current = current.next
                }
                prev.next = current.next
            }
            this.length--
            return  true


        }
        LinkedList.prototype.remove = function (data) {
            let postions = this.indexOf(data)

            return this.removeAt(postions)
        }
        
    }

    let list = new LinkedList()
雙向鏈表：包含表頭、表尾 和 存儲數據的 節點，其中節點包含三部分：一個鏈向下一個元素的next， 另一個鏈向前一個元素的prev 和存儲數據的 data。牢記這個特點

function doublyLinkedList() {
        this.head = null // 表頭：始終指向第一個節點，默認為 null
        this.tail = null // 表尾：始終指向最后一個節點，默認為 null
        this.length = 0 // 鏈表長度

        function Node(data) {
            this.data = data
            this.prev = null
            this.next = null
        }

        doublyLinkedList.prototype.append = function (data) {
            let newNode = new Node(data)

            if (this.length === 0) {
            // 當插入的節點為鏈表的第一個節點時
            // 表頭和表尾都指向這個節點
                this.head = newNode
                this.tail = newNode
            } else {
            // 當鏈表中已經有節點存在時
            // 注意tail指向的始終是最后一個節點
            // 注意head指向的始終是第一個節點
            // 因為是雙向鏈表，可以從頭部插入新節點，也可以從尾部插入
            // 這里以從尾部插入為例，將新節點插入到鏈表最后
            // 首先將新節點的 prev 指向上一個節點，即之前tail指向的位置
                newNode.prev = this.tail
            // 然后前一個節點的next（及之前tail指向的節點）指向新的節點
            // 此時新的節點變成了鏈表的最后一個節點
                this.tail.next = newNode
            // 因為 tail 始終指向的是最后一個節點，所以最后修改tail的指向
                this.tail = newNode
            }
            this.length++
        }
        doublyLinkedList.prototype.toString = function () {
            return this.backwardString()
        }
        doublyLinkedList.prototype.forwardString = function () {
            let current = this.tail
            let str = ''

            while (current) {
                str += current.data + ''
                current = current.prev
            }

            return str
        }
        doublyLinkedList.prototype.backwardString = function () {
            let current = this.head
            let str = ''

            while (current) {
                str += current.data + ''
                current = current.next
            }

            return str
        }

        doublyLinkedList.prototype.insert = function (position, data) {
            if (position < 0 || position > this.length) return false
            let newNode = new Node(data)
            if (this.length === 0) {
                this.head = newNode
                this.tail = newNode
            } else {
                if (position == 0) {
                    this.head.prev = newNode
                    newNode.next = this.head
                    this.head = newNode
                } else if (position == this.length) {
                    newNode.prev = this.tail
                    this.tail.next = newNode
                    this.tail = newNode
                } else {
                    let current = this.head
                    let index = 0
                    while( index++ < position){
                        current = current.next
                    }
                    newNode.next = current
                    newNode.prev = current.prev
                    current.prev.next = newNode
                    current.prev = newNode

                }

            }

            this.length++
            return true
        }
        doublyLinkedList.prototype.get = function (position) {
            if (position < 0 || position >= this.length) return null
            let current = this.head
            let index = 0
            while (index++) {
                current = current.next
            }

            return current.data
        }
        doublyLinkedList.prototype.indexOf = function (data) {
            let current = this.head
            let index = 0
            while (current) {
                if (current.data === data) {
                    return index
                }
                current = current.next
                index++
            }
            return  -1
        }
        doublyLinkedList.prototype.update = function (position, newData) {
            if (position < 0 || position >= this.length) return false
            let current = this.head
            let index = 0
            while(index++ < position){
                current = current.next
            }
            current.data = newData
            return true
        }
        doublyLinkedList.prototype.removeAt = function (position) {
            if (position < 0 || position >= this.length) return null
            let current = this.head
            if (this.length === 1) {
                this.head = null
                this.tail = null
            } else {
                if (position === 0) { // 刪除第一個節點
                    this.head.next.prev = null
                    this.head = this.head.next
                } else if (position === this.length - 1) { // 刪除最后一個節點
                    this.tail.prev.next = null
                    this.tail = this.tail.prev
                } else {
                    let index = 0
                    while (index++ < position) {
                        current = current.next
                    }
                    current.prev.next = current.next
                    current.next.prev = current.prev
                }
            }
            this.length--
            return current.data
        }
        doublyLinkedList.prototype.remove = function (data) {
            let index = this.indexOf(data)
            return this.removeAt(index)
        }
    }

感謝你的閱讀～
————————————————
版權聲明：本文為CSDN博主「重慶崽兒Brand」的原創文章，遵循CC 4.0 BY-SA版權協議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/brand2014/java/article/details/106134844