JavaScriptのデータ構造とアルゴリズム連結一覧_基礎知識-jsチュートリアル-php.cn

リンクされたリストの概要

リンクリストは一般的なデータ構造であり、線形リストでもありますが、データを線形順序で格納しません。代わりに、各ノードには、次のノードへのポインタが格納されます。写真を見れば分かります。 (C 言語の背景がある人は理解しやすいかもしれません)。
リンクリスト構造を使用すると、データサイズを事前に知っておく必要がある配列の欠点 (C 言語の配列では事前に定義された長さが必要) を克服でき、コンピュータのメモリ空間を最大限に活用して、次のような結果を得ることができます。柔軟な動的メモリ管理。
次に、2 つの一般的なリンクリスト、一方向リンクリストと JavaScript での二重リンクリストの実装を紹介します。

一方向リンクリスト

リンクリストの最も単純な形式は、一方向リンクリストです。リンクリスト内のノードには 2 つの部分が含まれており、最初の部分には独自の情報が格納され、2 番目の部分には次のノードへのポインターが格納されます。最後のノードは 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(): 一方向リンクリストの長さを返します

追加メソッド:

説明: 一方向リンクリストの末尾に要素を追加します。
実装:

/**
 * 向单向链表尾部添加元素
 * @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++;
};

ログイン後にコピー

メソッドの挿入:

説明: 一方向リンクリストの特定の位置に要素を挿入します。
実装:

/**
 * 向单向链表中插入某个元素
 * @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;
 }
};

ログイン後にコピー

メソッドのインデックス:

説明: 一方向リンクリスト内の要素の位置を検索します。
実装:

/**
 * 寻找某个元素在单向链表中的位置
 * @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;
};

ログイン後にコピー

メソッドの削除:

説明: 指定された要素を削除します。
実装:

/**
 * 移除给定的元素
 * @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;
}

ログイン後にコピー

二重リンクリストには次のメソッドが必要です:

append(element): 二重リンクリストの末尾に要素を追加します
insert(position,element): 二重リンクリスト内の特定の位置に要素を挿入します
removeAt(position): 二重リンクリスト内の特定の位置にある要素を削除します
showHead(): 二重リンクリストの先頭を取得します
showLength(): 二重リンクリストの長さを取得します
showTail(): 二重リンクリストの末尾を取得します

追加メソッド:

説明: 二重リンクリストの末尾に要素を追加します
実装:

/**
 * 向链表尾部添加元素
 * @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;
};

ログイン後にコピー

メソッドの挿入:

説明: 二重リンクリスト内の特定の位置に要素を挿入します。
実装:

/**
 * 向链表中插入某个元素
 * @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;
};

ログイン後にコピー

感想

リンクリストに関するこのセクションでは、基本的にすべてのコードは最初に要件に従って記述され、記述後に本と比較されます。あっという間にゴミと化したことが判明した。私の文章には多くの落とし穴があり、論理も非常にわかりにくいです。彼はまだ若すぎるようだ。