學習JavaScript數據結構與算法（二）：鏈表

lolomaco 發布于2019-08-22 11:00 / 3296人閱讀

摘要：實現移除給定的元素要移除的元素返回值表示移除成功方法說明移除單向鏈表中某個位置的元素。的前端樂園原文鏈接寒假前端學習學習數據結構與算法二鏈表

本系列的第一篇文章: 學習JavaScript數據結構與算法（一），棧與隊列
第二篇文章：學習JavaScript數據結構與算法（二）：鏈表
第三篇文章：學習JavaScript數據結構與算法（三）：集合
第四篇文章：學習JavaScript數據結構與算法（四）：二叉搜索樹

鏈表簡介

鏈表是一種常見的數據結構，也屬于線性表，但不會按線性的順序來儲存數據。而是在每一個節點中，儲存了下一個節點的指針。可以看圖理解。(有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;
}

不難看出，單向鏈表構造函數比棧與隊列要復雜許多。

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

append(element): 添加元素到鏈表尾部

insert(position,element): 向單向鏈表中某個位置插入元素

indexOf(element): 尋找某個元素在單向鏈表中的位置

remove(element): 移除給定的元素

removeAt(position): 移除單向鏈表中某個位置的元素

getHead(): 獲取單向鏈表的頭部

isAmpty(): 檢查單向鏈表是否為空，為空則返回true

toString(): 將鏈表所有內容以字符串輸出

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;
};

源代碼

以上的就是單向鏈表在JavaScript中的實現，有興趣的同學可以自己下載源代碼查看。

單向鏈表-源代碼

雙向鏈表

雙向鏈表與單向鏈表很是相像。在單向鏈表中，只有指向下一個節點的鏈接。但在雙向鏈表中，還有指向上一個節點的鏈接，是雙向的。
如圖所示:

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;
}

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

append(element): 添加元素到雙向鏈表尾部

insert(position,element): 向雙向鏈表中某個位置插入元素

removeAt(position): 移除雙向鏈表中某個位置的元素

showHead(): 獲取雙向鏈表的頭部

showLength(): 獲取雙向鏈表長度

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;
};

源代碼

源代碼在此~

雙向鏈表-源代碼

感想

鏈表這一節，基本全部都是先按需求寫代碼，寫完后再和書上對比。發現簡直被瞬間秒成渣。自己寫的很多暗坑，邏輯也很混亂。看來還是太年輕了。

有興趣的同學，也可以自己試試只看要求先寫代碼，寫完后再與書上比對，就知道自己的不足了。

前端路漫漫，且行且歌~

最后附上本人博客地址和原文鏈接，希望能與各位多多交流。

Lxxyx的前端樂園
原文鏈接：寒假前端學習(4)——學習JavaScript數據結構與算法（二）：鏈表

GPU云服務器云服務器鏈表算法鏈表排序算法算法 c語言鏈表最小二乘法改進算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/91599.html

CSS技巧

摘要：技巧使你的更加專業這是上關于技巧的一篇譯文，另外你也可以在本項目看到原文。列舉了一些很實用的技巧，比如給空內容的標簽添加內容，逗號分隔列表等等。排序算法看源碼，把它背下來吧排序算法的封裝。主要幫助初學者更好的掌握排序算法的實現。成為專業程序員路上用到的各種優秀資料、神器及框架成為一名專業程序員的道路上，需要堅持練習、學習與積累，技術方面既要有一定的廣度，更要有自己的深度。 Java...

DangoSky 2019-08-22 11:15 評論0 收藏0
CSS技巧

摘要：技巧使你的更加專業這是上關于技巧的一篇譯文，另外你也可以在本項目看到原文。列舉了一些很實用的技巧，比如給空內容的標簽添加內容，逗號分隔列表等等。排序算法看源碼，把它背下來吧排序算法的封裝。主要幫助初學者更好的掌握排序算法的實現。成為專業程序員路上用到的各種優秀資料、神器及框架成為一名專業程序員的道路上，需要堅持練習、學習與積累，技術方面既要有一定的廣度，更要有自己的深度。 Java...

zgbgx 2019-08-29 14:01 評論0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：筆者作為一位，將工作以來用到的各種優秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識點大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會用到。會持續更新… 一、...

Jonathan Shieber 2019-08-29 12:33 評論0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：筆者作為一位，將工作以來用到的各種優秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識點大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會用到。會持續更新… 一、...

SHERlocked93 2019-08-22 11:04 評論0 收藏0
學習數據結構與算法之鏈表

摘要：本系列所有文章第一篇文章學習數據結構與算法之棧與隊列第二篇文章學習數據結構與算法之鏈表第三篇文章學習數據結構與算法之集合第四篇文章學習數據結構與算法之字典和散列表第五篇文章學習數據結構與算法之二叉搜索樹簡單介紹鏈表鏈表一種常見的數據結構，可本系列所有文章：第一篇文章：學習數據結構與算法之棧與隊列第二篇文章：學習數據結構與算法之鏈表第三篇文章：學習數據結構與算法之集合第四篇文章：學習數...

jerryloveemily 2019-08-21 11:50 評論0 收藏0