數(shù)組
數(shù)組——最簡(jiǎn)單的內(nèi)存數(shù)據(jù)結(jié)構(gòu)
數(shù)組存儲(chǔ)一系列同一種數(shù)據(jù)類型的值。（ Javascript 中不存在這種限制）
對(duì)數(shù)據(jù)的隨機(jī)訪問，數(shù)組是更好的選擇，否則幾乎可以完全用 「鏈表」 來代替
在很多編程語言中，數(shù)組的長(zhǎng)度是固定的，當(dāng)數(shù)組被填滿時(shí)，再要加入新元素就很困難。Javascript 中數(shù)組不存在這個(gè)問題。
但是 Javascript 中的數(shù)組被實(shí)現(xiàn)成了對(duì)象，與其他語言相比，效率低下。
數(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ù)組的開頭，并返回該數(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è)方法沒有返回值，沒有辦法中止或者跳出 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ù)組元素的索引，沒有找到則返回 -1
lastIndexOf 返回在數(shù)組中搜索到的與給定參數(shù)相等的元素的索引里最大的值，沒有找到則返回 -1
slice 傳入索引值，將數(shù)組里對(duì)應(yīng)索引范圍內(nèi)的元素（淺復(fù)制原數(shù)組中的元素）作為新數(shù)組返回（原始數(shù)組不會(huì)被改變）
splice 刪除或替換現(xiàn)有元素或者原地添加新的元素來修改數(shù)組,并以數(shù)組形式返回被修改的內(nèi)容(改變?cè)瓟?shù)組)
toString 將數(shù)組作為字符串返回
valueOf 和 toString 類似，將數(shù)組作為字符串返回
棧
棧是一種遵循后進(jìn)先出（LIFO）原則的有序集合，新添加或待刪除的元素都保存在棧的同一端，稱作棧頂，另一端就叫棧底。在棧里，新元素都靠近棧頂，舊元素都接近棧底。
通俗來講，就是你向一個(gè)桶里放書本或者盤子，你要想取出最下面的書或者盤子，你必須要先把上面的都先取出來。
棧也被用在編程語言的編譯器和內(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，也稱為先來先服務(wù))原則的一組有序的項(xiàng)。隊(duì)列在尾部添加新
元素，并從頂部移除元素。添加的元素必須排在隊(duì)列的末尾。
生活中常見的就是排隊(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)其他元素，但是需要使用指針。訪問元素每次都需要從表頭開始查找。
代碼實(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
