JavaScript數據結構與算法之鏈表

更新時間：2016年01月29日 11:14:18 投稿：hebedich

鏈表就是線性表中針對順序存儲結構的一種優(yōu)化手段，但是在javascript語言中由于數組的特殊性（自動更新引用位置），所以我們可以采用對象的方式做鏈表存儲的結構

鏈表簡介

鏈表是一種常見的數據結構，也屬于線性表，但不會按線性的順序來儲存數據。而是在每一個節(jié)點中，儲存了下一個節(jié)點的指針?？梢钥磮D理解。(有C語言基礎的可能比較好理解)。
使用鏈表結構可以克服數組需要預先知道數據大小的缺點(C語言的數組需要預先定義長度)，鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態(tài)管理。
接下來就是介紹兩種常見的鏈表: 單向鏈表，雙向鏈表在JavaScript中的實現。

單向鏈表

鏈表中最簡單的形式就是單向鏈表，鏈表中的節(jié)點都包含兩個部分，第一部分儲存著自身信息，第二部分則儲存有指向下一節(jié)點的指針。最后一個節(jié)點則指向NULL:

JavaScipt中單向鏈表的實現

首先，創(chuàng)建一個構造函數。

/**
 * 單向鏈表構造函數
 */
function LinkedList() {
 /**
  * 單向鏈表中節(jié)點的構造函數
  * @param {Any} element 要傳入鏈表的節(jié)點
  */
 var Node = function(element) {
  this.element = element;
  //下個節(jié)點的地址
  this.next = null;
 }

 //單向鏈表的長度
 var length = 0;
 //單向鏈表的頭結點，初始化為NULL
 var head = null;
}

不難看出，單向鏈表構造函數比棧與隊列要復雜許多。
單向鏈表需要有如下的方法:

append(element): 添加元素到鏈表尾部
insert(position,element): 向單向鏈表中某個位置插入元素
indexOf(element): 尋找某個元素在單向鏈表中的位置
remove(element): 移除給定的元素
removeAt(position): 移除單向鏈表中某個位置的元素
getHead(): 獲取單向鏈表的頭部
isAmpty(): 檢查單向鏈表是否為空，為空則返回true
toString(): 將鏈表所有內容以字符串輸出
size(): 返回單向鏈表長度

append方法:

說明: 向單向鏈表尾部添加元素。
實現:

/**
 * 向單向鏈表尾部添加元素
 * @param {Any} element 要加入鏈表的節(jié)點
 */
this.append = function(element) {
 var node = new Node(element);
 var current;

 if (head == null) {
  head = node;
 } else {
  // 當前項等于鏈表頭部元素.
  // while循環(huán)到最后一個，從而將該節(jié)點加入鏈表尾部。
  current = head;
  // 當next為null時，判定為false。退出循環(huán)。
  while (current.next) {
   current = current.next;
  }
  current.next = node;
 }
 length++;
};

insert方法:

說明: 向單向鏈表中某個位置插入元素。
實現:

/**
 * 向單向鏈表中插入某個元素
 * @param {Number} position 要插入的位置
 * @param {Any} element 要插入的元素
 * @return {Boolean}     插入成功返回true，失敗返回false
 */
this.insert = function(position, element) {
 if (position >= 0 && position <= length) {
  var node = new Node(element);
  var current = head;
  var previous;
  var index = 0;

  if (position == 0) {
   node.next = current;
   head = node;
  } else {
   while (index++ < position) {
    previous = current;
    current = current.next;
   }

   previous.next = node;
   node.next = current;
  }

  length++;
  return true;
 } else {
  return false;
 }
};

indexOf方法:

說明：尋找某個元素在單向鏈表中的位置。
實現:

/**
 * 尋找某個元素在單向鏈表中的位置
 * @param {Any} element 要尋找的元素
 * @return {Number}     返回值>=0則代表找到相應位置
 */
this.indexOf = function(element) {
 var current = head;
 var index = -1;

 while (current) {
  if (element === current.element) {
   return index;
  }
  index++;
  current = current.next;
 }

 return -1;
};

