2020-5-28 前端達人
數組——最簡單的內存數據結構
數組存儲一系列同一種數據類型的值。（ 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）原則的有序集合，新添加或待刪除的元素都保存在棧的同一端，稱作棧頂，另一端就叫棧底。在棧里，新元素都靠近棧頂，舊元素都接近棧底。
通俗來講，就是你向一個桶里放書本或者盤子，你要想取出最下面的書或者盤子，你必須要先把上面的都先取出來。
棧也被用在編程語言的編譯器和內存中保存變量、方法調用等，也被用于瀏覽器歷史記錄 (瀏覽器的返回按鈕)。
代碼實現
// 封裝棧隊列是遵循先進先出(FIFO，也稱為先來先服務)原則的一組有序的項。隊列在尾部添加新
元素，并從頂部移除元素。添加的元素必須排在隊列的末尾。
生活中常見的就是排隊
代碼實現
function Queue() {代碼實現
鏈表——存儲有序的元素集合，但在內存中不是連續放置的。
鏈表(單向鏈表)中的元素由存放元素本身「data」 的節點和一個指向下一個「next」 元素的指針組成。牢記這個特點
相比數組，鏈表添加或者移除元素不需要移動其他元素，但是需要使用指針。訪問元素每次都需要從表頭開始查找。
代碼實現:
單向鏈表
表頭、表尾 和 存儲數據的 節點，其中節點包含三部分：一個鏈向下一個元素的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