在JavaScript中如何使用單鍊錶和循環鍊錶

這篇文章主要介紹了JavaScript資料結構之單鍊錶、循環鍊錶，詳細的介紹了JavaScript如何實作單鍊錶、循環鍊錶，有興趣的可以了解一下

資料結構系列前言：

資料結構作為程式設計師的基本知識，需要我們每個人牢牢掌握。近期我也展開了資料結構的二次學習，來彌補當年挖的坑。 。 。 。 。 。   當時上課的時候也就是跟著聽課，沒有親自實現任何一種資料結構，更別提利用資料結構來解決問題了。現在就來填坑了奮鬥   在這裡提醒看到我博客的孩子們，如果你還是在校生，永遠不要輕視任何一門基礎課的學習，這個時候挖的坑，要么需要用雙倍的努力去填，要么會直接影響一個人的能力等等。 。 。 。 。 。千萬別為自己挖坑

進入正題，關於鍊錶的資料結構知識，這裡簡單介紹下：

鍊錶是一種物理儲存單元上非線性、非連續性的數據結構（它在資料邏輯上是線性的），它的每個節點由兩個域組成：資料域和指標域。資料域中儲存實際數據，指標域則儲存指標訊息，指向鍊錶中的下一個元素或上一個元素。正是由於指標的存在，鍊錶的儲存在物理單元是非連續性的。

鍊錶的優點和缺點同樣明顯。和線性表相比，鍊錶在新增和刪除節點上的效率更高，因為其只需要修改指標資訊即可完成操作，而不是像線性表（陣列）那樣需要移動元素。同樣的，鍊錶的長度在理論上也是無限的（在記憶體容量範圍內），並且可以動態變化長度，相比線性表優勢很大。對應的，由於線性表無法隨機存取節點，只能透過指標順著鍊錶進行遍歷查詢來訪問，故其存取資料元素的效率比較低。

下面是JS部分

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

方法	描述
append(element)	在鍊錶尾部新增結點element
insert(position,element)	向位置position處插入結點element
removeAt(position)	# 依照索引值position刪除結點
#remove(element)	搜尋並刪除給定結點element
#remove()	刪除鍊錶中最後一個結點
indexOf(element)	找出並傳回給定結點element的索引值
isEmpty()	# #判斷鍊錶是否為空
size()	取得鍊錶長度
toString()	轉換為字串輸出
getHead()	取得頭結點
getTail()	#取得尾結點

對於各常用方法的演算法描述在這裡就不寫了，相信大家都可以輕易讀懂並理解，畢竟都是非常基礎的知識了。

單鍊錶：

function LinkedList(){ 
 /*节点定义*/ 
 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; 
  }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 = &#39;&#39;; 
 
  while(current){ 
   string += current.element; 
   current = current.next; 
  } 
  return string; 
 };  
 
 this.getHead = function(){ 
  return head; 
 } 
  
}

循環鍊錶：在單鍊錶的基礎上，將尾節點的指標指向頭接點，就構成了一個循環鍊錶。環形鍊錶從任一個節點開始，都可以遍歷整個鍊錶。

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 = &#39;&#39;, 
   indexCheck = 0; 
 
  while(current && indexCheck < length){ 
   string += current.element; 
   current = current.next; 
   indexCheck++; 
  } 
 
  return string; 
 };  
 
}

使用方法：

在類別外部擴充方法：

上面是我整理給大家的，希望今後對大家有幫助。

相關文章：

在Vue.js中如何實作元件間迴圈引用

在Vue中有關於非同步元件的範例

在nodejs中如何解決超出最大的呼叫堆疊錯誤

#在Vue SpringBoot中如何實作部落格管理平台

以上是在JavaScript中如何使用單鍊錶和循環鍊錶的詳細內容。更多資訊請關注PHP中文網其他相關文章！