JavaScript數(shù)據(jù)結(jié)構(gòu)之單鏈表和循環(huán)鏈表的示例分析

這篇文章將為大家詳細(xì)講解有關(guān)JavaScript數(shù)據(jù)結(jié)構(gòu)之單鏈表和循環(huán)鏈表的示例分析，小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

創(chuàng)新互聯(lián)公司-專(zhuān)業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性?xún)r(jià)比雙湖網(wǎng)站開(kāi)發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫(kù),直接使用。一站式雙湖網(wǎng)站制作公司更省心,省錢(qián),快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋雙湖地區(qū)。費(fèi)用合理售后完善，十載實(shí)體公司更值得信賴(lài)。

鏈表是一種物理存儲(chǔ)單元上非線(xiàn)性、非連續(xù)性的數(shù)據(jù)結(jié)構(gòu)（它在數(shù)據(jù)邏輯上是線(xiàn)性的），它的每個(gè)節(jié)點(diǎn)由兩個(gè)域組成：數(shù)據(jù)域和指針域。數(shù)據(jù)域中存儲(chǔ)實(shí)際數(shù)據(jù)，指針域則存儲(chǔ)著指針信息，指向鏈表中的下一個(gè)元素或者上一個(gè)元素。正是由于指針的存在，鏈表的存儲(chǔ)在物理單元是非連續(xù)性的。

鏈表的優(yōu)點(diǎn)和缺點(diǎn)同樣明顯。和線(xiàn)性表相比，鏈表在添加和刪除節(jié)點(diǎn)上的效率更高，因?yàn)槠渲恍枰薷闹羔樞畔⒓纯赏瓿刹僮鳎幌窬€(xiàn)性表（數(shù)組）那樣需要移動(dòng)元素。同樣的，鏈表的長(zhǎng)度在理論上也是無(wú)限的（在存儲(chǔ)器容量范圍內(nèi)），并可以動(dòng)態(tài)變化長(zhǎng)度，相比線(xiàn)性表優(yōu)勢(shì)很大。 相應(yīng)的，由于線(xiàn)性表無(wú)法隨機(jī)訪(fǎng)問(wèn)節(jié)點(diǎn)，只能通過(guò)指針順著鏈表進(jìn)行遍歷查詢(xún)來(lái)訪(fǎng)問(wèn)，故其訪(fǎng)問(wèn)數(shù)據(jù)元素的效率比較低。 

下面是JS部分

這里面封裝了的常用方法及描述：

方法	描述
append(element)	向鏈表尾部添加結(jié)點(diǎn)element
insert(position,element)	向位置position處插入結(jié)點(diǎn)element
removeAt(position)	按照索引值position刪除結(jié)點(diǎn)
remove(element)	搜索并刪除給定結(jié)點(diǎn)element
remove()	刪除鏈表中最后一個(gè)結(jié)點(diǎn)
indexOf(element)	查找并返回給定結(jié)點(diǎn)element的索引值
isEmpty()	判斷鏈表是否為空
size()	獲取鏈表長(zhǎng)度
toString()	轉(zhuǎn)換為字符串輸出
getHead()	獲取頭結(jié)點(diǎn)
getTail()	獲取尾結(jié)點(diǎn)

對(duì)于各常用方法的算法描述在這里就不寫(xiě)了，相信大家都可以輕易讀懂并理解，畢竟都是非?；A(chǔ)的知識(shí)了。

單鏈表：

function LinkedList(){ 
 /*節(jié)點(diǎn)定義*/ 
 var Node = function(element){ 
  this.element = element; //存放節(jié)點(diǎn)內(nèi)容 
  this.next = null; //指針 
 } 
 
 var length = 0, //存放鏈表長(zhǎng)度 
  head = null; //頭指針 
 
 this.append = function(element){ 
  var node = new Node(element), 
   current; //操作所用指針 
 
  if (!head){ 
   head = node; 
  }else { 
   current = head; 
 
   while(current.next){ 
    current = current.next; 
   } 
 
   current.next = node; 
  } 
 
  length++; 
  return true; 
 }; 
 
 this.insert = function(position, element){ 
  if (position >= 0 && position <= length) { 
   var node = new Node(element), 
    current = head, 
    previous, 
    index = 0; 
 
   if(position === 0){ 
    node.next = current; 
    head = node; 
   }else{ 
    while(index++ < position){ 
     previous = current; 
     current = current.next; 
    } 
    node.next = current; 
    previous.next = node; 
   } 
 
   length++; 
   return true; 
  }else{ 
   return false; 
  } 
  }; 
 
 this.removeAt = function(position){ 
  if(position > -1 && position < length){ 
   var current = head, 
    previous, 
    index = 0; 
 
   if (position === 0) { 
 
    head = current.next; 
 
   }else{ 
 
    while (index++ < position){ 
     previous = current; 
     current = current.next; 
    } 
 
    previous.next = current.next; 
   }; 
 
   length--; 
   return current.element; 
  }else{ 
   return null; 
  } 
 }; 
 
 this.remove = function(element){ 
  var current = head, 
   previous; 
 
  if(element === current.element){ 
   head = current.next; 
   length--; 
   return true; 
  } 
  previous = current; 
  current = current.next; 
 
  while(current){ 
   if(element === current.element){ 
    previous.next = current.next; 
    length--; 
    return true; 
   }else{ 
    previous = current; 
    current = current.next; 
   } 
  } 
  return false; 
 }; 
 
 this.remove = function(){ 
  if(length < 1){ 
   return false; 
  } 
 
  var current = head, 
  previous; 
 
  if(length == 1){ 
   head = null; 
   length--; 
   return current.element; 
  } 
 
  
  while(current.next !== null){ 
   previous = current; 
   current = current.next; 
  } 
 
  previous.next = null; 
  length--; 
  return current.element; 
 }; 
 
 this.indexOf = function(element){ 
  var current = head, 
   index = 0; 
 
  while(current){ 
   if(element === current.element){ 
    return index; 
   } 
   index++; 
   current = current.next; 
  } 
 
  return false; 
 }; 
 
 this.isEmpty = function(){ 
  return length === 0; 
 }; 
 
 this.size = function(){ 
  return length; 
 }; 
 
 this.toString = function(){ 
  var current = head, 
   string = ''; 
 
  while(current){ 
   string += current.element; 
   current = current.next; 
  } 
  return string; 
 };  
 
 this.getHead = function(){ 
  return head; 
 } 
  
}

