本篇文章給大家?guī)砹藬?shù)據(jù)結(jié)構(gòu)學(xué)習(xí)中關(guān)于怎樣使用JavaScript實(shí)現(xiàn)鏈表的相關(guān)知識，希望對大家有幫助。

鏈表有以下幾個特點(diǎn)：

• 可以動態(tài)擴(kuò)展空間（在js中，數(shù)組也是這樣的，但是有的語言中數(shù)組的長度是固定的，不能動態(tài)添加，如c語言）

• 需要一個頭節(jié)點(diǎn)

• 需要知道下一個節(jié)點(diǎn)的地址

??可以將鏈表中的每個節(jié)點(diǎn)看成是一個對象，這個對象中有兩個屬性，一個是該節(jié)點(diǎn)的值，一個是該節(jié)點(diǎn)的下一個節(jié)點(diǎn)的地址（如果是雙鏈表，還要添加前一個節(jié)點(diǎn)地址的屬性）

實(shí)現(xiàn)增加節(jié)點(diǎn)的操作：

1 在尾節(jié)點(diǎn)處添加節(jié)點(diǎn)

 //在尾節(jié)點(diǎn)處添加節(jié)點(diǎn)         function append(element){         let node = new node(element);         let current;         if(head == null){             current = node         }else{             while(current.next){                 current = current.next;             }             current.next = node         }             length++;         }

代碼分析：

• 根據(jù)傳入的元素定義一個節(jié)點(diǎn)，該元素作為這個節(jié)點(diǎn)的值
• 定義一個變量表示當(dāng)前的節(jié)點(diǎn)
• 判斷是否含有頭節(jié)點(diǎn),如果沒有頭節(jié)點(diǎn)，說明鏈表中還沒有值，將傳進(jìn)來的這個值作為頭節(jié)點(diǎn)；否則，對鏈表進(jìn)行遍歷，找到最后一個節(jié)點(diǎn)，將其next屬性賦值為新增的節(jié)點(diǎn)
• 鏈表的長度+1

2.在任意位置添加節(jié)點(diǎn)

分析：

??將這個位置的前一個節(jié)點(diǎn)的next屬性賦值為這個節(jié)點(diǎn)，并將它原先的下一個節(jié)點(diǎn)保存下來，賦值給現(xiàn)在這個節(jié)點(diǎn)的next屬性

function insert(position,element){         let node = new Node(element);         let current = head;         let previous;//當(dāng)前節(jié)點(diǎn)的前一個節(jié)點(diǎn)，在position處添加節(jié)點(diǎn)，就是在previos和current之間添加         if(position = 0){           node.next = head;           head = node;         }else{           for(let i = 0;i< position;i++){             pervious = current;             current = current.next;           }            pervious.next = node;           node.next = current;         }         length++;         return true;       }

代碼分析：

• 檢查postion是否越界,若沒有越界，則創(chuàng)建一個節(jié)點(diǎn)
• 定義一個變量表示當(dāng)前的節(jié)點(diǎn)，初始化為頭節(jié)點(diǎn)，表示從頭節(jié)點(diǎn)開始遍歷；一個變量表示當(dāng)前節(jié)點(diǎn)的前一個節(jié)點(diǎn)，作用是插入節(jié)點(diǎn)時方便找到前一個節(jié)點(diǎn)
• 判斷是否在頭節(jié)點(diǎn)前添加，如果是就將頭節(jié)點(diǎn)賦給node的next屬性，并且頭節(jié)點(diǎn)改為這個節(jié)點(diǎn)；否則，遍歷出這個位置的節(jié)點(diǎn)，將該節(jié)點(diǎn)插入到這個位置的節(jié)點(diǎn)前面
• 鏈表的長度+1

實(shí)現(xiàn)刪除節(jié)點(diǎn)的操作

分析：刪除節(jié)點(diǎn)的操作就是將目標(biāo)節(jié)點(diǎn)前面的那個節(jié)點(diǎn)的指針指向目標(biāo)節(jié)點(diǎn)的后一個節(jié)點(diǎn)

1.刪除指定節(jié)點(diǎn)

function removed(element){            let node = new Node(element);       let pervious;       let nextNode;       let current = head;      if(head != null){       while (current != node){         pervious = current;         current = current.next;         nextNode = current.next;       }          pervious.next = nextNode;       length--;       return true;     }else{       return false;     }         }

2.刪除指定位置的節(jié)點(diǎn)

function removedAt(position){         let current = head;         let pervious;         let nextNode;         let i = 0;          while(i < position){           pervious = current;           current = current.next;           nextNode = current.next;         }          pervious.next = nextNode;         length--;         return true;       }

實(shí)現(xiàn)查詢節(jié)點(diǎn)的操作

分析：查詢節(jié)點(diǎn)和刪除節(jié)點(diǎn)差不多，都是通過遍歷，找到相應(yīng)的節(jié)點(diǎn)或是相應(yīng)的位置，然后進(jìn)行操作

1.查詢某個位置是哪個節(jié)點(diǎn)

function searchElement(element){       //輸入元素，找到該元素后返回該元素的位置       if(head != null){         let node = new Node(element);         let current;         let index = 0;         if(head == node){           return 0;         }else{           current = head;           while(current != node){             current = current.next;             index++;           }           return index;         }       }else{         return -1;       }     }

2.查詢某個節(jié)點(diǎn)是在哪個位置

function searchPosition(position){         let i = 0;         let current = head;         while(i< position){           current = current.next;           i++;         }         return current;     }

思路總結(jié)

??關(guān)于鏈表的操作還有很多，復(fù)雜一點(diǎn)的鏈表還有雙鏈表（在初始化節(jié)點(diǎn)的時候增加一個前節(jié)點(diǎn)）和循環(huán)鏈表（尾節(jié)點(diǎn)的下一個節(jié)點(diǎn)是頭節(jié)點(diǎn)），這些鏈表的操作也是可以使用js實(shí)現(xiàn)的，這里就不多說了?？偨Y(jié)一下，鏈表的核心在于

• 鏈表中節(jié)點(diǎn)可看做一個對象，有兩個屬性值，一個是節(jié)點(diǎn)值，一個是指針
• 鏈表的增刪就是改變指針指向
• 鏈表查找時，重點(diǎn)是current = current.next

【