前言
鏈表是最基礎的動態數據結構。
動態數組、棧、隊列，底層都是依託靜態數組，靠 resize 解決固定容量問題。它們所謂的動態，是從用戶的角度上來看的。
鏈表是真正的動態數據結構，它是數據結構中的一個重點，也有可能是一個難點吧。它是最簡單的一種動態數據結構，其它更高級的動態數據結構有二分搜索樹、Trie、平衡二叉樹、AVL、紅黑樹等等。
熟悉了最簡單的動態數據結構，那麼對於更高級的也會比較容易掌握了。
還是那句老話：光看文章能夠掌握兩成，動手敲代碼、動腦思考、畫圖才可以掌握八成。源碼倉庫
不要完美主義。掌握好“度”。
太過於追求完美會把自己逼的太緊，會產生各種焦慮的心態，最後甚至會懷疑自己，溫故而知新，不要停止不前，掌握好這個度，不存在你把那些你認為完全掌握了，然後就成了某一個領域的專家，相反一旦你產生很濃厚的厭惡感，那麼就意味著你即將會放棄或者已經選擇了放棄，雖然你之前想把它做到 100 分，但是由於你的放棄讓它變為 0 分。
學習本著自己的目標去。不要在學的過程中偏離了自己的目標。要分清主次。
難的東西，你可以慢慢的回頭看一看。那樣才會更加的柳暗花明，更能提升自己的收穫。
鏈表（LinkNode）
對於鏈表來說它涉及到了計算機領域一個非常重要的概念，更深入的理解引用（或者指針），這個概念和內存相關，在 JS 裡面不需要手動的管理內存，但是對鏈表這種數據結構更加深入的理解，可以讓你對 引用、指針甚至計算機系統中和內存管理相關很多話題有更加深入的認識。
鏈表本身也是有它非常清晰的遞歸結構的，只不過由於鏈表這種數據結構它本身是一種線性的數據結構，所以依然可以非常容易的使用循環的方式來對鏈表進行操作，但是鏈表本身由於它天生也是具有這種遞歸結構的性質，所以它也能讓你更加深入的理解遞歸機制相應的這種數據結構，在學習更加複雜的數據結構的時候，對遞歸這種邏輯機制深入的理解是必不可缺的。
鏈表這種數據結構本身就具有功能性，它可以用來組成更加複雜的數據結構，比如 圖結構、hash 表、棧(鏈表版)、隊列(鏈表版)，所以他可以輔助組成其它數據結構。
先簡單認識一下鏈表
數據存儲在“節點”（Node）中，把數據存在一種單獨的結構中，這個結構通常管它叫做節點，對於鏈表節點來說他通常只有兩部分，一部分就是存儲真正的數據，另一部分存儲的是當前節點的下一個節點，鏈表其實就像一個火車，每一個節點都是一節車廂，在車廂中存儲數據，而車廂和車廂之間還會進行連接，以使得這些數據是整合在一起的，這樣用戶可以方便的在所有的這些數據上進行查詢等等其它的操作，數據與數據之間連接就是用下面的這個 next 來完成的。
class Node {
e; //Element
next; //Node
}鏈表的優缺點
鏈表的優點：
真正的動態，不需要處理固定容量的問題，它不像靜態數組那樣一下子 new 出來一片空間，也根本不需要考慮這個空間是不是不夠用，也根本不用去考慮這個空間是不是開多了。
對於鏈表來說，你需要多少個數據。你就可以生成多少個節點，把它們掛接起來了，這就是所謂的動態。
鏈表的缺點：
和數組相比，它喪失了隨機訪問的能力。不能像數組那樣給一個索引就能直接訪問對應索引位置的元素，這是因為從底層機制上數組所開闢的空間在內存裡是連續分佈的，所以才能夠直接去向索引對應的偏移計算出相應的數據所存儲的內存地址，然後就能夠直接用O(1)的複雜度取出這個元素，但是鏈表不同，鏈表由於是靠 next 一層一層連接的，所以在計算機的底層，每一個節點他所在的內存的位置是不同的，只能夠靠這個 next 來一層一層的找到這個元素，這就是鏈表最大的缺點。
數組與鏈表的對比
數組
數組最好永遠索引有語意的情況，如 scores[2]
最大的優點：支持快速查詢
鏈表
鏈表不適合用於索引有語意的情況。
最大的優點：動態存儲。
對比
數組也可以沒有語意，並不是所有的時候索引是有語意的，也並不是所有有語意的這樣的一個標誌就適合做索引，如身份證號，將一個靜態數組改變為一個動態數組，就是在應付不方便使用索引的時候有關數據存儲的問題，對於這樣的存儲數據的需求使用鏈表是更合適的，因為鏈表最大的優點是動態存儲。
要清楚什麼時候使用數組這樣的靜態數據結構，什麼時候使用鏈表這類的動態數據結構。
簡單的鏈表實現-MyLinkedList
class MyLinkedListNode {
constructor(element = null, next = null) {
this.element = element;
this.next = next;
}
// toString 2018-10-20-jwl
toString() {
return this.element.toString();
}
}
class MyLinkedList {
constructor() {}
}封裝鏈表
在鏈表中進行添加、插入操作
鏈表是通過節點來裝載元素，並且節點和節點之間會進行連接。如果想訪問這條鏈表中所有的節點，那麼就必須把鏈表的頭給存儲起來，通常這個鏈表的頭叫做的 head，應該說在MyLinkedList中應該有一個變量指向鏈表中的第一個節點。
給自定義數組添加元素是從數組尾部開始添加，給鏈表添加元素是從數組頭部開始添加，因為自定義數組有維護一個 size，這個 size 指向的是下一個待添加元素的位置，所以你直接將 size 做索引直接賦值即可，有 size 這個變量在跟蹤數組的尾巴，而對於鏈表來說 有設置一個鏈表的頭這樣的一個變量，也就是說有一個變量在跟蹤鏈表的頭，並沒有一個變量去跟蹤鏈表的尾巴，所以在鏈表頭部添加元素是非常方便。
添加操作原理將一個新的元素掛接到鏈表頭部，同時不破壞現在鏈表的這個結構，添加一個新元素 666，它的名字叫 node，就只需要使用 node.next = head，也就是將新添加的元素的 next 指向鏈表的頭，這個時候新添加的元素也成為新的鏈表頭，也就是head = node，這樣 head 就會指向新的元素 666，也就是 node 這個節點，如此一來就完成了將 node 這個節點插入了整個鏈表的頭部，node 這個變量是在一個函數中聲明的，所以函數結束之後這個變量的作用域也就結束了，鏈表的 head 也等於 node，鏈表中就新增了一個新元素。
在鏈表頭部添加元素非常簡單，只需要創建節點，讓節點的 next 指向 head，然後讓 head 重新指向這個節點，也就是讓 head 變成新的元素，因為鏈表是從頭部添加元素的。
在鏈表中間添加元素，定義一個 prev 的變量指向中間元素的前一個元素，然後讓新增加的元素這樣，node.next = prev.next，之後這樣，prev.next = node，這樣一來就在 prev 這個元素和原本 prev 的下一個元素之間插入了一個新元素，叫做 node，整個過程就是將 prev 的 next(下一個元素)的引用傳遞給新元素的 next(下一個元素)，然後將 prev 的 next(下一個元素)變更為這個新元素，最後就將新元素插入到中間了。這個過程的關鍵是找到待添加的節點的前一個節點，這個就是 prev 變量要做的事情。
在鏈表的操作中很多時候順序非常重要，如在鏈表中插入一個元素，在指定的元素後面插入一個元素，並且不影響整個鏈表結構，和在鏈表中間添加元素一樣，把原本的node.next = prev.next和prev.next = node的順序變一下，prev.next = node在前，node.next = prev.next 在後，這樣一來邏輯就不成立了，鏈表不僅斷開了，而且新節點的 next 指向的是自己，死循環了，所以一樣的代碼，順序顛倒了，得到的結果就是錯誤的。
在鏈表的 index(0-based)位置添加元素 e，通過索引來操作鏈表，在鏈表中不是一個常用的操作，因為在選擇使用鏈表的時候通常就選擇不使用索引了，這個需求在面試考題中有很大出現的概率喲，不過這種需求它的主要作用更多是一個練習吧。
代碼實現
(class: MyLinkedList)
MyLinkedList
class MyLinkedListNode {
constructor(element = null, next = null) {
this.element = element;
this.next = next;
}
// toString 2018-10-20-jwl
toString() {
return this.element.toString();
}
}
class MyLinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// 獲取鏈表中實際的節點個數
getSise() {
return this.size;
}
// 判斷鏈表是否為空
isEmpty() {
return this.size === 0;
}
// 在鏈表頭添加節點
addFirst(element) {
let node = new MyLinkedListNode(element, null);
node.next = this.head;
this.head = node;
this.size++;
}
// 在鏈表指定索引處插入節點
insert(index, element) {
if (index < 0 || index > this.size) {
throw new Error('add error. index < 0 or index > size');
}
if (index === 0) {
this.addFirst(element);
} else {
// 第一個prev就是head
let prev = this.head;
// 變量i(索引)之所以要從 1 開始，因為索引為0的那個節點就是head，循環就不需要從0開始了，
// 小於index是因為要找到指定索引位置的前一個節點
// 循環是因為 要繼續找到指定索引處的節點的前一個節點
for (var i = 1; i < index; i++) {
// 不停的切換引用，直到找到對應索引處節點的下一個節點
prev = prev.next;
}
let node = new MyLinkedListNode(element, null);
node.next = prev.next;
prev.next = node;
this.size++;
}
}
// 擴展：在鏈表最後一個節點的位置添加節點
addLast(element) {
this.insert(this.size, element);
}
}給鏈表設立虛擬頭節點
在鏈表中進行指定索引處插入元素時，對鏈表頭插入元素與對鏈表其它位置插入元素的邏輯有區別，所以就導致每次操作都需要對索引進行判斷，如果你是在索引 0 的位置插入元素，那麼就沒有 prev(前一個元素)，自然就不可以使用node.next = prev.next和prev.next = node了，那時候你可以直接使用node.next = head和head = node，不過已經有了向鏈表頭添加元素的方法了，所以向頭部插入元素時根本就不需要這麼做，這時候可以通過給鏈表設立虛擬頭節點來解決這個問題。
為什麼對鏈表頭插入元素那麼特殊？
因為插入元素時，必需要找到該索引位置的節點之前的一個節點(prev)，而鏈表頭(head)之前並沒有任何節點，所以邏輯上就會特殊一些。
不過在鏈表的具體實現中有一個非常常用的技巧，可以把鏈表頭的這種特殊的操作與其它的操作一起統一起來，其實這個方法的想法很簡單，既然它沒有鏈表頭之前的節點，那就自己造一個鏈表頭之前的節點，這個鏈表頭之前的節點不會用來存儲任何元素，存儲的數據為空，這個空節點就稱之為整個鏈表頭的 head，也可以叫它 dummyHead，因為它就是一個假的 head，它也是為鏈表設立的虛擬頭節點，這樣一來 鏈表的第一個元素就是 dummyHead 的 next 所對應的那個節點，因為 dummyHead 這個位置的元素是根本不存在的，對用戶來講也是根本沒有意義的，這只是為了編寫邏輯方便而出現的一個虛擬的頭節點，所以一個這樣的內部機制對用戶來說也是不可見的，用戶不知道鏈表中有沒有虛擬的頭節點，這和自定義的循環隊列有點像，自定義循環隊列中有一個不可用的空間，有意識地去浪費一個空間，為了編寫邏輯更加的方便，從而也讓性能在整體上得到了提升。
有了 dummyHead 之後就不需要處理頭節點這個特殊的操作，因為當你在頭部插入元素時，可以這樣node.next = dummyHead.next、dummyHead.next = node ，這樣你就解決了每次插入時都要進行一次邏輯判斷了，這樣一來就說明了鏈表中所有的節點都有前一個節點了，在初始的時候 dummyHead 指向的是索引為 0 的元素前一個位置的節點。
鏈表操作的實際原理
在沒有使用虛擬頭節點之前，一直都是在鏈表頭 head 這個地方不停的添加節點，然後將 head 這個變量不停的指向新添加的節點 node.next = head.next;head = node;。
在使用了虛擬頭節點之後，一直是在鏈表虛擬頭 dummyHead 這個地方後面一個位置不停的插入新節點，dummyHead 從未變動過，永遠在鏈表的第一個位置，node.next = dummyHead.next; dummyHead.next = node;，但是dummyHead.next才是鏈表中第一個實際記錄的節點，用戶會不知道虛擬節點的存在，因為 dummyHead 並不算在鏈表的實際節點中，也就是 size 中不會維護 dummyHead，dummyHead 的存在是為了維護一致的插入操作。
代碼實現
(class: MyLinkedList)
MyLinkedList
class MyLinkedListNode {
constructor(element = null, next = null) {
this.element = element;
this.next = next;
}
// toString 2018-10-20-jwl
toString() {
return this.element.toString();
}
}
class MyLinkedList {
constructor() {
this.dummyHead = new MyLinkedListNode(null, null);
this.size = 0;
}
// 獲取鏈表中實際的節點個數
getSise() {
return this.size;
}
// 判斷鏈表是否為空
isEmpty() {
return this.size === 0;
}
// 在鏈表頭添加節點
addFirst(element) {
// let node = new MyLinkedListNode(element, null);
// node.next = this.head;
// this.head = node;
// this.size ++;
// 改用虛擬頭節點
insert(0, element);
}
// 在鏈表指定索引處插入節點
insert(index, element) {
if (index < 0 || index > this.size) {
throw new Error('add error. index < 0 or index > size');
}
// 第一個prev就是dummyHead
let prev = this.dummyHead;
// 之前變量i(索引)之所以要從 1 開始，因為索引為0的那個節點就是head，循環就不需要從0開始了，
// 現在索引之所以要從 0 開始， 因為初始化時 多增加了一個虛擬的頭節點
// （因為這個索引為0的節點並不是dummyHead，dummyHead這個節點並不記錄為鏈表中的實際節點），
// 小於index是因為要找到指定索引位置的前一個節點
// 循環是因為 要繼續找到指定索引處的節點的前一個節點
for (var i = 0; i < index; i++) {
// 不停的切換引用，直到找到對應索引處節點的下一個節點
prev = prev.next;
}
let node = new MyLinkedListNode(element, null);
node.next = prev.next;
prev.next = node;
this.size++;
}
// 擴展：在鏈表最後一個節點的位置添加節點
addLast(element) {
this.insert(this.size, element);
}
}在鏈表中進行遍歷、查詢、修改操作
如果要找指定索引元素的前一個節點，那麼就要從dummyHead開始遍歷，如果要找指定索引元素的那個節點，那麼就要從dummyHead.next開始遍歷。
代碼實現
(class: MyLinkedList, class: Main)
MyLinkedList
class MyLinkedListNode {
constructor(element = null, next = null) {
this.element = element;
this.next = next;
}
// toString 2018-10-20-jwl
toString() {
return this.element.toString();
}
}
class MyLinkedList {
constructor() {
this.dummyHead = new MyLinkedListNode(null, null);
this.size = 0;
}
// 獲取鏈表中實際的節點個數
getSize() {
return this.size;
}
// 判斷鏈表是否為空
isEmpty() {
return this.size === 0;
}
// 在鏈表頭添加節點
addFirst(element) {
// let node = new MyLinkedListNode(element, null);
// node.next = this.head;
// this.head = node;
// this.size ++;
// 改用虛擬頭節點
this.insert(0, element);
}
// 在鏈表指定索引處插入節點
insert(index, element) {
if (index < 0 || index > this.size) {
throw new Error('add error. index < 0 or index > size');
}
// 第一個prev就是dummyHead
let prev = this.dummyHead;
// 之前變量i(索引)之所以要從 1 開始，因為索引為0的那個節點就是head，循環就不需要從0開始了，
// 現在索引之所以要從 0 開始， 因為初始化時 多增加了一個虛擬的頭節點
// （因為這個索引為0的節點並不是dummyHead，dummyHead這個節點並不記錄為鏈表中的實際節點），
// 小於index是因為要找到指定索引位置的前一個節點
// 循環是因為 要繼續找到指定索引處的節點的前一個節點
for (var i = 0; i < index; i++) {
// 不停的切換引用，直到找到對應索引處節點的下一個節點
prev = prev.next;
}
let node = new MyLinkedListNode(element, null);
node.next = prev.next;
prev.next = node;
this.size++;
}
// 擴展：在鏈表最後一個節點的位置添加節點
addLast(element) {
this.insert(this.size, element);
}
// 獲取指定索引位置的元素
get(index) {
// 判斷索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 如果你要找指定索引節點的前一個節點 就使用dummyHead
// 如果你要找到指定索引節點 就使用dummyHead.next
// 因為duumyHead並不是第一個節點，因為它是一個虛擬節點，
// dummyHead.next才是真正被記錄的第一個節點。
let node = this.dummyHead.next;
for (var i = 0; i < index; i++) {
node = node.next;
}
return node.element;
}
// 獲取頭節點的元素
getFirst() {
return this.get(0);
}
// 獲取尾節點的元素
getLast() {
return this.get(this.size - 1);
}
// 設置指定索引位置的元素值
set(index, element) {
// 判斷索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 從第一個真正被記錄的節點開始，從0開始
let node = this.dummyHead.next;
// 索引為 0 時，實際上切換到的節點 它的索引為 1
// i < index ，當索引為 index-1 時， 實際上切換到的節點 它的索引為index
for (let i = 0; i < index; i++) {
// 每一次切換 都只是改變引用
// 不的在鏈表中找下一個節點
node = node.next;
}
node.element = element;
}
// 所有節點中是否有包含該元素
contains(element) {
let node = this.dummyHead;
while (node.next !== null) {
if (node.next.element === element) return true;
// 不停的向下切換
node = node.next;
}
return false;
}
// 輸出鏈表中的信息
// @Override toString 2018-10-21-jwl
toString() {
let arrInfo = `LinkedList: size = ${this.size}，\n`;
arrInfo += `data = front [`;
let node = this.dummyHead.next;
while (node.next !== null) {
arrInfo += `${node.element}->`;
node = node.next;
}
arrInfo += 'NULL] tail';
// 在頁面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}Main
class Main {
constructor () {
/this.alterLine("MyLinkedList Area");
let mylinkedList = new MyLinkedList();
for (let i = 1; i <= 5 ; i++) {
mylinkedList.addFirst(i);
console.log(mylinkedList.toString());
}
mylinkedList.insert(2, 88888);
console.log(mylinkedList.toString());
}
// 將內容顯示在頁面上
show (content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割線
alterLine (title) {
let line = `--------------------${title}----------------------`
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}在鏈表中進行刪除操作
鏈表元素的刪除
假設要刪除索引為 2 位置的元素就是要索引為 2 位置的元素的前一個元素，還要索引為 2 位置的元素的後一個元素，讓前一個元素的 next 等於後一個元素，也就是前一個元素的 next 等於索引為 2 的元素的 next。
也就是讓 prev 指向待刪除的那個節點的前一個節點，prev 這個節點的 next 就是要刪除的那個節點 delNode，然後讓prev.next = delNode.next，這樣就讓待刪除的那個節點的前一個節點的 next，也就是直接指向了待刪除的那個節點的後一個節點了，然後讓delNode.next = null 就完成了刪除，千萬不要這樣delNode = delNode.next，這個並不是刪除，而是將待刪除節點的引用指向了下一個節點，通過設置為 null 才是真正的與當前鏈表脫離關係。
代碼實現
(class: MyLinkedList, class: Main)
MyLinkedList
class MyLinkedListNode {
constructor(element = null, next = null) {
this.element = element;
this.next = next;
}
// toString 2018-10-20-jwl
toString() {
return this.element.toString();
}
}
class MyLinkedList {
constructor() {
this.dummyHead = new MyLinkedListNode(null, null);
this.size = 0;
}
// 獲取鏈表中實際的節點個數
getSize() {
return this.size;
}
// 判斷鏈表是否為空
isEmpty() {
return this.size === 0;
}
// 在鏈表頭添加節點
addFirst(element) {
// let node = new MyLinkedListNode(element, null);
// node.next = this.head;
// this.head = node;
// this.size ++;
// 改用虛擬頭節點
this.insert(0, element);
}
// 在鏈表指定索引處插入節點
insert(index, element) {
if (index < 0 || index > this.size) {
throw new Error('add error. index < 0 or index > size');
}
// 第一個prev就是dummyHead
let prev = this.dummyHead;
// 之前變量i(索引)之所以要從 1 開始，因為索引為0的那個節點就是head，循環就不需要從0開始了，
// 現在索引之所以要從 0 開始， 因為初始化時 多增加了一個虛擬的頭節點
// （因為這個索引為0的節點並不是dummyHead，dummyHead這個節點並不記錄為鏈表中的實際節點），
// 小於index是因為要找到指定索引位置的前一個節點
// 循環是因為 要繼續找到指定索引處的節點的前一個節點
for (var i = 0; i < index; i++) {
// 不停的切換引用，直到找到對應索引處節點的下一個節點
prev = prev.next;
}
let node = new MyLinkedListNode(element, null);
node.next = prev.next;
prev.next = node;
this.size++;
}
// 擴展：在鏈表最後一個節點的位置添加節點
addLast(element) {
this.insert(this.size, element);
}
// 獲取指定索引位置的元素
get(index) {
// 判斷索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 如果你要找指定索引節點的前一個節點 就使用dummyHead
// 如果你要找到指定索引節點 就使用dummyHead.next
// 因為duumyHead並不是第一個節點，因為它是一個虛擬節點，
// dummyHead.next才是真正被記錄的第一個節點。
let node = this.dummyHead.next;
for (var i = 0; i < index; i++) {
node = node.next;
}
return node.element;
}
// 獲取頭節點的元素
getFirst() {
return this.get(0);
}
// 獲取尾節點的元素
getLast() {
return this.get(this.size - 1);
}
// 設置指定索引位置的元素值
set(index, element) {
// 判斷索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 從第一個真正被記錄的節點開始，從0開始
let node = this.dummyHead.next;
// 索引為 0 時，實際上切換到的節點 它的索引為 1
// i < index ，當索引為 index-1 時， 實際上切換到的節點 它的索引為index
for (let i = 0; i < index; i++) {
// 每一次切換 都只是改變引用
// 不的在鏈表中找下一個節點
node = node.next;
}
node.element = element;
}
// 所有節點中是否有包含該元素
contains(element) {
let node = this.dummyHead;
while (node.next !== null) {
if (node.next.element === element) return true;
// 不停的向下切換
node = node.next;
}
return false;
}
// 刪除指定索引位置的節點
remove(index) {
// 驗證索引的合法性
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index > this.size');
}
let node = this.dummyHead;
for (let i = 0; i < index; i++) {
node = node.next;
}
// 待刪除的節點
let delNode = node.next;
// 給待刪除那個節點的前一個的節點的next引用替換為
// 但刪除的這個節點的next
node.next = delNode.next;
// 或者這樣也行
// node.next = node.next.next;
// 臨時存儲待刪除的那個節點裡的元素
let element = delNode.element;
// 清空 待刪除的節點
delNode = null;
this.size--;
return element;
}
// 擴展：移除鏈表頭的元素
removeFirst() {
return this.remove(0);
}
// 擴展：移除鏈表尾部的元素
removeLast() {
return this.remove(this.size - 1);
}
// 輸出鏈表中的信息
// @Override toString 2018-10-21-jwl
toString() {
let arrInfo = `LinkedList: size = ${this.size}，\n`;
arrInfo += `data = front [`;
let node = this.dummyHead.next;
while (node.next !== null) {
arrInfo += `${node.element}->`;
node = node.next;
}
arrInfo += 'NULL] tail';
// 在頁面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}Main
class Main {
constructor() {
this.alterLine('MyLinkedList Area');
let mylinkedList = new MyLinkedList();
for (let i = 1; i <= 5; i++) {
mylinkedList.addFirst(i);
console.log(mylinkedList.toString());
}
mylinkedList.insert(2, 88888);
console.log(mylinkedList.toString());
mylinkedList.remove(2);
console.log(mylinkedList.toString());
mylinkedList.removeFirst();
console.log(mylinkedList.toString());
mylinkedList.removeLast();
console.log(mylinkedList.toString());
}
// 將內容顯示在頁面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割線
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}鏈表的時間複雜度分析
增：O(n)：在只對鏈表頭進行操作時為O(1)
刪：O(n)：在只對鏈表頭進行操作時為O(1)
改：O(n)
查：O(n)：只查鏈表頭的元素時為O(1)
鏈表增刪改查的時間複雜度
整體上要比數組增刪改查的時間複雜度要差，因為數組有一個優勢，你有索引的話你就可以快速訪問，而鏈表沒有這樣的優勢但是鏈表的優勢是，如果你只對鏈表頭進行增刪的操作，那麼它的時間複雜度是 O(1)級別的，而且它整體是動態的，所以不會大量的浪費內存空間。鏈表適合做的事情是不去修改、也不去查任意的元素，就算查，也只能查鏈表頭的元素，查的時候，只有那樣才是 O(1)級別的時間複雜度，並且增加刪除的時候只對鏈表頭進行操作，只有在這種時候才會和數組整體的時間複雜度是一樣的，不過鏈表整體是動態的，不會去大量的浪費內存空間，所以它具有一定的優勢。
鏈表還有諸多的改進的方式，所以應用鏈表在一些情況下仍然是有它的優勢的，最最重要的是 鏈表本身是一種最最基礎的動態數據結構，對這種動態數據結構要深刻的理解和掌握，對於學習更重要的動態數據結構是有巨大的幫助，比如說二叉樹、平衡二叉樹、AVL、紅黑樹等等。
添加操作 O(n)
addLast(e)：O(n)
會從頭遍歷到尾，找到最後一個節點之後才能添加元素
addFirst(e)：O(1)
直接從頭部添加元素
insert(index, e)：O(n/2) = O(n)
會去遍歷鏈表中每一個節點，檢索到合適的位置才會添加這個元素。
刪除操作 O(n)
removeLast()：O(n)
會去遍歷鏈表中每一個節點，找到最後一個節點後才會刪除
removeFirst()：O(1)
直接從頭部刪除這個節點
remove(index)：O(n/2) = O(n)
會去遍歷鏈表中每一個節點，檢索到合適的位置才會移除這個元素
修改操作 O(n)
set(index, e)：O(n)
會去遍歷鏈表中每一個節點，找到了合適位置的節點後，才會修改元素
查找操作 O(n)
get(index)：O(n)
會去遍歷鏈表中每一個節點，找到了合適位置的節點後，返回這個元素。
contains(e)：O(n)
會去遍歷鏈表中每一個節點，返回 是否有相同元素的 bool 值。
find(e)：O(n)
這個方法對鏈表來說是沒有用的，就算你拿到了那個索引你也不能快速訪問。
總結
如果剛接觸鏈表，對鏈表不熟悉，然後很多這種操作在腦子裡不能非常快的反應出來，不清楚他的意義是什麼，那你可以使用紙筆來稍微畫一下，每一步程序邏輯的執行意味著當前這個鏈表變成了什麼樣子，這個過程能夠幫助你更加深入的理解程序，包括在調試的時候來看你的程序到底為什麼出了錯誤時，非常非常有幫助的，不要犯懶，為了更加深入的理解你的程序，不能只盯著你的代碼去想，一定要寫寫畫畫，必要的時候甚至根據你的程序進行具體的調試，這些都是非常重要非常有幫助的。
拓展
使用鏈表來實現棧
對鏈表進行添加操作時，時間複雜度為O(n)，但是在只對鏈表頭進行操作時為O(1)
對鏈表進行刪除操作時，時間複雜度為O(n)，但是在只對鏈表頭進行操作時為O(1)
對鏈表進行查詢操作時，時間複雜度為O(n)，但是在只查鏈表頭的元素時為O(1)
這些特性很符合棧的需求棧是後進先出的，並且棧只查棧頂的元素，所以可以使用鏈表來實現棧這樣的數據結構。
鏈表實現的棧
MyLinkedListStack
void push(E e)：添加一個元素 E pop()：移除一個元素 E peek()：查看棧頂的元素 int getSize()：獲取棧中實際的元素個數 boolean isEmpty()：判斷棧是否為空
代碼示例
(class: MyLinkedList,class: MyLinkedListStack, class: Main)
MyLinkedList
class MyLinkedListNode {
constructor(element = null, next = null) {
this.element = element;
this.next = next;
}
// toString 2018-10-20-jwl
toString() {
return this.element.toString();
}
}
class MyLinkedList {
constructor() {
this.dummyHead = new MyLinkedListNode(null, null);
this.size = 0;
}
// 獲取鏈表中實際的節點個數
getSize() {
return this.size;
}
// 判斷鏈表是否為空
isEmpty() {
return this.size === 0;
}
// 在鏈表頭添加節點
addFirst(element) {
// let node = new MyLinkedListNode(element, null);
// node.next = this.head;
// this.head = node;
// this.size ++;
// 改用虛擬頭節點
this.insert(0, element);
}
// 在鏈表指定索引處插入節點
insert(index, element) {
if (index < 0 || index > this.size) {
throw new Error('add error. index < 0 or index > size');
}
// 第一個prev就是dummyHead
let prev = this.dummyHead;
// 之前變量i(索引)之所以要從 1 開始，因為索引為0的那個節點就是head，循環就不需要從0開始了，
// 現在索引之所以要從 0 開始， 因為初始化時 多增加了一個虛擬的頭節點
// （因為這個索引為0的節點並不是dummyHead，dummyHead這個節點並不記錄為鏈表中的實際節點），
// 小於index是因為要找到指定索引位置的前一個節點
// 循環是因為 要繼續找到指定索引處的節點的前一個節點
for (var i = 0; i < index; i++) {
// 不停的切換引用，直到找到對應索引處節點的下一個節點
prev = prev.next;
}
let node = new MyLinkedListNode(element, null);
node.next = prev.next;
prev.next = node;
this.size++;
}
// 擴展：在鏈表最後一個節點的位置添加節點
addLast(element) {
this.insert(this.size, element);
}
// 獲取指定索引位置的元素
get(index) {
// 判斷索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 如果你要找指定索引節點的前一個節點 就使用dummyHead
// 如果你要找到指定索引節點 就使用dummyHead.next
// 因為duumyHead並不是第一個節點，因為它是一個虛擬節點，
// dummyHead.next才是真正被記錄的第一個節點。
let node = this.dummyHead.next;
for (var i = 0; i < index; i++) {
node = node.next;
}
return node.element;
}
// 獲取頭節點的元素
getFirst() {
return this.get(0);
}
// 獲取尾節點的元素
getLast() {
return this.get(this.size - 1);
}
// 設置指定索引位置的元素值
set(index, element) {
// 判斷索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 從第一個真正被記錄的節點開始，從0開始
let node = this.dummyHead.next;
// 索引為 0 時，實際上切換到的節點 它的索引為 1
// i < index ，當索引為 index-1 時， 實際上切換到的節點 它的索引為index
for (let i = 0; i < index; i++) {
// 每一次切換 都只是改變引用
// 不的在鏈表中找下一個節點
node = node.next;
}
node.element = element;
}
// 所有節點中是否有包含該元素
contains(element) {
let node = this.dummyHead;
while (node.next !== null) {
if (node.next.element === element) return true;
// 不停的向下切換
node = node.next;
}
return false;
}
// 刪除指定索引位置的節點
remove(index) {
// 驗證索引的合法性
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index > this.size');
}
let node = this.dummyHead;
for (let i = 0; i < index; i++) {
node = node.next;
}
// 待刪除的節點
let delNode = node.next;
// 給待刪除那個節點的前一個的節點的next引用替換為
// 但刪除的這個節點的next
node.next = delNode.next;
// 或者這樣也行
// node.next = node.next.next;
// 臨時存儲待刪除的那個節點裡的元素
let element = delNode.element;
// 清空 待刪除的節點
delNode = null;
this.size--;
return element;
}
// 擴展：移除鏈表頭的元素
removeFirst() {
return this.remove(0);
}
// 擴展：移除鏈表尾部的元素
removeLast() {
return this.remove(this.size - 1);
}
// 輸出鏈表中的信息
// @Override toString 2018-10-21-jwl
toString() {
let arrInfo = `LinkedList: size = ${this.size}，\n`;
arrInfo += `data = front [`;
let node = this.dummyHead.next;
while (node.next !== null) {
arrInfo += `${node.element}->`;
node = node.next;
}
arrInfo += 'NULL] tail';
// 在頁面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MyLinkedListStack
class MyLinkedListStack {
constructor() {
this.myLinkedList = new MyLinkedList();
}
// 入棧
push(element) {
this.myLinkedList.addFirst(element);
}
// 出棧
pop() {
return this.myLinkedList.removeFirst();
}
// 查看棧頂元素
peek() {
return this.myLinkedList.getFirst();
}
// 查看棧中實際元素的個數
getSize() {
return this.myLinkedList.getSize();
}
// 判斷棧是否為空
isEmpty() {
return this.myLinkedList.isEmpty();
}
// 輸出棧中信息
// @Override toString 2018-10-21-jwl
toString() {
let arrInfo = `LinkedListStack: size = ${this.getSize()}，\n`;
arrInfo += `data = stack top [`;
let node = this.myLinkedList.dummyHead.next;
for (var i = 1; i < this.getSize(); i++) {
arrInfo += `${node.element},`;
node = node.next;
}
if (!this.isEmpty()) {
arrInfo += `${node.element}`;
}
arrInfo += ']';
// 在頁面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}Main
class Main {
constructor() {
this.alterLine('MyLinkedListStack Area');
let myLinkedListStack = new MyLinkedListStack();
for (let i = 1; i <= 5; i++) {
myLinkedListStack.push(i);
console.log(myLinkedListStack.toString());
}
console.log(myLinkedListStack.peek());
this.show(myLinkedListStack.peek());
for (let i = 0; i < 5; i++) {
console.log(myLinkedListStack.toString());
myLinkedListStack.pop();
}
}
// 將內容顯示在頁面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割線
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
window.onload = function() {
// 執行主函數
new Main();
};自定義數組實現的棧 VS 自定義鏈表實現的棧
自定義數組棧與自定義鏈表棧的性能相差很少，但是隨著操作的次數增長，數組棧會慢慢強過鏈表棧，自定義鏈表棧中有太多的 new 操作，new 操作在有一些系統上比較耗費性能的，因為它在不停的在內存中尋找可以開闢空間的地方來進行開闢空間，自定義數組棧中有比較多的擴容操作，所以這個比較是相對比較複雜的，和你的語法、操作系統、編譯器、解釋器都有關係，不過他們的時間複雜度都是O(1)級別的，所以他們之間的性能差異無非就 1-2 倍這樣，在最極端的情況下 3-5 倍就已經很難了，不會有幾百倍的巨大的差異，因為畢竟他們的時間複雜度一樣。
代碼示例
(class: MyLinkedList, class: MyLinkedListStack, class: MyArray, class: MyStack, class: Main)
MyLinkedList
class MyLinkedListNode {
constructor(element = null, next = null) {
this.element = element;
this.next = next;
}
// toString 2018-10-20-jwl
toString() {
return this.element.toString();
}
}
class MyLinkedList {
constructor() {
this.dummyHead = new MyLinkedListNode(null, null);
this.size = 0;
}
// 獲取鏈表中實際的節點個數
getSize() {
return this.size;
}
// 判斷鏈表是否為空
isEmpty() {
return this.size === 0;
}
// 在鏈表頭添加節點
addFirst(element) {
// let node = new MyLinkedListNode(element, null);
// node.next = this.head;
// this.head = node;
// this.size ++;
// 改用虛擬頭節點
this.insert(0, element);
}
// 在鏈表指定索引處插入節點
insert(index, element) {
if (index < 0 || index > this.size) {
throw new Error('add error. index < 0 or index > size');
}
// 第一個prev就是dummyHead
let prev = this.dummyHead;
// 之前變量i(索引)之所以要從 1 開始，因為索引為0的那個節點就是head，循環就不需要從0開始了，
// 現在索引之所以要從 0 開始， 因為初始化時 多增加了一個虛擬的頭節點
// （因為這個索引為0的節點並不是dummyHead，dummyHead這個節點並不記錄為鏈表中的實際節點），
// 小於index是因為要找到指定索引位置的前一個節點
// 循環是因為 要繼續找到指定索引處的節點的前一個節點
for (var i = 0; i < index; i++) {
// 不停的切換引用，直到找到對應索引處節點的下一個節點
prev = prev.next;
}
let node = new MyLinkedListNode(element, null);
node.next = prev.next;
prev.next = node;
this.size++;
}
// 擴展：在鏈表最後一個節點的位置添加節點
addLast(element) {
this.insert(this.size, element);
}
// 獲取指定索引位置的元素
get(index) {
// 判斷索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 如果你要找指定索引節點的前一個節點 就使用dummyHead
// 如果你要找到指定索引節點 就使用dummyHead.next
// 因為duumyHead並不是第一個節點，因為它是一個虛擬節點，
// dummyHead.next才是真正被記錄的第一個節點。
let node = this.dummyHead.next;
for (var i = 0; i < index; i++) {
node = node.next;
}
return node.element;
}
// 獲取頭節點的元素
getFirst() {
return this.get(0);
}
// 獲取尾節點的元素
getLast() {
return this.get(this.size - 1);
}
// 設置指定索引位置的元素值
set(index, element) {
// 判斷索引合法性
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
// 從第一個真正被記錄的節點開始，從0開始
let node = this.dummyHead.next;
// 索引為 0 時，實際上切換到的節點 它的索引為 1
// i < index ，當索引為 index-1 時， 實際上切換到的節點 它的索引為index
for (let i = 0; i < index; i++) {
// 每一次切換 都只是改變引用
// 不的在鏈表中找下一個節點
node = node.next;
}
node.element = element;
}
// 所有節點中是否有包含該元素
contains(element) {
let node = this.dummyHead;
while (node.next !== null) {
if (node.next.element === element) return true;
// 不停的向下切換
node = node.next;
}
return false;
}
// 刪除指定索引位置的節點
remove(index) {
// 驗證索引的合法性
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index > this.size');
}
let node = this.dummyHead;
for (let i = 0; i < index; i++) {
node = node.next;
}
// 待刪除的節點
let delNode = node.next;
// 給待刪除那個節點的前一個的節點的next引用替換為
// 但刪除的這個節點的next
node.next = delNode.next;
// 或者這樣也行
// node.next = node.next.next;
// 臨時存儲待刪除的那個節點裡的元素
let element = delNode.element;
// 清空 待刪除的節點
delNode = null;
this.size--;
return element;
}
// 擴展：移除鏈表頭的元素
removeFirst() {
return this.remove(0);
}
// 擴展：移除鏈表尾部的元素
removeLast() {
return this.remove(this.size - 1);
}
// 輸出鏈表中的信息
// @Override toString 2018-10-21-jwl
toString() {
let arrInfo = `LinkedList: size = ${this.size}，\n`;
arrInfo += `data = front [`;
let node = this.dummyHead.next;
while (node.next !== null) {
arrInfo += `${node.element}->`;
node = node.next;
}
arrInfo += 'NULL] tail';
// 在頁面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MyLinkedListStack
class MyLinkedListStack {
constructor() {
this.myLinkedList = new MyLinkedList();
}
// 入棧
push(element) {
this.myLinkedList.addFirst(element);
}
// 出棧
pop() {
return this.myLinkedList.removeFirst();
}
// 查看棧頂元素
peek() {
return this.myLinkedList.getFirst();
}
// 查看棧中實際元素的個數
getSize() {
return this.myLinkedList.getSize();
}
// 判斷棧是否為空
isEmpty() {
return this.myLinkedList.isEmpty();
}
// 輸出棧中信息
// @Override toString 2018-10-21-jwl
toString() {
let arrInfo = `LinkedListStack: size = ${this.getSize()}，\n`;
arrInfo += `data = stack top [`;
let node = this.myLinkedList.dummyHead.next;
for (var i = 1; i < this.getSize(); i++) {
arrInfo += `${node.element},`;
node = node.next;
}
if (!this.isEmpty()) {
arrInfo += `${node.element}`;
}
arrInfo += ']';
// 在頁面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MyArray
class MyArray {
// 構造函數，傳入數組的容量capacity構造Array 默認數組的容量capacity=10
constructor(capacity = 10) {
this.data = new Array(capacity);
this.size = 0;
}
// 獲取數組中的元素實際個數
getSize() {
return this.size;
}
// 獲取數組的容量
getCapacity() {
return this.data.length;
}
// 判斷數組是否為空
isEmpty() {
return this.size === 0;
}
// 給數組擴容
resize(capacity) {
let newArray = new Array(capacity);
for (var i = 0; i < this.size; i++) {
newArray[i] = this.data[i];
}
// let index = this.size - 1;
// while (index > -1) {
// newArray[index] = this.data[index];
// index --;
// }
this.data = newArray;
}
// 在指定索引處插入元素
insert(index, element) {
// 先判斷數組是否已滿
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// 然後判斷索引是否符合要求
if (index < 0 || index > this.size) {
throw new Error(
'insert error. require index < 0 or index > size.'
);
}
// 最後 將指定索引處騰出來
// 從指定索引處開始，所有數組元素全部往後移動一位
// 從後往前移動
for (let i = this.size - 1; i >= index; i--) {
this.data[i + 1] = this.data[i];
}
// 在指定索引處插入元素
this.data[index] = element;
// 維護一下size
this.size++;
}
// 擴展 在數組最前面插入一個元素
unshift(element) {
this.insert(0, element);
}
// 擴展 在數組最後面插入一個元素
push(element) {
this.insert(this.size, element);
}
// 其實在數組中添加元素 就相當於在數組最後面插入一個元素
add(element) {
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// size其實指向的是 當前數組最後一個元素的 後一個位置的索引。
this.data[this.size] = element;
// 維護size
this.size++;
}
// get
get(index) {
// 不能訪問沒有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size.');
}
return this.data[index];
}
// 擴展： 獲取數組中第一個元素
getFirst() {
return this.get(0);
}
// 擴展： 獲取數組中最後一個元素
getLast() {
return this.get(this.size - 1);
}
// set
set(index, newElement) {
// 不能修改沒有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('set error. index < 0 or index >= size.');
}
this.data[index] = newElement;
}
// contain
contain(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return true;
}
}
return false;
}
// find
find(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return i;
}
}
return -1;
}
// findAll
findAll(element) {
// 創建一個自定義數組來存取這些 元素的索引
let myarray = new MyArray(this.size);
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
myarray.push(i);
}
}
// 返回這個自定義數組
return myarray;
}
// 刪除指定索引處的元素
remove(index) {
// 索引合法性驗證
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index >= size.');
}
// 暫存即將要被刪除的元素
let element = this.data[index];
// 後面的元素覆蓋前面的元素
for (let i = index; i < this.size - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.size--;
this.data[this.size] = null;
// 如果size 為容量的四分之一時 就可以縮容了
// 防止複雜度震盪
if (Math.floor(this.getCapacity() / 4) === this.size) {
// 縮容一半
this.resize(Math.floor(this.getCapacity() / 2));
}
return element;
}
// 擴展：刪除數組中第一個元素
shift() {
return this.remove(0);
}
// 擴展： 刪除數組中最後一個元素
pop() {
return this.remove(this.size - 1);
}
// 擴展： 根據元素來進行刪除
removeElement(element) {
let index = this.find(element);
if (index !== -1) {
this.remove(index);
}
}
// 擴展： 根據元素來刪除所有元素
removeAllElement(element) {
let index = this.find(element);
while (index != -1) {
this.remove(index);
index = this.find(element);
}
// let indexArray = this.findAll(element);
// let cur, index = 0;
// for (var i = 0; i < indexArray.getSize(); i++) {
// // 每刪除一個元素 原數組中就少一個元素，
// // 索引數組中的索引值是按照大小順序排列的，
// // 所以 這個cur記錄的是 原數組元素索引的偏移量
// // 只有這樣才能夠正確的刪除元素。
// index = indexArray.get(i) - cur++;
// this.remove(index);
// }
}
// @Override toString 2018-10-17-jwl
toString() {
let arrInfo = `Array: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = [`;
for (var i = 0; i < this.size - 1; i++) {
arrInfo += `${this.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.data[this.size - 1]}`;
}
arrInfo += `]`;
// 在頁面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MyStack
class MyStack {
constructor(capacity = 10) {
this.myArray = new MyArray(capacity);
}
// 入棧
push(element) {
this.myArray.push(element);
}
// 出棧
pop() {
return this.myArray.pop();
}
// 查看棧頂的元素
peek() {
return this.myArray.getLast();
}
// 棧中實際元素的個數
getSize() {
return this.myArray.getSize();
}
// 棧是否為空
isEmpty() {
return this.myArray.isEmpty();
}
// 查看棧的容量
getCapacity() {
return this.myArray.getCapacity();
}
// @Override toString 2018-10-20-jwl
toString() {
let arrInfo = `Stack: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = [`;
for (var i = 0; i < this.myArray.size - 1; i++) {
arrInfo += `${this.myArray.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.myArray.data[this.myArray.size - 1]}`;
}
arrInfo += `] stack top is right!`;
// 在頁面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}Main
class Main {
constructor() {
this.alterLine('Stacks Comparison Area');
let myStack = new MyStack();
let myLinkedListStack = new MyLinkedListStack();
let performanceTest = new PerformanceTest();
let myStackInfo = performanceTest.testStack(myStack, 100000);
let myLinkedListStackInfo = performanceTest.testStack(
myLinkedListStack,
100000
);
this.alterLine('MyStack Area');
console.log(myStackInfo);
this.show(myStackInfo);
this.alterLine('MyLinkedListStack Area');
console.log(myLinkedListStackInfo);
this.show(myLinkedListStackInfo);
}
// 將內容顯示在頁面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割線
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
class Student {
constructor(studentName, studentScore) {
this.name = studentName;
this.score = studentScore;
}
toString() {
let studentInfo = `Student(name: ${this.name}, score: ${this.score})`;
return studentInfo;
}
}
window.onload = function() {
// 執行主函數
new Main();
};使用鏈表來實現隊列
對鏈表進行添加操作時，時間複雜度為O(n)，只對鏈表頭進行操作時為O(1)，對鏈表尾部進行操作時為O(n)
對鏈表進行刪除操作時，時間複雜度為O(n)，只對鏈表頭進行操作時為O(1)，對鏈表尾部進行操作時為O(n)
對鏈表進行查詢操作時，時間複雜度為O(n)，只查鏈表頭的元素時為O(1)，查鏈表尾部的元素時為O(n)
隊列中的操作，在線性結構的一端插入元素，在另外一端刪除元素，所以必然會在線性結構的兩端同時操作，此時就會有一端的操作的複雜度是O(n)級別，這個問題在用自定義數組實現時也遇到了，也正因為如此產生了循環隊列，通過改進使用數組來實現隊列的方式，所以鏈表也可以進行改進。
改進鏈表，不能使用之前的鏈表來進行隊列的實現，設置一個 head 變量指向鏈表的頭部第一個節點，設置一個 tail 變量指向鏈表的尾部第一個節點，有了 tail 這個變量，那麼在鏈表的尾部添加一個元素非常容易，有了 head 和 tail 之後在兩端添加節點是非常容易的，但是無法使用O(1)去刪除尾部的節點，從 tail 這一端刪除元素並不容易，但是如果將 head 作為隊首，將 tail 作為隊尾，隊列操作是從隊尾進隊首出的，只需要從隊尾 tail 插入元素，從隊首 head 刪除元素，這樣一來就可以實現隊列的功能。
鏈表中不再有插入的功能所以不需要 dummyHead，但是由於沒有 dummyHead，所以需要注意鏈表為空的情況。
讓自定義動態數組隊列與自定義鏈表隊列進行對比，自定義動態數組隊列的性能最差自定義動態數組循環隊列與自定義鏈表隊列的性能相近。
與鏈表相關的有一個非常重要的內容，就是遞歸，因為鏈表本身具有天然的遞歸性質，同時它又是一種非常簡單的數據結構，所以鏈表是一種非常好的研究學習遞歸的邏輯機制的的數據結構。
代碼示例
( class: MyArray, class: MyQueue, class: MyLoopQueue, class: MyLinkedListQueue, class: Main)
MyArray
class MyArray {
// 構造函數，傳入數組的容量capacity構造Array 默認數組的容量capacity=10
constructor(capacity = 10) {
this.data = new Array(capacity);
this.size = 0;
}
// 獲取數組中的元素實際個數
getSize() {
return this.size;
}
// 獲取數組的容量
getCapacity() {
return this.data.length;
}
// 判斷數組是否為空
isEmpty() {
return this.size === 0;
}
// 給數組擴容
resize(capacity) {
let newArray = new Array(capacity);
for (var i = 0; i < this.size; i++) {
newArray[i] = this.data[i];
}
// let index = this.size - 1;
// while (index > -1) {
// newArray[index] = this.data[index];
// index --;
// }
this.data = newArray;
}
// 在指定索引處插入元素
insert(index, element) {
// 先判斷數組是否已滿
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// 然後判斷索引是否符合要求
if (index < 0 || index > this.size) {
throw new Error(
'insert error. require index < 0 or index > size.'
);
}
// 最後 將指定索引處騰出來
// 從指定索引處開始，所有數組元素全部往後移動一位
// 從後往前移動
for (let i = this.size - 1; i >= index; i--) {
this.data[i + 1] = this.data[i];
}
// 在指定索引處插入元素
this.data[index] = element;
// 維護一下size
this.size++;
}
// 擴展 在數組最前面插入一個元素
unshift(element) {
this.insert(0, element);
}
// 擴展 在數組最後面插入一個元素
push(element) {
this.insert(this.size, element);
}
// 其實在數組中添加元素 就相當於在數組最後面插入一個元素
add(element) {
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// size其實指向的是 當前數組最後一個元素的 後一個位置的索引。
this.data[this.size] = element;
// 維護size
this.size++;
}
// get
get(index) {
// 不能訪問沒有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size.');
}
return this.data[index];
}
// 擴展： 獲取數組中第一個元素
getFirst() {
return this.get(0);
}
// 擴展： 獲取數組中最後一個元素
getLast() {
return this.get(this.size - 1);
}
// set
set(index, newElement) {
// 不能修改沒有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('set error. index < 0 or index >= size.');
}
this.data[index] = newElement;
}
// contain
contain(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return true;
}
}
return false;
}
// find
find(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return i;
}
}
return -1;
}
// findAll
findAll(element) {
// 創建一個自定義數組來存取這些 元素的索引
let myarray = new MyArray(this.size);
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
myarray.push(i);
}
}
// 返回這個自定義數組
return myarray;
}
// 刪除指定索引處的元素
remove(index) {
// 索引合法性驗證
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index >= size.');
}
// 暫存即將要被刪除的元素
let element = this.data[index];
// 後面的元素覆蓋前面的元素
for (let i = index; i < this.size - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.size--;
this.data[this.size] = null;
// 如果size 為容量的四分之一時 就可以縮容了
// 防止複雜度震盪
if (Math.floor(this.getCapacity() / 4) === this.size) {
// 縮容一半
this.resize(Math.floor(this.getCapacity() / 2));
}
return element;
}
// 擴展：刪除數組中第一個元素
shift() {
return this.remove(0);
}
// 擴展： 刪除數組中最後一個元素
pop() {
return this.remove(this.size - 1);
}
// 擴展： 根據元素來進行刪除
removeElement(element) {
let index = this.find(element);
if (index !== -1) {
this.remove(index);
}
}
// 擴展： 根據元素來刪除所有元素
removeAllElement(element) {
let index = this.find(element);
while (index != -1) {
this.remove(index);
index = this.find(element);
}
// let indexArray = this.findAll(element);
// let cur, index = 0;
// for (var i = 0; i < indexArray.getSize(); i++) {
// // 每刪除一個元素 原數組中就少一個元素，
// // 索引數組中的索引值是按照大小順序排列的，
// // 所以 這個cur記錄的是 原數組元素索引的偏移量
// // 只有這樣才能夠正確的刪除元素。
// index = indexArray.get(i) - cur++;
// this.remove(index);
// }
}
// @Override toString 2018-10-17-jwl
toString() {
let arrInfo = `Array: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = [`;
for (var i = 0; i < this.size - 1; i++) {
arrInfo += `${this.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.data[this.size - 1]}`;
}
arrInfo += `]`;
// 在頁面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MyQueue
class MyQueue {
constructor(capacity = 10) {
this.myArray = new MyArray(capacity);
}
// 入隊
enqueue(element) {
this.myArray.push(element);
}
// 出隊
dequeue() {
return this.myArray.shift();
}
// 查看隊首的元素
getFront() {
return this.myArray.getFirst();
}
// 查看隊列中實際元素的個數
getSize() {
return this.myArray.getSize();
}
// 查看 隊列當前的容量
getCapacity() {
return this.myArray.getCapacity();
}
// 查看隊列是否為空
isEmpty() {
return this.myArray.isEmpty();
}
// 輸出隊列中的信息
// @Override toString 2018-10-20-jwl
toString() {
let arrInfo = `Queue: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = front [`;
for (var i = 0; i < this.myArray.size - 1; i++) {
arrInfo += `${this.myArray.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.myArray.data[this.myArray.size - 1]}`;
}
arrInfo += `] tail`;
// 在頁面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MyLoopQueue
class MyLoopQueue {
constructor(capacity = 10) {
// 初始化新數組
this.data = new Array(capacity);
// 初始化 隊首、隊尾的值 (索引)
this.front = this.tail = 0;
// 隊列中實際元素個數
this.size = 0;
}
// 擴容
resize(capacity) {
let newArray = new Array(capacity);
let index = 0;
for (let i = 0; i < this.size; i++) {
// 索引可能會越界，於是就要取餘一下，
// 如果越界了，就從隊首開始
index = (this.front + i) % this.getCapacity();
newArray[i] = this.data[index];
}
this.data = newArray;
this.front = 0;
this.tail = this.size;
}
// 入隊
enqueue(element) {
// 判斷隊列中是否已滿
if ((this.tail + 1) % this.getCapacity() === this.front) {
this.resize(this.getCapacity() * 2);
}
this.data[this.tail] = element;
this.tail = (this.tail + 1) % this.getCapacity();
this.size++;
}
// 出隊
dequeue() {
// 判斷隊列是否為空
if (this.isEmpty()) {
throw new Error("can't dequeue from an empty queue.");
}
let element = this.data[this.front];
this.data[this.front] = null;
this.front = (this.front + 1) % this.getCapacity();
this.size--;
// 當size 為容量的四分之一時就縮容一倍
if (this.size === Math.floor(this.getCapacity() / 4)) {
this.resize(Math.floor(this.getCapacity() * 2));
}
return element;
}
// 查看隊首的元素
getFront() {
if (this.isEmpty()) {
throw new Error('queue is empty.');
}
return this.data[front];
}
// 查看實際的元素個數
getSize() {
return this.size;
}
// 查看容量
getCapacity() {
return this.data.length;
}
// 隊列是否為空
isEmpty() {
// return this.size === 0;
return this.front == this.tail;
}
// 輸出循環隊列中的信息
// @Override toString 2018-10-20-jwl
toString() {
let arrInfo = `LoopQueue: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = front [`;
for (var i = 0; i < this.myArray.size - 1; i++) {
arrInfo += `${this.myArray.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.myArray.data[this.myArray.size - 1]}`;
}
arrInfo += `] tail`;
// 在頁面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MyLinkedListQueue
class MyLinkedListQueue {
constructor() {
this.front = this.tail = null;
this.size = 0;
}
// 入隊
enqueue(element) {
// 判斷隊尾是否為空
if (this.tail === null) {
// 第一個節點 即是尾也是頭
this.tail = new MyLinkedListNode(element, null);
this.front = this.tail;
} else {
let node = new MyLinkedListNode(element, null);
this.tail.next = node;
this.tail = node;
}
this.size++;
}
// 出隊
dequeue() {
// 判斷隊首是否為空
if (this.front === null) {
throw new Error('front is empty.');
}
let delNode = this.front;
let element = delNode.element;
this.front = this.front.next;
delNode = null;
if (this.front === null)
// 如果頭為空了，那麼尾部也為空
this.tail = null;
this.size--;
return element;
}
// 查看隊首的元素
getFront() {
// 判斷隊首是否為空
if (this.front === null) {
throw new Error('front is empty.');
}
return this.front.element;
}
// 查看隊列中實際元素的個數
getSize() {
return this.size;
}
// 判斷隊列是否為空
isEmpty() {
return this.size === 0;
}
// 輸出隊列中的信息
// @Override toString 2018-10-21-jwl
toString() {
let arrInfo = `LinkedListQueue: size = ${this.getSize()}，\n`;
arrInfo += `data = front [`;
let node = this.front;
for (var i = 1; i < this.getSize(); i++) {
arrInfo += `${node.element},`;
node = node.next;
}
if (!this.isEmpty()) {
arrInfo += `${node.element}`;
}
arrInfo += '] tail';
// 在頁面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}Main
class Main {
constructor() {
this.alterLine('MyLinkedListQueue Area');
let myLinkedListQueue = new MyLinkedListQueue();
for (let i = 1; i <= 5; i++) {
myLinkedListQueue.enqueue(i);
console.log(myLinkedListQueue.toString());
}
console.log(myLinkedListQueue.getFront());
this.show(myLinkedListQueue.getFront());
for (let i = 0; i < 5; i++) {
console.log(myLinkedListQueue.toString());
myLinkedListQueue.dequeue();
}
}
// 將內容顯示在頁面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割線
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
class Student {
constructor(studentName, studentScore) {
this.name = studentName;
this.score = studentScore;
}
toString() {
let studentInfo = `Student(name: ${this.name}, score: ${this.score})`;
return studentInfo;
}
}
window.onload = function() {
// 執行主函數
new Main();
};