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

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

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

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

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

??可以將鏈表中的每個(gè)節(jié)點(diǎn)看成是一個(gè)對(duì)象，這個(gè)對(duì)象中有兩個(gè)屬性，一個(gè)是該節(jié)點(diǎn)的值，一個(gè)是該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的地址（如果是雙鏈表，還要添加前一個(gè)節(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ù)傳入的元素定義一個(gè)節(jié)點(diǎn)，該元素作為這個(gè)節(jié)點(diǎn)的值
• 定義一個(gè)變量表示當(dāng)前的節(jié)點(diǎn)
• 判斷是否含有頭節(jié)點(diǎn),如果沒有頭節(jié)點(diǎn)，說明鏈表中還沒有值，將傳進(jìn)來的這個(gè)值作為頭節(jié)點(diǎn)；否則，對(duì)鏈表進(jìn)行遍歷，找到最后一個(gè)節(jié)點(diǎn)，將其next屬性賦值為新增的節(jié)點(diǎn)
• 鏈表的長(zhǎng)度+1

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

分析：

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

function insert(position,element){         let node = new Node(element);         let current = head;         let previous;//當(dāng)前節(jié)點(diǎn)的前一個(gè)節(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)建一個(gè)節(jié)點(diǎn)
• 定義一個(gè)變量表示當(dāng)前的節(jié)點(diǎn)，初始化為頭節(jié)點(diǎn)，表示從頭節(jié)點(diǎn)開始遍歷；一個(gè)變量表示當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，作用是插入節(jié)點(diǎn)時(shí)方便找到前一個(gè)節(jié)點(diǎn)
• 判斷是否在頭節(jié)點(diǎn)前添加，如果是就將頭節(jié)點(diǎn)賦給node的next屬性，并且頭節(jié)點(diǎn)改為這個(gè)節(jié)點(diǎn)；否則，遍歷出這個(gè)位置的節(jié)點(diǎn)，將該節(jié)點(diǎn)插入到這個(gè)位置的節(jié)點(diǎn)前面
• 鏈表的長(zhǎng)度+1

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

分析：刪除節(jié)點(diǎn)的操作就是將目標(biāo)節(jié)點(diǎn)前面的那個(gè)節(jié)點(diǎn)的指針指向目標(biāo)節(jié)點(diǎn)的后一個(gè)節(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.查詢某個(gè)位置是哪個(gè)節(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.查詢某個(gè)節(jié)點(diǎn)是在哪個(gè)位置

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)的時(shí)候增加一個(gè)前節(jié)點(diǎn)）和循環(huán)鏈表（尾節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)是頭節(jié)點(diǎn)），這些鏈表的操作也是可以使用js實(shí)現(xiàn)的，這里就不多說了?？偨Y(jié)一下，鏈表的核心在于

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

【