JavaScriptデータ構造とアルゴリズムを勉強します.

本シリーズの第一篇文章:JavaScriptデータ構造とアルゴリズムを勉強します.スタックとキューの第二篇文章:JavaScriptデータ構造とアルゴリズムを勉強します.チェーン表第三篇文章:JavaScriptデータ構造とアルゴリズムを勉強します.
チェーンの概要
チェーンテーブルは一般的なデータ構造であり、線形表にも属しますが、線形の順序でデータを保存することはありません.代わりに、各ノードには、次のノードのポインタが格納されている.図を見て理解できます.(C言語の基礎がある方が理解しやすいかもしれません).リンク構造を使用すると、配列があらかじめデータサイズを知る必要があるという欠点(C言語の配列は長さを予め定義する必要がある)を克服でき、リンク構造はコンピュータメモリ空間を十分に利用し、柔軟なメモリダイナミック管理を実現することができる.
次に、2つのよくあるチェーンを紹介します.一方向チェーン、双方向チェーンはJavaScriptで実現されます.
一方向チェーン
チェーンテーブルの中で一番簡単な形式は一方向チェーンで、チェーンテーブルのノードは全部二つの部分を含んでいます.第一部分は自分の情報を保存しています.第二部分は次のノードを指すポインタが格納されています.最後のノードは、図に示すように、NULLを指す.
JavaScriptにおける一方向チェーンの実現
まず、構造関数を作成します.

/**
 *         
 */
function LinkedList() {
  /**
   *             
   * @param {Any} element         
   */
  var Node = function(element) {
    this.element = element;
    //       
    this.next = null;
  }

  //       
  var length = 0;
  //        ，    NULL
  var head = null;
}

単方向リンク構造関数はスタックとキューよりも複雑であることが分かります.
一方通行のチェーンは次のような方法が必要です.

apped:チェーンテール

に要素を追加します.

insert(position,element):一方向チェーンテーブルのある位置に要素

を挿入する.

indexOf(element):一方向チェーンにある要素の位置を探しています.

remove(element):与えられた要素を除去する

removeAt(position):一方向チェーンのある位置の要素を除去する

get Head():一方向チェーンの頭部を取得する

isAmpty():一方向チェーンが空かどうかをチェックし、空の場合はtrue

に戻ります.

toStering():チェーンのすべての内容を文字列で出力する

size():逆方向リンク長

apped方法:
説明:一方向チェーンの末尾に要素を追加します.実装:

/**
 *            
 * @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;
  }
};

get Head方法:
説明:一方向チェーンの頭部を取得します.実装:

/**
 *          
 * @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での実現です.興味のある学生は自分でソースコードをダウンロードして調べられます.
単方向リンク表-ソースコード
双方向リンク表
双方向チェーンは一方向チェーンとよく似ています.一方向リンクテーブルには、次のノードへのリンクのみがあります.しかし、双方向リンクテーブルには、前のノードへのリンクがあります.双方向です.図のように:
JavaScriptにおける双方向チェーンの実現
まず、依然として構造関数です.

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

双方向チェーンは次のような方法が必要です.

apped(element):双方向リンクテール

に要素を追加する.

insert(position,element):要素

を双方向チェーンテーブルのある位置に挿入する.

removeAt(position):双方向リンク内のある位置の要素を除去する

showHead():双方向チェーンの頭部

を取得する.

showLength():双方向リンク長

を取得する.

showTail():双方向リンクテール

を取得する.
apped方法:
説明:双方向チェーンの末尾に要素を追加して実現する:

/**
 *          
 * @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;
};

ソースコード
ソースコードはここです
双方向リスト-ソースコード
感想
チェーンのこの一節は、基本的には全部需要に応じてコードを書いて、書き終わったら本と比較します.発見は一瞬のうちに断片化された.自分で書いた暗いところが多くて、ロジックも混乱しています.まだ若すぎるようです.
興味のある学生は、自分で試してもいいです.要求だけを見てコードを書いて、書いてから本と比べると、自分の足りないところが分かります.
先の道が長くて、歌を歌っています.
最後に本人のブログの住所と原文のリンクを添付します.
Lxxxyxの先端楽園の原文リンク:冬休みの先端学習(4)――JavaScriptデータ構造とアルゴリズムを学ぶ(2):チェーン表