remove方法:

說明: 移除給定的元素。
實現:

/**
 * 移除給定的元素
 * @param {Any} element 要移除的元素
 * @return {Number}     返回值>=0表示移除成功
 */
this.remove = function(element) {
 var index = this.indexOf(element);
 return this.removeAt(index);
};

removeAt方法:

說明:移除單向鏈表中某個位置的元素。
實現:

/**
 * 移除單向鏈表中某一個元素
 * @param {Number} position 要移除元素的位置
 * @return {Any}     移除成功返回被移除的元素，不成功則返回NULL
 */
this.removeAt = function(position) {
 if (position > -1 && position < length) {
  var current = head;
  var previous;
  var index = 0;

  if (position == 0) {
   // 因為之前head指向第一個元素，現在把head修改為指向第二個元素。
   // 核心概念在于鏈表前后全靠指針鏈接，而非數組一般。
   // 所以只需要改變head的元素。
   head = current.next;
  } else {
   while (index++ < position) {
    // previous指要操作元素位置之前的那個元素，current表示之后的那個元素。
    previous = current;
    current = current.next;
   }

   previous.next = current.next;
  }

  length--;

  return current.element;
 } else {
  return null;
 }
};

getHead方法:

說明:獲取單向鏈表的頭部。
實現:

/**
 * 獲取單向鏈表的頭部
 * @return {Any} 單向鏈表的頭部
 */
this.getHead = function() {
 return head;
}

isAmpty、toString、size方法

實現:

/**
 * 判斷單向鏈表是否為空
 * @return {Boolean} 為空則返回true，不為空則返回false
 */
this.isAmpty = function() {
 return length === 0
};

/**
 * 將鏈表所有內容以字符串輸出
 * @return {String} 要輸出的字符串
 */
this.toString = function() {
 var current = head;
 var string = '';

 while (current) {
  string += current.element;
  current = current.next;
 }
 return string;
};

/**
 * 返回單向鏈表長度
 * @return {Number} 單向鏈表的長度
 */
this.size = function() {
 return length;
};

雙向鏈表

雙向鏈表與單向鏈表很是相像。在單向鏈表中，只有指向下一個節(jié)點的鏈接。但在雙向鏈表中，還有指向上一個節(jié)點的鏈接，是雙向的。

JavaScipt中雙向鏈表的實現

首先，依然是構造函數:

/**
 * 雙向鏈表的構造函數
 */
function DoublyLinkedList() {
 /**
  * 雙向鏈表中節(jié)點的構造函數
  * @param {Any} element 要傳入鏈表的元素
  */
 var Node = function(element) {
  this.element = element;
  this.prev = null;
  this.next = null;
 }

 //雙向鏈表的長度
 var length = 0;
 //雙向鏈表的頭結點，初始化為NULL
 var head = null;
 //雙向鏈表的尾結點，初始化為NULL
 var tail = null;
}

雙向鏈表需要有如下的方法:

append(element): 添加元素到雙向鏈表尾部
insert(position,element): 向雙向鏈表中某個位置插入元素
removeAt(position): 移除雙向鏈表中某個位置的元素
showHead(): 獲取雙向鏈表的頭部
showLength(): 獲取雙向鏈表長度
showTail(): 獲取雙向鏈表尾部

append方法:

說明: 添加元素到雙向鏈表尾部
實現:

/**
 * 向鏈表尾部添加元素
 * @param {Any} element 要加入鏈表的節(jié)點
 * @return {Any}     加入鏈表的節(jié)點
 */
this.append = function(element) {
 var node = new Node(element);

 if (head === null) {
  head = node;
  tail = node;
 } else {
  var previous;
  var current = head;

  while (current.next) {
   current = current.next;
  }

  current.next = node;
  node.prev = current;
  tail = node;
 }

 length++;
 return node;
};

insert方法:

說明: 向雙向鏈表中某個位置插入元素。
實現:

/**
 * 向鏈表中插入某個元素
 * @param {Number} position 要插入的位置
 * @return {Boolean}     插入成功返回true，失敗返回false
 */
