文章首發(fā)于 www.shaotianyu.com
一、數(shù)組和鏈表優(yōu)缺點(diǎn)
1.1、數(shù)組(Array)
1.1.1 數(shù)組的優(yōu)點(diǎn)
線性表的一種。高級(jí)數(shù)據(jù)語(yǔ)言中，對(duì)數(shù)組內(nèi)部的元素類型沒(méi)有嚴(yán)格的要求，這在語(yǔ)言中稱為泛型，可以放入任何單元類型。數(shù)組的底層的硬件實(shí)現(xiàn)，存在一個(gè)內(nèi)存管理器，每當(dāng)申請(qǐng)一個(gè)數(shù)組的時(shí)候，計(jì)算機(jī)會(huì)在內(nèi)存中開(kāi)辟一段連續(xù)的地址，每一個(gè)地址可以通過(guò)內(nèi)存管理器進(jìn)行訪問(wèn)，數(shù)組訪問(wèn)第一個(gè)元素和其他任何一個(gè)元素的時(shí)間復(fù)雜度是相同的，都是O(1)，即常數(shù)級(jí)別。由于數(shù)組可以隨機(jī)訪問(wèn)任何一個(gè)元素，所以它的時(shí)間效率快，這是數(shù)組的優(yōu)勢(shì)之一。
1.1.2 數(shù)組的缺點(diǎn)
數(shù)組的問(wèn)題出現(xiàn)于它增加、刪除某些元素的時(shí)候。
比如現(xiàn)在有個(gè)數(shù)組，要在中間插入一個(gè)元素F，那么元素C、D、E就要相應(yīng)的向后移動(dòng)一個(gè)位置，這樣一來(lái)數(shù)組插入操作的時(shí)間復(fù)雜度趨于O(1)-O(n)之間。
數(shù)組刪除也是同理。
所以在增加、刪除操作比較頻繁的情況下，數(shù)組的缺點(diǎn)就會(huì)顯露出來(lái)。
下面是數(shù)組中各個(gè)操作對(duì)應(yīng)的時(shí)間復(fù)雜度：
| 操作 | 最大時(shí)間復(fù)雜度 |
|------|------------|
| search | O(1) |
| insert | O(n) |
| remove/delete | O(n) |
| append | O(1) |
| prepend | O(1) |
1.2、鏈表(LinkedList)
單鏈表
雙向鏈表
單向循環(huán)鏈表
1.2.1 、鏈表的優(yōu)點(diǎn)
相比于數(shù)組，鏈表在增加節(jié)點(diǎn)和刪除節(jié)點(diǎn)時(shí)候，并不會(huì)引起其他節(jié)點(diǎn)的群移，這樣的話增加、刪除操作的時(shí)間復(fù)雜度為O(1)，下面是單鏈表插入某個(gè)節(jié)點(diǎn)的示意圖，我們可以看到只需要更改當(dāng)前節(jié)點(diǎn)和前置節(jié)點(diǎn)和的next指針，即可完成節(jié)點(diǎn)的插入操作。
下面是單鏈表的節(jié)點(diǎn)插入操作示意圖：
1.2.2 、鏈表的缺點(diǎn)
與數(shù)組相比，在鏈表中訪問(wèn)任一元素的位置，就沒(méi)那么容易了，需要從鏈表的head開(kāi)始，一步步的向后查詢，這種情況下時(shí)間復(fù)雜度為O(1)-O(n)之間。
下面是鏈表中各個(gè)操作對(duì)應(yīng)的時(shí)間復(fù)雜度：
| 操作 | 最大時(shí)間復(fù)雜度 |
|------|------------|
| search | O(n) |
| insert | O(1) |
| remove/delete | O(1) |
| append | O(1) |
| prepend | O(1) |
1.2.3 、跳表
由于鏈表的search操作時(shí)間復(fù)雜度為O(n)，為了彌補(bǔ)鏈表的缺陷，我們可以思考給鏈表增加多個(gè)指針去作為起始指針，這樣的話search某個(gè)節(jié)點(diǎn)就會(huì)更有效率，從而減少search的時(shí)間復(fù)雜度。
由此引出了跳表的思想，而多個(gè)起始指針則晉升為索引的概念，通過(guò)增加維度，以空間換時(shí)間來(lái)進(jìn)行時(shí)間度優(yōu)化，跳表中search的時(shí)間復(fù)雜度為O(logn)。
下面是跳表中一級(jí)索引的示意圖：
二、使用JS實(shí)現(xiàn)鏈表
理解了鏈表的幾種通用形態(tài)，我們可以用js一步步實(shí)現(xiàn)鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu)。
2.1、單鏈表
實(shí)現(xiàn)單鏈表的原理在于，要不斷更新節(jié)點(diǎn)的next指針，使整個(gè)鏈表串聯(lián)起來(lái)。
class Node {
constructor (element) {
this.element = element
this.next = null
}
}
class LinkedList {
constructor () {
// 初始化鏈表長(zhǎng)度
this.length = 0
// 初始化鏈表第一個(gè)節(jié)點(diǎn)
this.head = null
}
append (element) {
let node = new Node(element)
let current
// 鏈表為空情況
if (this.head === null) {
this.head = node
} else {
current = this.head
while (current.next) {
current = current.next
}
current.next = node
}
this.length ++
}
insert (element, point) {
if (point >=0 && point <= this.length) {
let node = new Node(element)
let current = this.head
let previous
let index = 0
if (point === 0) {
node.next = current
this.head = node
} else {
while (index++ < point) {
previous = current
current = current.next
}
previous.next = node
node.next = current
}
this.length++
return true
} else {
return false
}
}
removeAt (point) {
if (point > -1 && point < this.length) {
let current = this.head
let index = 0
let previous
if (point === 0) {
this.head = current.next
} else {
while (index++ < point) {
previous = current
current = current.next
}
previous.next = current.next
}
this.length--
return current.element
} else {
return null
}
}
remove (element) {
let index = this.find(element)
// 刪除后返回已刪除的節(jié)點(diǎn)
return this.removeAt(index)
}
find (element) {
let current = this.head
let index = 0
if (element == current.element){
return 0;
}
while (current.next) {
if(current.element === element) {
return index
}
index++
current = current.next
}
if (element == current.element){
return index;
}
return -1
}
isEmpty () {
return this.length === 0
}
size () {
return this.length
}
print () {
let current = this.head
let result = ''
while (current) {
result += current.element + (current.next ? '->' : '')
current = current.next
}
return result
}
}
let l1 = new LinkedList()
...
2.2、雙向鏈表
實(shí)現(xiàn)雙向鏈表的原理在于，每次更新鏈表要同時(shí)考慮到next和prev兩個(gè)指針，并保證更新指針的指向。
class Node {
constructor (element) {
this.element = element
this.next = null
this.prev = null
}
}
class DoubleLinkedList {
constructor () {
this.length = 0
this.head = null
// 定義尾部節(jié)點(diǎn)
this.tail = null
}
append (element) {
let node = new Node(element)
let tail = this.tail
if (this.head === null) {
this.head = node
this.tail = node
} else {
tail.next = node
node.prev = tail
this.tail = node
}
this.length++
}
insert (element, point) {
if(point >= 0 && point <= this.length) {
let node = new Node(element)
let current = this.head
let tail = this.tail
let index = 0
let previous
if (point === 0) {
if (!this.head) {
this.head = node
this.tail = node
} else {
node.next = current
current.prev = node
this.head = node
}
} else if (point === this.length) {
current = tail
current.next = node
node.prev = current
this.tail = node
} else {
while (index++ < point) {
previous = current
current = current.next
}
// 將原來(lái)的鏈表斷開(kāi)，重新使用指針串接起來(lái)
node.next = current
node.prev = previous
previous.next = node
current.prev = node
}
this.length++
return true
} else {
return false
}
}
removeAt (point) {
if (point > -1 && point < this.length) {
let current = this.head
let index = 0
let previous
let tail = this.tail
if (point === 0) {
// remove第一項(xiàng)的情況
this.head = current.next
if (this.length === 1) {
this.tail = null
} else {
this.head.prev = null
}
} else if (point === this.length -1) {
current = tail
this.tail = current.prev
this.tail.next = null
} else {
while (index++ < point) {
previous = current
current = current.next
}
previous.next = current.next
current.next.prev = previous
}
this.length--
return current.element
} else {
return null
}
}
find (element) {
let current = this.head
let index = 0
if (element == current.element){
return 0;
}
while (current.next) {
if(current.element === element) {
return index
}
index++
current = current.next
}
// 為了保證最后一位被找到
if (element == current.element){
return index;
}
return -1
}
remove (element) {
let index = this.find(element)
return this.removeAt(index)
}
isEmpty () {
return this.length === 0
}
size () {
return this.length
}
print () {
let current = this.head
let result = ''
while (current) {
result += current.element + (current.next ? '->' : '')
current = current.next
}
return result
}
}
let l1 = new DoubleLinkedList()
2.3、單向循環(huán)鏈表
單向循環(huán)鏈表和單鏈表大致相同，唯一區(qū)別是，尾節(jié)點(diǎn)tail的next指針要指向head，使鏈表的頭尾串聯(lián)在一起，形成循環(huán)。
class Node {
constructor (element) {
this.element = element
this.next = null
}
}
class CircleLinkedList {
constructor () {
// 初始化鏈表長(zhǎng)度
this.length = 0
// 初始化鏈表第一個(gè)節(jié)點(diǎn)
this.head = null
}
append (element) {
let node = new Node(element)
let head = this.head
let current
// 鏈表為空情況
if (this.head === null) {
this.head = node
} else {
current = this.head
while (current.next && current.next !== head) {
current = current.next
}
current.next = node
}
// 保持首尾相連
node.next = head
this.length ++
}
insert (element, point) {
if (point >=0 && point <= this.length) {
let node = new Node(element)
let current = this.head
let previous
let index = 0
if (point === 0) {
node.next = current
while (current.next && current.next !== this.head) {
current = current.next
}
this.head = node
current.next = this.head
} else {
while (index++ < point) {
previous = current
current = current.next
}
previous.next = node
// 首尾相連
node.next = current === null ? head : current
}
this.length++
return true
} else {
return false
}
}
removeAt (point) {
if (point > -1 && point < this.length) {
let current = this.head
let index = 0
let previous
if (point === 0) {
this.head = current.next
while (current.next && current.next !== this.head) {
current = current.next
}
current.next = this.head
} else {
while (index++ < point) {
previous = current
current = current.next
}
previous.next = current.next
}
this.length--
return current.element
} else {
return null
}
}
remove (element) {
let index = this.find(element)
// 刪除后返回已刪除的節(jié)點(diǎn)
return this.removeAt(index)
}
find (element) {
let current = this.head
let index = 0
if (element == current.element){
return 0;
}
while (current.next && current.next !== this.head) {
if(current.element === element) {
return index
}
index++
current = current.next
}
if (element == current.element){
return index;
}
return -1
}
isEmpty () {
return this.length === 0
}
size () {
return this.length
}
print () {
let current = this.head
let result = ''
while (current.next && current.next !== this.head) {
result += current.element + (current.next ? '->' : '')
current = current.next
}
result += current.element
return result
}
}
let l1 = new CircleLinkedList()
2.4、雙向循環(huán)鏈表
雙向循環(huán)鏈表和單向循環(huán)原理上大概一致，區(qū)別在于，雙向循環(huán)鏈表同時(shí)擁有2個(gè)指針prev和next，并在head和tail兩個(gè)臨界點(diǎn)進(jìn)行指針更新處理，并保持鏈表的首尾相連。
三、小結(jié)
以上是我對(duì)鏈表數(shù)組相關(guān)數(shù)據(jù)結(jié)構(gòu)的淺薄認(rèn)知，如有紕漏，還望指出～～
以上代碼部分參考了書(shū)籍《javascript數(shù)據(jù)結(jié)構(gòu)和算法》～～
??????????
