社群 學習 工具庫 休閒
搜尋
繁体中文
首頁 > web前端 > js教程 > 主體

JavaScript資料結構與演算法之鍊錶_基礎知識

WBOY
發布： 2016-05-16 15:16:54
原創
1035 人瀏覽過

鍊錶簡介

鍊錶是一種常見的資料結構，也屬於線性表，但不會以線性的順序來儲存資料。而是在每一個節點中，儲存了下一個節點的指標。可以看圖理解。 (有C語言基礎的可能比較好理解)。
使用鍊錶結構可以克服陣列需要預先知道資料大小的缺點(C語言的陣列需要預先定義長度)，鍊錶結構可以充分利用電腦記憶體空間，實現靈活的記憶體動態管理。
接下來就是介紹兩種常見的鍊錶: 單向鍊錶，雙向鍊錶在JavaScript中的實作。

單向鍊錶

鍊錶中最簡單的形式就是單向鍊錶，鍊錶中的節點都包含兩個部分，第一部分儲存著自身訊息，第二部分則儲存有指向下一節點的指標。最後一個節點則指向NULL:

JavaScipt中單向鍊錶的實作

首先，建立一個建構函式。 

/**
 * 单向链表构造函数
 */
function LinkedList() {
 /**
  * 单向链表中节点的构造函数
  * @param {Any} element 要传入链表的节点
  */
 var Node = function(element) {
  this.element = element;
  //下个节点的地址
  this.next = null;
 }

 //单向链表的长度
 var length = 0;
 //单向链表的头结点，初始化为NULL
 var head = null;
}
登入後複製

不難看出，單向鍊錶建構函式比棧與佇列要複雜許多。
單向鍊錶需要有以下的方法:

  1. append(element): 加入元素到鍊錶尾部
  2. insert(position,element): 向單向鍊錶中某個位置插入元素
  3. indexOf(element): 尋找某個元素在單向鍊錶中的位置
  4. remove(element): 移除給定的元素
  5. removeAt(position): 移除單向鍊錶中某個位置的元素
  6. getHead(): 取得單向鍊錶的頭部
  7. isAmpty(): 檢查單向鍊錶是否為空，為空則回傳true
  8. toString(): 將鍊錶所有內容以字串輸出
  9. size(): 傳回單向鍊錶長度

append方法:

說明: 在單向鍊錶尾部新增元素。
實作:

/**
 * 向单向链表尾部添加元素
 * @param {Any} element 要加入链表的节点
 */
this.append = function(element) {
 var node = new Node(element);
 var current;

 if (head == null) {
  head = node;
 } else {
  // 当前项等于链表头部元素.
  // while循环到最后一个，从而将该节点加入链表尾部。
  current = head;
  // 当next为null时，判定为false。退出循环。
  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;
};
登入後複製

雙向鍊錶

雙向鍊錶與單向鍊錶很是相像。在單向鍊錶中，只有指向下一個節點的連結。但在雙向鍊錶中，還有指向上一個節點的鏈接，是雙向的。

JavaScipt中雙向鍊錶的實作

首先，依然是建構子:

/**
 * 双向链表的构造函数
 */
function DoublyLinkedList() {
 /**
  * 双向链表中节点的构造函数
  * @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;
}
登入後複製

雙向鍊錶需要有以下的方法:

  1. append(element): 加入元素到雙向鍊錶尾部
  2. insert(position,element): 向雙向鍊錶中某個位置插入元素
  3. removeAt(position): 移除雙向鍊錶中某個位置的元素
  4. showHead(): 取得雙向鍊錶的頭部
  5. showLength(): 取得雙向鍊錶長度
  6. showTail(): 取得雙向鍊錶尾部

append方法:

說明: 新增元素到雙向鍊錶尾部
實作:

/**
 * 向链表尾部添加元素
 * @param {Any} element 要加入链表的节点
 * @return {Any}     加入链表的节点
 */
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;
};
登入後複製

感想

鍊錶這一節，基本上全部都是先依照需求寫程式碼，寫完後再和書上比較。發現簡直被瞬間秒成渣。自己寫的很多暗坑，邏輯也很混亂。看來還是太年輕了。

相關標籤：
JavaScript数据结构与算法 JavaScript链表
來源：php.cn
上一篇：理解javascript中的嚴格模式_javascript技巧 下一篇：深入探秘jquery瀑布流的實現_jquery
本網站聲明
本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn
作者最新文章
最新問題
**錯誤類型：無法迭代的'NoneType'物件** 我想使用ssh隧道來存取Mysql資料庫。不幸的是，此程式碼的體系結構似乎不支援我的查詢格式，因為該函數似乎與我的查詢格式不相容。 /Users/peter/PycharmProj...
來自於 2024-04-06 10:26:38
0
1
378
在個人伺服器上使用 mysql 資料庫部署 Django 我正在努力在Linode上部署我的Django專案。我在開發過程中使用的MySQL資料庫位於我家的ubuntu伺服器上。這與我編寫程式的計算機不同。在settings.py檔案中，...
來自於 2024-03-31 14:44:26
0
1
371
如何在Vue中存取不同v-for循環中的數據 我在我的Vue應用程式中有一個表格主體，在其中我透過循環一個資料物件來建構一部分行。然後，我有一個單獨的部分使用不同的資料對象，但是，我需要將其值與另一個循環中的值進行比較，以便進...
來自於 2024-03-31 14:54:54
0
1
348
相關專題
更多>
熱門推薦
熱門教學
更多>
相關教學
熱門推薦
最新課程
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板