this.insert = function(position, element) {
 if (position >= 0 && position <= length) {

  var node = new Node(element);
  var index = 0;
  var previous;
  var current = head;

  if (position === 0) {

   if (head === null) {
    head = node;
    tail = node;
   } else {
    current.prev = node;
    node.next = current;
    head = node;
   }
  } else if (position === length) {

   current = tail;
   current.next = node;
   node.prev = current;
   tail = node;
  } else {

   while (index++ < position) {
    previous = current;
    current = current.next;
   }

   previous.next = node;
   node.prev = previous;
   current.prev = node;
   node.next = current;
  }

  length++;
  return true;
 } else {
  return false;
 }
};

removeAt方法:

說明:移除雙向鏈表中某個位置的元素。
實現:

/**
 * 移除鏈表中某一個元素
 * @param {Number} position 要移除元素的位置
 * @return {Any}       移除成功返回被移除的元素，不成功則返回false
 */
this.removeAt = function(position) {
 if (position > -1 && position < length) {
  var current = head;
  var index = 0;
  var previous;

  if (position === 0) {
   head = current.next;

   if (length === 1) {
    tail = null;
    head.prev = null;
   }
  } else if (position === length - 1) {
   current = tail;
   tail = current.prev;
   tail.next = null;
  } else {
   while (index++ < position) {
    previous = current.prev;
    current = current.next;
   }
   previous.next = current.next;
   current.next.prev = previous;
  }

  length--;
  return current.element;
 } else {
  return false;
 }
};

showHead、showLength、showTail方法

實現:

/**
 * 獲取鏈表的頭部
 * @return {Any} 鏈表的頭部
 */
this.showHead = function() {
 return head;
};

/**
 * 獲取鏈表長度
 * @return {Number} 鏈表長度
 */
this.showLength = function() {
 return length;
};

/**
 * 獲取鏈表尾部
 * @return {Any} 鏈表尾部
 */
this.showTail = function() {
 return tail;
};

感想

鏈表這一節(jié)，基本全部都是先按需求寫代碼，寫完后再和書上對比。發(fā)現簡直被瞬間秒成渣。自己寫的很多暗坑，邏輯也很混亂?？磥磉€是太年輕了。

您可能感興趣的文章:

JavaScript鏈表

Javascript基礎:運算符與流程控制詳解
這篇文章主要給大家介紹了關于Javascript中運算符及流程控制的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2021-10-10
JavaScript中的對象與JSON
這篇文章主要介紹了JavaScript中的對象與JSON,本文講解了定義JSON與javascript對象、javascript對象轉換為JSON、javascript中解析JSON等內容,需要的朋友可以參考下
2015-07-07
JavaScript基礎知識學習筆記
本文是初學javascript的時候記的學習筆記，簡單介紹了javascript的定義及用法，并附上示例，適合初學者們，老鳥請出門左轉。
2014-12-12
javascript操作excel生成報表示例
最近做一個項目,用到javascript操縱excel以生成報表,下面是標有詳細注解的實例
2014-05-05
JavaScript中require和import的區(qū)別詳解
本文詳細講解了JS中require和import的區(qū)別，文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下
2022-06-06
淺談javascript中的加減時間
下面小編就為大家?guī)硪黄獪\談javascript中的加減時間。小編覺得挺不錯的，現在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
2016-07-07
30分鐘就入門的正則表達式基礎教程
30分鐘內讓你明白正則表達式是什么，并對它有一些基本的了解，讓你可以在自己的程序或網頁里使用它。
2013-02-02
從零學JSON之JSON數據結構
這篇文章主要介紹了JSON數據結構的相關知識,需要的朋友可以參考下
2014-05-05
JavaScript基礎介紹與實例
這篇文章介紹了JavaScript的基礎與實例，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2022-02-02
JavaScript面向對象中的封裝和繼承你了解嗎
這篇文章主要為大家詳細介紹了JavaScript面向對象中的封裝和繼承，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
2022-02-02