循環(huán)鏈表：在單鏈表的基礎(chǔ)上，將尾節(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，就構(gòu)成了一個(gè)循環(huán)鏈表。環(huán)形鏈表從任意一個(gè)節(jié)點(diǎn)開(kāi)始，都可以遍歷整個(gè)鏈表。

function CircularLinkedList(){ 
 var Node = function(element){ 
  this.element = element; 
  this.next = null; 
 } 
 
 var length = 0, 
  head = null; 
 
 this.append = function(element){ 
  var node = new Node(element), 
   current; 
 
  if (!head) { 
   head = node; 
   node.next = head; 
  }else{ 
   current = head; 
 
   while(current.next !== head){ 
    current = current.next; 
   } 
 
   current.next = node; 
   node.next = head; 
  }; 
 
  length++; 
  return true; 
 }; 
 
 this.insert = function(position, element){ 
  if(position > -1 && position < length){ 
   var node = new Node(element), 
    index = 0, 
    current = head, 
    previous; 
 
 
   if (position === 0) { 
 
    node.next = head; 
    head = node; 
 
   }else{ 
 
    while(index++ < position){ 
     previous = current; 
     current = current.next; 
    } 
 
    previous.next = node; 
    node.next = current; 
 
   }; 
 
   length++; 
   return true; 
  }else{ 
   return false; 
  } 
 }; 
 
 this.removeAt = function(position){ 
  if(position > -1 && position < length){ 
   var current = head, 
    previous, 
    index = 0; 
 
   if (position === 0) { 
 
    head = current.next; 
 
   }else{ 
 
    while (index++ < position){ 
     previous = current; 
     current = current.next; 
    } 
 
    previous.next = current.next; 
   }; 
 
   length--; 
   return current.element; 
  }else{ 
   return null; 
  } 
 }; 
 
 this.remove = function (element){ 
  var current = head, 
   previous, 
   indexCheck = 0; 
 
  while(current && indexCheck < length){ 
   if(current.element === element){ 
    if(indexCheck == 0){ 
     head = current.next; 
     length--; 
     return true; 
    }else{ 
     previous.next = current.next; 
     length--; 
     return true; 
    } 
   }else{ 
    previous = current; 
    current = current.next; 
    indexCheck++; 
   } 
  } 
  return false; 
 }; 
 
 this.remove = function(){ 
  if(length === 0){ 
   return false; 
  } 
 
  var current = head, 
   previous, 
   indexCheck = 0; 
 
  if(length === 1){ 
   head = null; 
   length--; 
   return current.element; 
  } 
 
  while(indexCheck++ < length){ 
   previous = current; 
   current = current.next; 
  } 
  previous.next = head; 
  length--; 
  return current.element; 
 }; 
 
 this.indexOf = function(element){ 
  var current = head, 
   index = 0; 
 
  while(current && index < length){ 
   if(current.element === element){ 
    return index; 
   }else{ 
    index++; 
    current = current.next; 
   } 
  } 
  return false; 
 }; 
 
 
 this.isEmpty = function(){ 
  return length === 0; 
 }; 
 
 this.size = function(){ 
  return length; 
 }; 
 
 this.toString = function(){ 
  var current = head, 
   string = '', 
   indexCheck = 0; 
 
  while(current && indexCheck < length){ 
   string += current.element; 
   current = current.next; 
   indexCheck++; 
  } 
 
  return string; 
 };  
 
}

使用方法：

在類(lèi)外部擴(kuò)充方法：

關(guān)于“JavaScript數(shù)據(jù)結(jié)構(gòu)之單鏈表和循環(huán)鏈表的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。

文章題目：JavaScript數(shù)據(jù)結(jié)構(gòu)之單鏈表和循環(huán)鏈表的示例分析
文章位置：http://bm7419.com/article0/jdcgoo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營(yíng)銷(xiāo)推廣、做網(wǎng)站、網(wǎng)站建設(shè)、企業(yè)建站、網(wǎng)站制作、域名注冊(cè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀(guān)點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)