2020-5-28 前端達人
數(shù)組——最簡單的內存數(shù)據(jù)結構
數(shù)組存儲一系列同一種數(shù)據(jù)類型的值。（ Javascript 中不存在這種限制）
對數(shù)據(jù)的隨機訪問，數(shù)組是更好的選擇，否則幾乎可以完全用 「鏈表」 來代替
在很多編程語言中，數(shù)組的長度是固定的，當數(shù)組被填滿時，再要加入新元素就很困難。Javascript 中數(shù)組不存在這個問題。
但是 Javascript 中的數(shù)組被實現(xiàn)成了對象，與其他語言相比，效率低下。
數(shù)組的一些核心方法
方法 描述
push 方法將一個或多個元素添加到數(shù)組的末尾，并返回該數(shù)組的新長度。(改變原數(shù)組)
pop 方法從數(shù)組中刪除最后一個元素，并返回該元素的值。(改變原數(shù)組)
shift 方法從數(shù)組中刪除第一個元素，并返回該元素的值，如果數(shù)組為空則返回 undefined 。(改變原數(shù)組)
unshift 將一個或多個元素添加到數(shù)組的開頭，并返回該數(shù)組的新長度(改變原數(shù)組)
concat 連接兩個或多個數(shù)組，并返回結果（返回一個新數(shù)組，不影響原有的數(shù)組。）
every 對數(shù)組中的每個元素運行給定函數(shù)，如果該函數(shù)對每個元素都返回 true，則返回 true。若為一個空數(shù)組，，始終返回 true。 （不會改變原數(shù)組，[].every(callback)始終返回 true）
some 對數(shù)組中的每個元素運行給定函數(shù)，如果任一元素返回 true，則返回 true。若為一個空數(shù)組，，始終返回 false。（不會改變原數(shù)組，）
forEach 對數(shù)組中的每個元素運行給定函數(shù)。這個方法沒有返回值，沒有辦法中止或者跳出 forEach() 循環(huán)，除了拋出一個異常（foreach不直接改變原數(shù)組，但原數(shù)組可能會被 callback 函數(shù)該改變。）
map 對數(shù)組中的每個元素運行給定函數(shù)，返回每次函數(shù)調用的結果組成的數(shù)組（map不直接改變原數(shù)組，但原數(shù)組可能會被 callback 函數(shù)該改變。）
sort 按照Unicode位點對數(shù)組排序，支持傳入指定排序方法的函數(shù)作為參數(shù)（改變原數(shù)組）
reverse 方法將數(shù)組中元素的位置顛倒，并返回該數(shù)組（改變原數(shù)組）
join 將所有的數(shù)組元素連接成一個字符串
indexOf 返回第一個與給定參數(shù)相等的數(shù)組元素的索引，沒有找到則返回 -1
lastIndexOf 返回在數(shù)組中搜索到的與給定參數(shù)相等的元素的索引里最大的值，沒有找到則返回 -1
slice 傳入索引值，將數(shù)組里對應索引范圍內的元素（淺復制原數(shù)組中的元素）作為新數(shù)組返回（原始數(shù)組不會被改變）
splice 刪除或替換現(xiàn)有元素或者原地添加新的元素來修改數(shù)組,并以數(shù)組形式返回被修改的內容(改變原數(shù)組)
toString 將數(shù)組作為字符串返回
valueOf 和 toString 類似，將數(shù)組作為字符串返回
棧是一種遵循后進先出（LIFO）原則的有序集合，新添加或待刪除的元素都保存在棧的同一端，稱作棧頂，另一端就叫棧底。在棧里，新元素都靠近棧頂，舊元素都接近棧底。
通俗來講，就是你向一個桶里放書本或者盤子，你要想取出最下面的書或者盤子，你必須要先把上面的都先取出來。
棧也被用在編程語言的編譯器和內存中保存變量、方法調用等，也被用于瀏覽器歷史記錄 (瀏覽器的返回按鈕)。
代碼實現(xiàn)
// 封裝棧隊列是遵循先進先出(FIFO，也稱為先來先服務)原則的一組有序的項。隊列在尾部添加新
元素，并從頂部移除元素。添加的元素必須排在隊列的末尾。
生活中常見的就是排隊
代碼實現(xiàn)
function Queue() {代碼實現(xiàn)
鏈表——存儲有序的元素集合，但在內存中不是連續(xù)放置的。
鏈表(單向鏈表)中的元素由存放元素本身「data」 的節(jié)點和一個指向下一個「next」 元素的指針組成。牢記這個特點
相比數(shù)組，鏈表添加或者移除元素不需要移動其他元素，但是需要使用指針。訪問元素每次都需要從表頭開始查找。
代碼實現(xiàn):
單向鏈表
表頭、表尾 和 存儲數(shù)據(jù)的 節(jié)點，其中節(jié)點包含三部分：一個鏈向下一個元素的next， 另一個鏈向前一個元素的prev 和存儲數(shù)據(jù)的 data。牢記這個特點
function doublyLinkedList() {
this.head = null // 表頭：始終指向第一個節(jié)點，默認為 null
this.tail = null // 表尾：始終指向最后一個節(jié)點，默認為 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) {
// 當插入的節(jié)點為鏈表的第一個節(jié)點時
// 表頭和表尾都指向這個節(jié)點
this.head = newNode
this.tail = newNode
} else {
// 當鏈表中已經(jīng)有節(jié)點存在時
// 注意tail指向的始終是最后一個節(jié)點
// 注意head指向的始終是第一個節(jié)點
// 因為是雙向鏈表，可以從頭部插入新節(jié)點，也可以從尾部插入
// 這里以從尾部插入為例，將新節(jié)點插入到鏈表最后
// 首先將新節(jié)點的 prev 指向上一個節(jié)點，即之前tail指向的位置
newNode.prev = this.tail
// 然后前一個節(jié)點的next（及之前tail指向的節(jié)點）指向新的節(jié)點
// 此時新的節(jié)點變成了鏈表的最后一個節(jié)點
this.tail.next = newNode
// 因為 tail 始終指向的是最后一個節(jié)點，所以最后修改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) { // 刪除第一個節(jié)點
this.head.next.prev = null
this.head = this.head.next
} else if (position === this.length - 1) { // 刪除最后一個節(jié)點
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」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權協(xié)議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/brand2014/java/article/details/106134844