數(shù)組

數(shù)組——最簡(jiǎn)單的內(nèi)存數(shù)據(jù)結(jié)構(gòu)

數(shù)組存儲(chǔ)一系列同一種數(shù)據(jù)類型的值。（ Javascript 中不存在這種限制）

對(duì)數(shù)據(jù)的隨機(jī)訪問(wèn)，數(shù)組是更好的選擇，否則幾乎可以完全用 「鏈表」 來(lái)代替

在很多編程語(yǔ)言中，數(shù)組的長(zhǎng)度是固定的，當(dāng)數(shù)組被填滿時(shí)，再要加入新元素就很困難。Javascript 中數(shù)組不存在這個(gè)問(wèn)題。

但是 Javascript 中的數(shù)組被實(shí)現(xiàn)成了對(duì)象，與其他語(yǔ)言相比，效率低下。

數(shù)組的一些核心方法

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

棧

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

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

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

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

// 封裝棧
    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.獲取棧中元素的個(gè)數(shù)
        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()

隊(duì)列

隊(duì)列是遵循先進(jìn)先出(FIFO，也稱為先來(lái)先服務(wù))原則的一組有序的項(xiàng)。隊(duì)列在尾部添加新
元素，并從頂部移除元素。添加的元素必須排在隊(duì)列的末尾。

生活中常見(jiàn)的就是排隊(duì)

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

function Queue() {
        this.items = []
        // 1.將元素加入隊(duì)列
        Queue.prototype.enqueue = function (element) {
            this.items.push(element)
        }
        // 2.從隊(duì)列前端刪除元素
        Queue.prototype.dequeue = function () {
            return this.items.shift()
        }
        // 3.查看隊(duì)列前端元素
        Queue.prototype.front = function () {
            return this.items[0]
        }
        // 4.判斷是否為空
        Queue.prototype.isEmpty = function () {
            return this.items.length === 0
        }
        // 5.獲取隊(duì)列中元素的個(gè)數(shù)
        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
        }
    }
    
    // 隊(duì)列使用
    let Q = new Queue()

優(yōu)先級(jí)隊(duì)列：

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

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)

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

        }
        
    }
    

鏈表

鏈表——存儲(chǔ)有序的元素集合，但在內(nèi)存中不是連續(xù)放置的。

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

相比數(shù)組，鏈表添加或者移除元素不需要移動(dòng)其他元素，但是需要使用指針。訪問(wèn)元素每次都需要從表頭開(kāi)始查找。

代碼實(shí)現(xiàn):
單向鏈表

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

        }
        this.head = null // 表頭
        this.length = 0
        // 插入鏈表
        LinkedList.prototype.append = function (data) {
            // 判斷是否是添加的第一個(gè)節(jié)點(diǎn)
            let newNode = new Node(data)
            if (this.length == 0) {
                this.head = newNode
            } else {
                let current = this.head
                while (current.next) { 
                // 如果next存在，
                // 則當(dāng)前節(jié)點(diǎn)不是鏈表最后一個(gè)
                // 所以繼續(xù)向后查找
                    current = current.next
                }
                // 如果next不存在
                 // 則當(dāng)前節(jié)點(diǎn)是鏈表最后一個(gè)
                // 所以讓next指向新節(jié)點(diǎn)即可
                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()
雙向鏈表：包含表頭、表尾 和 存儲(chǔ)數(shù)據(jù)的 節(jié)點(diǎn)，其中節(jié)點(diǎn)包含三部分：一個(gè)鏈向下一個(gè)元素的next， 另一個(gè)鏈向前一個(gè)元素的prev 和存儲(chǔ)數(shù)據(jù)的 data。牢記這個(gè)特點(diǎn)

function doublyLinkedList() {
        this.head = null // 表頭：始終指向第一個(gè)節(jié)點(diǎn)，默認(rèn)為 null
        this.tail = null // 表尾：始終指向最后一個(gè)節(jié)點(diǎn)，默認(rèn)為 null
        this.length = 0 // 鏈表長(zhǎng)度

        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) {
            // 當(dāng)插入的節(jié)點(diǎn)為鏈表的第一個(gè)節(jié)點(diǎn)時(shí)
            // 表頭和表尾都指向這個(gè)節(jié)點(diǎn)
                this.head = newNode
                this.tail = newNode
            } else {
            // 當(dāng)鏈表中已經(jīng)有節(jié)點(diǎn)存在時(shí)
            // 注意tail指向的始終是最后一個(gè)節(jié)點(diǎn)
            // 注意head指向的始終是第一個(gè)節(jié)點(diǎn)
            // 因?yàn)槭请p向鏈表，可以從頭部插入新節(jié)點(diǎn)，也可以從尾部插入
            // 這里以從尾部插入為例，將新節(jié)點(diǎn)插入到鏈表最后
            // 首先將新節(jié)點(diǎn)的 prev 指向上一個(gè)節(jié)點(diǎn)，即之前tail指向的位置
                newNode.prev = this.tail
            // 然后前一個(gè)節(jié)點(diǎn)的next（及之前tail指向的節(jié)點(diǎn)）指向新的節(jié)點(diǎn)
            // 此時(shí)新的節(jié)點(diǎn)變成了鏈表的最后一個(gè)節(jié)點(diǎn)
                this.tail.next = newNode
            // 因?yàn)?tail 始終指向的是最后一個(gè)節(jié)點(diǎn)，所以最后修改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) { // 刪除第一個(gè)節(jié)點(diǎn)
                    this.head.next.prev = null
                    this.head = this.head.next
                } else if (position === this.length - 1) { // 刪除最后一個(gè)節(jié)點(diǎn)
                    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)
        }
    }

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