摘要：實(shí)現(xiàn)移除給定的元素要移除的元素返回值表示移除成功方法說(shuō)明移除單向鏈表中某個(gè)位置的元素。的前端樂(lè)園原文鏈接寒假前端學(xué)習(xí)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法二鏈表

本系列的第一篇文章: 學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（一），棧與隊(duì)列
第二篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（二）：鏈表
第三篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（三）：集合
第四篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（四）：二叉搜索樹(shù)

鏈表是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，也屬于線性表，但不會(huì)按線性的順序來(lái)儲(chǔ)存數(shù)據(jù)。而是在每一個(gè)節(jié)點(diǎn)中，儲(chǔ)存了下一個(gè)節(jié)點(diǎn)的指針?？梢钥磮D理解。(有C語(yǔ)言基礎(chǔ)的可能比較好理解)。
使用鏈表結(jié)構(gòu)可以克服數(shù)組需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)(C語(yǔ)言的數(shù)組需要預(yù)先定義長(zhǎng)度)，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。

接下來(lái)就是介紹兩種常見(jiàn)的鏈表: 單向鏈表，雙向鏈表在JavaScript中的實(shí)現(xiàn)。

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

首先，創(chuàng)建一個(gè)構(gòu)造函數(shù)。

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

  //單向鏈表的長(zhǎng)度
  var length = 0;
  //單向鏈表的頭結(jié)點(diǎn)，初始化為NULL
  var head = null;
}

不難看出，單向鏈表構(gòu)造函數(shù)比棧與隊(duì)列要復(fù)雜許多。

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

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

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

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

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

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

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

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

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

size(): 返回單向鏈表長(zhǎng)度

說(shuō)明: 向單向鏈表尾部添加元素。
實(shí)現(xiàn):

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

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

說(shuō)明: 向單向鏈表中某個(gè)位置插入元素。
實(shí)現(xiàn):

/**
 * 向單向鏈表中插入某個(gè)元素
 * @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;
  }
};

說(shuō)明：尋找某個(gè)元素在單向鏈表中的位置。
實(shí)現(xiàn):

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

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

  return -1;
};

說(shuō)明: 移除給定的元素。
實(shí)現(xiàn):

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

說(shuō)明:移除單向鏈表中某個(gè)位置的元素。
實(shí)現(xiàn):

/**
 * 移除單向鏈表中某一個(gè)元素
 * @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) {
      // 因?yàn)橹癶ead指向第一個(gè)元素，現(xiàn)在把head修改為指向第二個(gè)元素。
      // 核心概念在于鏈表前后全靠指針鏈接，而非數(shù)組一般。
      // 所以只需要改變head的元素。
      head = current.next;
    } else {
      while (index++ < position) {
        // previous指要操作元素位置之前的那個(gè)元素，current表示之后的那個(gè)元素。
        previous = current;
        current = current.next;
      }

      previous.next = current.next;
    }

    length--;

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

說(shuō)明:獲取單向鏈表的頭部。
實(shí)現(xiàn):

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

實(shí)現(xiàn):

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

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

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

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

以上的就是單向鏈表在JavaScript中的實(shí)現(xiàn)，有興趣的同學(xué)可以自己下載源代碼查看。

單向鏈表-源代碼

雙向鏈表與單向鏈表很是相像。在單向鏈表中，只有指向下一個(gè)節(jié)點(diǎn)的鏈接。但在雙向鏈表中，還有指向上一個(gè)節(jié)點(diǎn)的鏈接，是雙向的。
如圖所示:

首先，依然是構(gòu)造函數(shù):

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

  //雙向鏈表的長(zhǎng)度
  var length = 0;
  //雙向鏈表的頭結(jié)點(diǎn)，初始化為NULL
  var head = null;
  //雙向鏈表的尾結(jié)點(diǎn)，初始化為NULL
  var tail = null;
}

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

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

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

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

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

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

showTail(): 獲取雙向鏈表尾部

說(shuō)明: 添加元素到雙向鏈表尾部
實(shí)現(xiàn):

/**
 * 向鏈表尾部添加元素
 * @param  {Any} element 要加入鏈表的節(jié)點(diǎn)
 * @return {Any}         加入鏈表的節(jié)點(diǎn)
 */
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;
};

說(shuō)明: 向雙向鏈表中某個(gè)位置插入元素。
實(shí)現(xiàn):

/**
 * 向鏈表中插入某個(gè)元素
 * @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;
  }
};

說(shuō)明:移除雙向鏈表中某個(gè)位置的元素。
實(shí)現(xiàn):

/**
 * 移除鏈表中某一個(gè)元素
 * @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;
  }
};

實(shí)現(xiàn):

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

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

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

源代碼在此~

雙向鏈表-源代碼

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

有興趣的同學(xué)，也可以自己試試只看要求先寫(xiě)代碼，寫(xiě)完后再與書(shū)上比對(duì)，就知道自己的不足了。

前端路漫漫，且行且歌~

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

Lxxyx的前端樂(lè)園
原文鏈接：寒假前端學(xué)習(xí)(4)——學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（二）：鏈表