JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之鏈表
更新時間：2016年01月29日 11:14:18 投稿：hebedich
鏈表就是線性表中針對順序存儲結(jié)構(gòu)的一種優(yōu)化手段，但是在javascript語言中由于數(shù)組的特殊性（自動更新引用位置），所以我們可以采用對象的方式做鏈表存儲的結(jié)構(gòu)
鏈表簡介
鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)，也屬于線性表，但不會按線性的順序來儲存數(shù)據(jù)。而是在每一個節(jié)點中，儲存了下一個節(jié)點的指針?？梢钥磮D理解。(有C語言基礎的可能比較好理解)。
使用鏈表結(jié)構(gòu)可以克服數(shù)組需要預先知道數(shù)據(jù)大小的缺點(C語言的數(shù)組需要預先定義長度)，鏈表結(jié)構(gòu)可以充分利用計算機內(nèi)存空間，實現(xiàn)靈活的內(nèi)存動態(tài)管理。
接下來就是介紹兩種常見的鏈表: 單向鏈表，雙向鏈表在JavaScript中的實現(xiàn)。
單向鏈表
鏈表中最簡單的形式就是單向鏈表，鏈表中的節(jié)點都包含兩個部分，第一部分儲存著自身信息，第二部分則儲存有指向下一節(jié)點的指針。最后一個節(jié)點則指向NULL:
JavaScipt中單向鏈表的實現(xiàn)
首先，創(chuàng)建一個構(gòu)造函數(shù)。
/**
* 單向鏈表構(gòu)造函數(shù)
*/
function LinkedList() {
/**
* 單向鏈表中節(jié)點的構(gòu)造函數(shù)
* @param {Any} element 要傳入鏈表的節(jié)點
*/
var Node = function(element) {
this.element = element;
//下個節(jié)點的地址
this.next = null;
}
//單向鏈表的長度
var length = 0;
//單向鏈表的頭結(jié)點，初始化為NULL
var head = null;
}
不難看出，單向鏈表構(gòu)造函數(shù)比棧與隊列要復雜許多。
單向鏈表需要有如下的方法:
- append(element): 添加元素到鏈表尾部
- insert(position,element): 向單向鏈表中某個位置插入元素
- indexOf(element): 尋找某個元素在單向鏈表中的位置
- remove(element): 移除給定的元素
- removeAt(position): 移除單向鏈表中某個位置的元素
- getHead(): 獲取單向鏈表的頭部
- isAmpty(): 檢查單向鏈表是否為空，為空則返回true
- toString(): 將鏈表所有內(nèi)容以字符串輸出
- size(): 返回單向鏈表長度
append方法:
說明: 向單向鏈表尾部添加元素。
實現(xiàn):
/**
* 向單向鏈表尾部添加元素
* @param {Any} element 要加入鏈表的節(jié)點
*/
this.append = function(element) {
var node = new Node(element);
var current;
if (head == null) {
head = node;
} else {
// 當前項等于鏈表頭部元素.
// while循環(huán)到最后一個，從而將該節(jié)點加入鏈表尾部。
current = head;
// 當next為null時，判定為false。退出循環(huán)。
while (current.next) {
current = current.next;
}
current.next = node;
}
length++;
};
insert方法:
說明: 向單向鏈表中某個位置插入元素。
實現(xiàn):
/**
* 向單向鏈表中插入某個元素
* @param {Number} position 要插入的位置
* @param {Any} element 要插入的元素
* @return {Boolean} 插入成功返回true，失敗返回false
*/
this.insert = function(position, element) {
if (position >= 0 && position <= length) {
var node = new Node(element);
var current = head;
var previous;
var index = 0;
if (position == 0) {
node.next = current;
head = node;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = node;
node.next = current;
}
length++;
return true;
} else {
return false;
}
};
indexOf方法:
說明：尋找某個元素在單向鏈表中的位置。
實現(xiàn):
/**
* 尋找某個元素在單向鏈表中的位置
* @param {Any} element 要尋找的元素
* @return {Number} 返回值>=0則代表找到相應位置
*/
this.indexOf = function(element) {
var current = head;
var index = -1;
while (current) {
if (element === current.element) {
return index;
}
index++;
current = current.next;
}
return -1;
};
remove方法:
說明: 移除給定的元素。
實現(xiàn):
/**
* 移除給定的元素
* @param {Any} element 要移除的元素
* @return {Number} 返回值>=0表示移除成功
*/
this.remove = function(element) {
var index = this.indexOf(element);
return this.removeAt(index);
};
removeAt方法:
說明:移除單向鏈表中某個位置的元素。
實現(xiàn):
/**
* 移除單向鏈表中某一個元素
* @param {Number} position 要移除元素的位置
* @return {Any} 移除成功返回被移除的元素，不成功則返回NULL
*/
this.removeAt = function(position) {
if (position > -1 && position < length) {
var current = head;
var previous;
var index = 0;
if (position == 0) {
// 因為之前head指向第一個元素，現(xiàn)在把head修改為指向第二個元素。
// 核心概念在于鏈表前后全靠指針鏈接，而非數(shù)組一般。
// 所以只需要改變head的元素。
head = current.next;
} else {
while (index++ < position) {
// previous指要操作元素位置之前的那個元素，current表示之后的那個元素。
previous = current;
current = current.next;
}
previous.next = current.next;
}
length--;
return current.element;
} else {
return null;
}
};
getHead方法:
說明:獲取單向鏈表的頭部。
實現(xiàn):
/**
* 獲取單向鏈表的頭部
* @return {Any} 單向鏈表的頭部
*/
this.getHead = function() {
return head;
}
isAmpty、toString、size方法
實現(xiàn):
/**
* 判斷單向鏈表是否為空
* @return {Boolean} 為空則返回true，不為空則返回false
*/
this.isAmpty = function() {
return length === 0
};
/**
* 將鏈表所有內(nèi)容以字符串輸出
* @return {String} 要輸出的字符串
*/
this.toString = function() {
var current = head;
var string = '';
while (current) {
string += current.element;
current = current.next;
}
return string;
};
/**
* 返回單向鏈表長度
* @return {Number} 單向鏈表的長度
*/
this.size = function() {
return length;
};
雙向鏈表
雙向鏈表與單向鏈表很是相像。在單向鏈表中，只有指向下一個節(jié)點的鏈接。但在雙向鏈表中，還有指向上一個節(jié)點的鏈接，是雙向的。
JavaScipt中雙向鏈表的實現(xiàn)
首先，依然是構(gòu)造函數(shù):
/**
* 雙向鏈表的構(gòu)造函數(shù)
*/
function DoublyLinkedList() {
/**
* 雙向鏈表中節(jié)點的構(gòu)造函數(shù)
* @param {Any} element 要傳入鏈表的元素
*/
var Node = function(element) {
this.element = element;
this.prev = null;
this.next = null;
}
//雙向鏈表的長度
var length = 0;
//雙向鏈表的頭結(jié)點，初始化為NULL
var head = null;
//雙向鏈表的尾結(jié)點，初始化為NULL
var tail = null;
}
雙向鏈表需要有如下的方法:
- append(element): 添加元素到雙向鏈表尾部
- insert(position,element): 向雙向鏈表中某個位置插入元素
- removeAt(position): 移除雙向鏈表中某個位置的元素
- showHead(): 獲取雙向鏈表的頭部
- showLength(): 獲取雙向鏈表長度
- showTail(): 獲取雙向鏈表尾部
append方法:
說明: 添加元素到雙向鏈表尾部
實現(xiàn):
/**
* 向鏈表尾部添加元素
* @param {Any} element 要加入鏈表的節(jié)點
* @return {Any} 加入鏈表的節(jié)點
*/
this.append = function(element) {
var node = new Node(element);
if (head === null) {
head = node;
tail = node;
} else {
var previous;
var current = head;
while (current.next) {
current = current.next;
}
current.next = node;
node.prev = current;
tail = node;
}
length++;
return node;
};
insert方法:
說明: 向雙向鏈表中某個位置插入元素。
實現(xiàn):
/**
* 向鏈表中插入某個元素
* @param {Number} position 要插入的位置
* @return {Boolean} 插入成功返回true，失敗返回false
*/
this.insert = function(position, element) {
if (position >= 0 && position <= length) {
var node = new Node(element);
var index = 0;
var previous;
var current = head;
if (position === 0) {
if (head === null) {
head = node;
tail = node;
} else {
current.prev = node;
node.next = current;
head = node;
}
} else if (position === length) {
current = tail;
current.next = node;
node.prev = current;
tail = node;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = node;
node.prev = previous;
current.prev = node;
node.next = current;
}
length++;
return true;
} else {
return false;
}
};
removeAt方法:
說明:移除雙向鏈表中某個位置的元素。
實現(xiàn):
/**
* 移除鏈表中某一個元素
* @param {Number} position 要移除元素的位置
* @return {Any} 移除成功返回被移除的元素，不成功則返回false
*/
this.removeAt = function(position) {
if (position > -1 && position < length) {
var current = head;
var index = 0;
var previous;
if (position === 0) {
head = current.next;
if (length === 1) {
tail = null;
head.prev = null;
}
} else if (position === length - 1) {
current = tail;
tail = current.prev;
tail.next = null;
} else {
while (index++ < position) {
previous = current.prev;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
}
length--;
return current.element;
} else {
return false;
}
};
showHead、showLength、showTail方法
實現(xiàn):
/**
* 獲取鏈表的頭部
* @return {Any} 鏈表的頭部
*/
this.showHead = function() {
return head;
};
/**
* 獲取鏈表長度
* @return {Number} 鏈表長度
*/
this.showLength = function() {
return length;
};
/**
* 獲取鏈表尾部
* @return {Any} 鏈表尾部
*/
this.showTail = function() {
return tail;
};
感想
鏈表這一節(jié)，基本全部都是先按需求寫代碼，寫完后再和書上對比。發(fā)現(xiàn)簡直被瞬間秒成渣。自己寫的很多暗坑，邏輯也很混亂。看來還是太年輕了。
您可能感興趣的文章:
- JavaScript數(shù)據(jù)結(jié)構(gòu)之雙向鏈表
- JavaScript數(shù)據(jù)結(jié)構(gòu)之雙向鏈表和雙向循環(huán)鏈表的實現(xiàn)
- JavaScript數(shù)據(jù)結(jié)構(gòu)之單鏈表和循環(huán)鏈表
- JavaScript數(shù)據(jù)結(jié)構(gòu)之雙向鏈表定義與使用方法示例
- 使用JavaScript實現(xiàn)鏈表的數(shù)據(jù)結(jié)構(gòu)的代碼
- JavaScript數(shù)據(jù)結(jié)構(gòu)之鏈表的實現(xiàn)
- JavaScript數(shù)據(jù)結(jié)構(gòu)鏈表知識詳解
- JavaScript實現(xiàn)的鏈表數(shù)據(jù)結(jié)構(gòu)實例
- JavaScript數(shù)據(jù)結(jié)構(gòu)之鏈表各種操作詳解
相關文章
這篇文章主要給大家介紹了關于Javascript中運算符及流程控制的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-10-10
這篇文章主要介紹了JavaScript中的對象與JSON,本文講解了定義JSON與javascript對象、javascript對象轉(zhuǎn)換為JSON、javascript中解析JSON等內(nèi)容,需要的朋友可以參考下2015-07-07
本文是初學javascript的時候記的學習筆記，簡單介紹了javascript的定義及用法，并附上示例，適合初學者們，老鳥請出門左轉(zhuǎn)。2014-12-12
最近做一個項目,用到javascript操縱excel以生成報表,下面是標有詳細注解的實例2014-05-05
JavaScript中require和import的區(qū)別詳解
本文詳細講解了JS中require和import的區(qū)別，文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-06-06
下面小編就為大家?guī)硪黄獪\談javascript中的加減時間。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-07-07
30分鐘內(nèi)讓你明白正則表達式是什么，并對它有一些基本的了解，讓你可以在自己的程序或網(wǎng)頁里使用它。2013-02-02
從零學JSON之JSON數(shù)據(jù)結(jié)構(gòu)
這篇文章主要介紹了JSON數(shù)據(jù)結(jié)構(gòu)的相關知識,需要的朋友可以參考下2014-05-05
這篇文章介紹了JavaScript的基礎與實例，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-02-02
這篇文章主要為大家詳細介紹了JavaScript面向?qū)ο笾械姆庋b和繼承，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02