快捷導(dǎo)航

JS實現(xiàn)線性表的鏈?zhǔn)奖硎痉椒ㄊ纠窘?jīng)典數(shù)據(jù)結(jié)構(gòu)】

更新時間：2017年04月11日 12:18:03 作者：布瑞澤的童話

這篇文章主要介紹了JS實現(xiàn)線性表的鏈?zhǔn)奖硎痉椒?簡單講解了線性表鏈?zhǔn)奖硎镜脑聿⒔Y(jié)合實例形式分析了js針對線性表鏈?zhǔn)奖硎镜膭?chuàng)建、插入、刪除等節(jié)點操作技巧,需要的朋友可以參考下

本文實例講述了JS實現(xiàn)線性表的鏈?zhǔn)奖硎痉椒?。分享給大家供大家參考，具體如下：

從上一節(jié)可以，順序存儲結(jié)構(gòu)的弱點就是在插入或刪除操作時，需要移動大量元素。所以這里需要介紹一下鏈?zhǔn)酱鎯Y(jié)構(gòu)，由于它不要求邏輯上相鄰的元素在物理位置上也相鄰，所以它沒有順序存儲結(jié)構(gòu)的弱點，但是也沒有順序表可隨機存取的優(yōu)點。

下面介紹一下什么是鏈表。

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素。所以，每一個數(shù)據(jù)元素除了存儲自身的信息之外，還需要存儲一個指向其后繼的存儲位置的信息。這兩部分信息組成了元素的存儲映像，稱為結(jié)點。

結(jié)點包括兩個域：數(shù)據(jù)域和指針域。

數(shù)據(jù)域是元素中存儲數(shù)據(jù)元素的信息。

指針域是元素中存儲的后繼存儲位置的信息。

n個結(jié)點鏈接成為鏈表，就是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，又由于此鏈表的每個結(jié)點中只包含一個指針域，所有又稱為線性鏈表或單鏈表。

舉一個例子

上圖表示的線性表為

ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG

這樣應(yīng)該就好理解多了吧。

下面我們通過js代碼來實現(xiàn)鏈表的插入和刪除還有查找操作

<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8"/>
<script type = "text/javascript">
 var Node = function(newData){//創(chuàng)建節(jié)點對象
 this.next = null;
 this.data = null;
 this.Init = function(){
  this.data = newData;
 };
 this.Init();
 }
 //定義鏈表類
 var List = function(){
 this.head = null;
 this.size = 0;
 this.Init = function(){
  this.head = null;
  this.size = 0;
 }
 this.Init();
 this.Insert = function(newData){//初始批量插入操作
  this.size += 1;
  var newNode = new Node(newData);
  if(this.head == null){
  this.head = newNode;
  return;
  }
  var tempNode = this.head;
  while(tempNode.next != null)
  tempNode = tempNode.next;//找到鏈表尾部
  tempNode.next = newNode;//將新元素插入到鏈表尾部
 };
 this.GetData = function(pos){//查找操作
  if(pos >= this.size || pos < 0)
  return null;
  else{
  tempNode = this.head;
  for(i = 0;i < pos;i++)
   tempNode = tempNode.next; //找到所處位置
  return tempNode.data;
  }
 };
 this.Remove = function(pos){//移除某一位置節(jié)點
  if(pos >= this.size || pos < 0)
  return null;
  this.size -= 1;
  tempNode = this.head;
  if(pos == 0){
  this.head = this.head.next;
  return this.head;
  }
  for(i = 0;i < pos - 1;i++){
  tempNode = tempNode.next;
  }
  tempNode.next = tempNode.next.next;
  return tempNode.next;
 };
 this.InsertBefore=function(data,pos){//從某一位置前插入節(jié)點
  if(pos>=this.size||pos<0)
  return null;
  this.size+=1;
  tempNode=this.head;
  var newNode = new Node(data);//將數(shù)據(jù)創(chuàng)造節(jié)點
  if(pos==0){
  newNode.next=tempNode;
  return newNode.next;
  }
  for(i=0;i<pos-1;i++){
  tempNode=tempNode.next;//找到插入的位置
  }
  newNode.next=tempNode.next;//插入操作
  tempNode.next=newNode;
  return newNode.next;
 };
 this.Print = function(){//輸出
  document.write("鏈表中元素: <br>");
  tempNode = this.head;
  while(tempNode != null){
  document.write(tempNode.data + " ");
  tempNode = tempNode.next;
  }
  document.write("<br>");
 };
 };
 //運行測試:
 var list = new List();
 var array = new Array(1,2,3,4,5,6);
 for(i = 0;i < array.length;i++){
 list.Insert(array[i]);
 }
 list.Print();
 document.write("查找操作下標(biāo)為4的元素: <br>");
 var data= list.GetData(4);
 document.write(data+"<br>");
 document.write("刪除操作: <br>");
 list.Remove(5);
 list.Print();
 document.write("插入操作: <br>");
 list.InsertBefore(8,3);
 list.Print();
 document.write("鏈表大小: " + list.size);
</script>
</head>
<body>
</body>
</html>

運行得到結(jié)果為

先分析一下插入和刪除的代碼。

 this.InsertBefore=function(data,pos){//從某一位置前插入節(jié)點
  if(pos>=this.size||pos<0)
    return null;
  this.size+=1;
  tempNode=this.head;
  var newNode = new Node(data);//將數(shù)據(jù)創(chuàng)造節(jié)點
  if(pos==0){
    newNode.next=tempNode;
    return newNode.next;
  }
  for(i=0;i<pos-1;i++){
    tempNode=tempNode.next;//找到插入的位置
  }
    newNode.next=tempNode.next;//插入操作
    tempNode.next=newNode;
  return newNode.next;
};
this.Remove = function(pos){//移除某一位置節(jié)點
      if(pos >= this.size || pos < 0)
       return null;
      this.size -= 1;
      tempNode = this.head;
      if(pos == 0){
       this.head = this.head.next;
       return this.head;
      }
      for(i = 0;i < pos - 1;i++){
       tempNode = tempNode.next;
      }
      tempNode.next = tempNode.next.next;
      return tempNode.next;
};

可以看出，插入和刪除的世界復(fù)雜度都為o(n)。因為在第i個結(jié)點前插入或刪除都得找到第i-1個元素。

再來看看初始化方法Insert，

this.Insert = function(newData){//初始批量插入操作
      this.size+= 1;
      var newNode = new Node(newData);
      if(this.head == null){
       this.head = newNode;
       return;
      }
      var tempNode = this.head;
      while(tempNode.next != null)
       tempNode = tempNode.next;//找到鏈表尾部
      tempNode.next= newNode;//將新元素插入到鏈表尾部
};

初始的插入Insert方法的時間復(fù)雜度也是o(n)。

下面介紹一下另外一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)，就是循環(huán)鏈表。它的特點就表中的最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。有時候，在循環(huán)鏈表中設(shè)立尾指針而不設(shè)立頭指針，可以簡化操作。比如兩個線性表集合為一個表時，僅需將一個表的表尾和另一個表的表頭相接。這個操作的時間復(fù)雜度是o(1)。

如下圖所示