整合營銷服務(wù)商
電腦端+手機(jī)端+微信端=數(shù)據(jù)同步管理
免費(fèi)咨詢熱線：
電腦端+手機(jī)端+微信端=數(shù)據(jù)同步管理
免費(fèi)咨詢熱線：
不管是在前端還是后端開發(fā)面試過程中，關(guān)于數(shù)據(jù)結(jié)構(gòu)部分的問題是必不可少的，比如像鏈表，棧，隊(duì)列，圖等等。今天這篇文章，我們站在前端開發(fā)人員的角度，看看如何使用Javascript來實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的鏈表結(jié)構(gòu)。
今天這篇文章中的代碼已經(jīng)放到Github上了，感興趣的可以自取，Github地址為：
https://github.com/zhouxiongking/article-pages/blob/master/articles/LinkedList/LinkedList.js
Javascript
鏈表和數(shù)組是數(shù)據(jù)結(jié)構(gòu)中用于存儲多個(gè)元素，比較常用的數(shù)據(jù)結(jié)構(gòu)。數(shù)組中的元素在內(nèi)存中占用連續(xù)的內(nèi)存空間，而在鏈表中各個(gè)元素不是占有連續(xù)的內(nèi)存空間，元素之間通過引用關(guān)系連接。
通過下面這張圖可以很容易看清鏈表結(jié)構(gòu)。
鏈表結(jié)構(gòu)
相比于數(shù)組，鏈表在添加或移除元素時(shí)不會移動元素，只需要改變引用指向即可。但是如果想要訪問鏈表中的某個(gè)元素時(shí)，必須從表頭開始尋找，這是在使用上比數(shù)組劣勢的地方。
下面我們看看如何通過代碼來實(shí)現(xiàn)一個(gè)鏈表結(jié)構(gòu)，由于我們會采用類的結(jié)構(gòu)來組織代碼，因此采用ES6的語法來寫。
鏈表節(jié)點(diǎn)
首先我們需要如上圖所示的鏈表節(jié)點(diǎn)。
鏈表節(jié)點(diǎn)
追加元素
追加元素是在鏈表的末尾添加元素，動態(tài)的修改next引用的指向并修改鏈表的長度。
追加元素
任意位置插入元素
在任意位置插入元素時(shí)，我們需要建立一個(gè)臨時(shí)索引，從表頭開始往后迭代，直到臨時(shí)變量值等于插入位置，即改變插入點(diǎn)的next引用指向。
任意位置插入元素
移除指定位置元素
在移除指定位置元素時(shí)，首先需要檢查值是否越界，同樣需要建立一個(gè)臨時(shí)索引，從表頭向后迭代時(shí)，動態(tài)修改索引值，直到索引值與指定位置值相等，最后修改元素的next引用指向。
移除指定位置元素
尋找元素索引
在尋找元素索引時(shí)，建立一個(gè)臨時(shí)變量，從表頭開始向后遍歷，在遍歷過程中動態(tài)修改臨時(shí)變量值，直到找到需要的元素，返回這個(gè)臨時(shí)變量即可。
尋找元素索引
刪除指定元素
在刪除指定元素時(shí)，可以借助上述的尋找元素索引方法，先找到索引再通過移除指定位置元素的方法來刪除。
刪除指定元素
判空和鏈表長度
判斷鏈表是否為空以及獲取鏈表的長度，都只需要通過length屬性即可。
判空和鏈表長度
自定義輸出
打印鏈表時(shí)，我們可以自定義toString()方法，以我們想要的方式進(jìn)行輸出。
自定義輸出
用Javascript編寫完鏈表結(jié)構(gòu)后，我們通過以下的代碼進(jìn)行測試。
測試代碼
我們可以得到以下結(jié)果。
測試結(jié)果
這也證明了我們實(shí)現(xiàn)鏈表結(jié)構(gòu)的正確性。
今天這篇文章主要利用Javascript實(shí)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)中的鏈表，大家學(xué)會了嗎？
不管是在前端還是后端開發(fā)面試過程中，關(guān)于數(shù)據(jù)結(jié)構(gòu)部分的問題是必不可少的，比如像鏈表，棧，隊(duì)列，圖等等。今天這篇文章，我們站在前端開發(fā)人員的角度，看看如何使用Javascript來實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的鏈表結(jié)構(gòu)。
今天這篇文章中的代碼已經(jīng)放到Github上了，感興趣的可以自取，Github地址為：
https://github.com/zhouxiongking/article-pages/blob/master/articles/LinkedList/LinkedList.js
Javascript
鏈表和數(shù)組是數(shù)據(jù)結(jié)構(gòu)中用于存儲多個(gè)元素，比較常用的數(shù)據(jù)結(jié)構(gòu)。數(shù)組中的元素在內(nèi)存中占用連續(xù)的內(nèi)存空間，而在鏈表中各個(gè)元素不是占有連續(xù)的內(nèi)存空間，元素之間通過引用關(guān)系連接。
通過下面這張圖可以很容易看清鏈表結(jié)構(gòu)。
鏈表結(jié)構(gòu)
相比于數(shù)組，鏈表在添加或移除元素時(shí)不會移動元素，只需要改變引用指向即可。但是如果想要訪問鏈表中的某個(gè)元素時(shí)，必須從表頭開始尋找，這是在使用上比數(shù)組劣勢的地方。
下面我們看看如何通過代碼來實(shí)現(xiàn)一個(gè)鏈表結(jié)構(gòu)，由于我們會采用類的結(jié)構(gòu)來組織代碼，因此采用ES6的語法來寫。
鏈表節(jié)點(diǎn)
首先我們需要如上圖所示的鏈表節(jié)點(diǎn)。
鏈表節(jié)點(diǎn)
追加元素
追加元素是在鏈表的末尾添加元素，動態(tài)的修改next引用的指向并修改鏈表的長度。
追加元素
任意位置插入元素
在任意位置插入元素時(shí)，我們需要建立一個(gè)臨時(shí)索引，從表頭開始往后迭代，直到臨時(shí)變量值等于插入位置，即改變插入點(diǎn)的next引用指向。
任意位置插入元素
移除指定位置元素
在移除指定位置元素時(shí)，首先需要檢查值是否越界，同樣需要建立一個(gè)臨時(shí)索引，從表頭向后迭代時(shí)，動態(tài)修改索引值，直到索引值與指定位置值相等，最后修改元素的next引用指向。
移除指定位置元素
尋找元素索引
在尋找元素索引時(shí)，建立一個(gè)臨時(shí)變量，從表頭開始向后遍歷，在遍歷過程中動態(tài)修改臨時(shí)變量值，直到找到需要的元素，返回這個(gè)臨時(shí)變量即可。
尋找元素索引
刪除指定元素
在刪除指定元素時(shí)，可以借助上述的尋找元素索引方法，先找到索引再通過移除指定位置元素的方法來刪除。
刪除指定元素
判空和鏈表長度
判斷鏈表是否為空以及獲取鏈表的長度，都只需要通過length屬性即可。
判空和鏈表長度
自定義輸出
打印鏈表時(shí)，我們可以自定義toString()方法，以我們想要的方式進(jìn)行輸出。
自定義輸出
用Javascript編寫完鏈表結(jié)構(gòu)后，我們通過以下的代碼進(jìn)行測試。
測試代碼
我們可以得到以下結(jié)果。
測試結(jié)果
這也證明了我們實(shí)現(xiàn)鏈表結(jié)構(gòu)的正確性。
今天這篇文章主要利用Javascript實(shí)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)中的鏈表，大家學(xué)會了嗎？
篇文章給大家?guī)淼膬?nèi)容是關(guān)于JavaScript中鏈表的詳細(xì)介紹，有一定的參考價(jià)值，有需要的朋友可以參考一下，希望對你有所幫助。
鏈表和數(shù)組
大家都用過js中的數(shù)組，數(shù)組其實(shí)是一種線性表的順序存儲結(jié)構(gòu)，它的特點(diǎn)是用一組地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素。而它的缺點(diǎn)也正是其特點(diǎn)而造成，比如對數(shù)組做刪除或者插入的時(shí)候，可能需要移動大量的元素。
這里大致模擬一下數(shù)組的插入操作：
insert(arr, index, data){
for(let i=index + 1; i < arr.length; i++){
arr[i]=arr[i - 1];
}
arr[index]=data;
}
從上面的代碼可以看出數(shù)組的插入以及刪除都有可能會是一個(gè)O(n)的操作。從而就引出了鏈表這種數(shù)據(jù)結(jié)構(gòu)，鏈表不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲結(jié)構(gòu)所具有的缺點(diǎn)，當(dāng)然它也失去了數(shù)組在一塊連續(xù)空間內(nèi)隨機(jī)存取的優(yōu)點(diǎn)。
單向鏈表
單向鏈表的特點(diǎn)：
鏈表中的幾個(gè)主要操作
初始化節(jié)點(diǎn)
class Node {
constructor(key) {
this.next=null;
this.key=key;
}
}
初始化單向鏈表
class List {
constructor() {
this.head=null;
}
}
創(chuàng)建節(jié)點(diǎn)
static createNode(key) {
return new createNode(key);
}
這里說明一下，這一塊我是向外暴露了一個(gè)靜態(tài)方法來創(chuàng)建節(jié)點(diǎn)，而并非直接把它封裝進(jìn)插入操作里去，因?yàn)槲腋杏X這樣的邏輯會更加正確一些。 從創(chuàng)建一個(gè)鏈表 -> 創(chuàng)建一個(gè)節(jié)點(diǎn) -> 將節(jié)點(diǎn)插入進(jìn)鏈表中?？赡苣銜龅揭恍┪恼陆榻B的方式是直接將一個(gè)數(shù)據(jù)作為參數(shù)去調(diào)用insert操作，在insert內(nèi)部做了一個(gè)創(chuàng)建節(jié)點(diǎn)。
插入節(jié)點(diǎn)（插入到頭節(jié)點(diǎn)之后）
插入操作只需要去調(diào)整節(jié)點(diǎn)的指針即可,兩種情況：
insert(node) {
// 如果head有指向的節(jié)點(diǎn)
if(this.head){
node.next=this.head;
}else {
node.next=null;
}
this.head=node;
}
搜索節(jié)點(diǎn)
find(key) {
let node=this.head;
while(node !==null && node.key !==key){
node=node.next;
}
return node;
}
刪除節(jié)點(diǎn)
這里分三種情況：
delete(node) {
// 第一種情況
if(node===this.head){
this.head=node.next;
return;
}
// 查找所要?jiǎng)h除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
let prevNode=this.head;
while (prevNode.next !==node) {
prevNode=prevNode.next;
}
// 第二種情況
if(node.next===null) {
prevNode.next=null;
}
// 第三種情況
if(node.next) {
prevNode.next=node.next;
}
}
單向鏈表整體的代碼
class ListNode {
constructor(key) {
this.next=null;
this.key=key;
}
}
class List {
constructor() {
this.head=null;
this.length=0;
}
static createNode(key) {
return new ListNode(key);
}
// 往頭部插入數(shù)據(jù)
insert(node) {
// 如果head后面有指向的節(jié)點(diǎn)
if (this.head) {
node.next=this.head;
} else {
node.next=null;
}
this.head=node;
this.length++;
}
find(key) {
let node=this.head;
while (node !==null && node.key !==key) {
node=node.next;
}
return node;
}
delete(node) {
if (this.length===0) {
throw 'node is undefined';
}
if (node===this.head) {
this.head=node.next;
this.length--;
return;
}
let prevNode=this.head;
while (prevNode.next !==node) {
prevNode=prevNode.next;
}
if (node.next===null) {
prevNode.next=null;
}
if (node.next) {
prevNode.next=node.next;
}
this.length--;
}
}
雙向鏈表
如果你把上面介紹的單向列表都看明白了，那么這里介紹的雙向列表其實(shí)差不多。
從上面的圖可以很清楚的看到雙向鏈表和單向鏈表的區(qū)別。雙向鏈表多了一個(gè)指向上一個(gè)節(jié)點(diǎn)的指針。
初始化節(jié)點(diǎn)
class ListNode {
this.prev=null;
this.next=null;
this.key=key;
}
初始化雙向鏈表
class List {
constructor(){
this.head=null;
}
}
創(chuàng)建節(jié)點(diǎn)
static createNode(key){
return new ListNode(key);
}
插入節(jié)點(diǎn)（（插入到頭節(jié)點(diǎn)之后）
insert(node) {
node.prev=null;
node.next=this.head;
if(this.head){
this.head.prev=node;
}
this.head=node;
}
搜索節(jié)點(diǎn)
這里和單向節(jié)點(diǎn)一樣，就直接貼代碼了
search(key) {
let node=this.head;
while (node !==null && node.key !==key) {
node=node.next;
}
return node;
}
刪除節(jié)點(diǎn)
和之前單向鏈表一樣，分三種情況去看：
delete(node) {
const {prev,next}=node;
delete node.prev;
delete node.next;
if(node===this.head){
this.head=next;
}
if(next){
next.prev=prev;
}
if(prev){
prev.next=next;
}
}
雙向鏈表整體代碼
class ListNode {
constructor(key) {
// 指向前一個(gè)節(jié)點(diǎn)
this.prev=null;
// 指向后一個(gè)節(jié)點(diǎn)
this.next=null;
// 節(jié)點(diǎn)的數(shù)據(jù)(或者用于查找的鍵)
this.key=key;
}
}
/**
* 雙向鏈表
*/
class List {
constructor() {
this.head=null;
}
static createNode(key) {
return new ListNode(key);
}
insert(node) {
node.prev=null;
node.next=this.head;
if (this.head) {
this.head.prev=node;
}
this.head=node;
}
search(key) {
let node=this.head;
while (node !==null && node.key !==key) {
node=node.next;
}
return node;
}
delete(node) {
const { prev, next }=node;
delete node.prev;
delete node.next;
if (node===this.head) {
this.head=next;
}
if (prev) {
prev.next=next;
}
if (next) {
next.prev=prev;
}
}
}
總結(jié)
這里做一個(gè)小總結(jié)吧，可能有一部分人讀到這里還不是特別的明白，我的建議是先好好看懂上面的單向鏈表。 其實(shí)只要你明白了鏈表的基礎(chǔ)概念，就是有一個(gè)head，然后在有好多的節(jié)點(diǎn)(Node)，然后用一個(gè)指針把他們串起來就好了，至于里面的插入操作也好，刪除也好，其實(shí)都是在調(diào)整節(jié)點(diǎn)中指針的指向。
以上就是JavaScript中鏈表的詳細(xì)介紹的詳細(xì)內(nèi)容，更多請關(guān)注其它相關(guān)文章！
更多技巧請《轉(zhuǎn)發(fā) + 關(guān)注》哦！
*請認(rèn)真填寫需求信息，我們會在24小時(shí)內(nèi)與您取得聯(lián)系。
