JavaScript のデータ構造とアルゴリズム (3): リンクされた list

JavaScript の概念におけるキューとスタックは、特別な線形リスト構造と比較的単純な配列ベースの順次ストレージ構造の両方であることがわかります。 JavaScript インタプリタは配列用に直接最適化されているため、多くのプログラミング言語では配列が固定長であるという問題は発生しません (配列がいっぱいになった後に追加するのはさらに難しく、追加や削除も含めてすべてを行う必要があります)配列内) すべての要素の位置が変更され、JavaScript 配列はプッシュ、ポップ、シフト、シフト解除、分割メソッドなどのように実際に直接最適化されます...)

線形テーブルの順次ストレージ構造の最大の欠点は、要素の 1 つの配置を変更するとコレクション全体が変更されることです。その理由は、メモリ内のストレージが本質的に一貫性があり、ギャップがないためです。要素を 1 つ削除すると、自然に補われます。この構造の最適化後、考え方を変えると、データの配置をまったく気にせず、各要素内の次のデータの位置を記録するだけで済みます。リンクモードで格納される線形リストをリンクリストと略して呼びます。リンク構造ではデータ=(情報アドレス)

となります。

チェーン構造では、アドレスを「チェーン」と呼ぶこともできます。データ単位はノードであるため、リンクされたリストはノードの集合であると言えます。各ノードには、次のノードを指すデータブロック参照があります

配列要素は位置関係に基づいて論理的に参照され、リンクされたリストは参照ポインタ関係を保存する各データ要素に基づいて参照されます

この構造の利点は非常に明白であり、データを挿入するときは、「チェーン」の方向を接続するだけで済みます。

このようなリンクされたリストの考え方は、オブジェクト間に参照関係がある限り、オブジェクトを使用することができます。

リードには通常、単一リンクリスト、静的リンクリスト、循環リンクリスト、二重リンクリストが含まれます

単一リンクリスト: これは非常に単純な下方向への送信です。インファナルアフェアのトニーレオンと同様に、潜入捜査官は仲介者を介してオンラインとオフラインで通信します。が切れると、自分の身元を証明できないので、映画の最後に「私は良い人です、誰にも分かりません。」という一文があります。

静的リンクリスト: 配列で記述されたリンクリストです。つまり、配列内の各テーブルは、データとポインターを含む「セクション」です

循環連結リスト: 単連結リストは逆方向にしか渡されないため、最後まで到達すると先頭に戻るのが非常に面倒なので、尾部のチェーンを先頭に接続して、ループ

ダブルリンクリスト: シングルリンクリストを最適化して、各セクションが前後の位置を把握できるようにするため、バックポインターフィールドに加えてフロントポインターフィールドも追加され、検索効率が向上しますが、いくつかの設計上の問題を引き起こす一般的に言えば、複雑さは空間と時間を交換することです

まとめると、実はリンクリストは線形リストにおける逐次記憶構造の最適化手法ですが、JavaScript言語では配列の特殊性(参照位置の自動更新)により、オブジェクトを使用してリンクされたリストを保存できます

。

単一リンクリスト

最も単純なリンクリスト関係を実装します

function createLinkList() {
  var _this = {},
    prev = null;
  return {
    add: function(val) {
      //保存当前的引用
      prev = {
        data: val,
        next: prev || null
      }
    }
  }
}
var linksList = createLinkList(); 
linksList.add("arron1"); 
linksList.add("arron2"); 
linksList.add("arron3");
//node节的next链就是 -arron3-arron2-arron1

ログイン後にコピー

ノードオブジェクトのnextを介して次のノードオブジェクトを直接参照するこのチェーンの考え方は、jQueryの非同期deferredのthenメソッドや日本のcho45のjsderferreで最初に実装されています。。この実装には、実行されたセクションの後にデータを動的に挿入する方法がもう 1 つあります。

したがって、このノードチェーン上のデータを検索し、対応するデータを見つけて、新しいセクションを現在のチェーンに挿入し、位置レコードを書き換えるトラバーサルメソッドを設計する必要があります

//在链表中找到对应的节
var findNode = function createFindNode(currNode) {
  return function(key){
    //循环找到执行的节，如果没有返回本身
    while (currNode.data != key) {
      currNode = currNode.next;
    }
    return currNode;        
  }
}(headNode);

ログイン後にコピー

これは、元の先頭の headNode セクションを渡して、対応するセクション情報が見つかるまで次に検索することで、現在のセクションを見つける方法です

これはカリーメソッドを使用して実装されています

そしてセクション挿入時のリンクリストアドレスの変換関係は以下のようになります

a-b-c-d のリンクリストで、c(c.next->d) の後に f

を挿入したい場合

a-b-c-f-d 、次に c,next->f 、 f.next-d

insert メソッドを使用してセクションを追加

首先分离出createNode节的构建，在初始化的时候先创建一个头部节对象用来做节开头的初始化对象

在insert增加节方法中，通过对headNode链的一个查找，找到对应的节，把新的节给加后之后，最后就是修改一下链的关系

如何从链表中删除一个节点？

由于链表的特殊性，我们a->b->c->d ，如果要删除c那么就必须修改b.next->c为 b.next->d，所以找到前一个节修改其链表next地址，这个有点像dom操作中removeChild找到其父节点调用移除子节点

同样的我们也在remove方法的设计中，需要设计一个遍历往上回溯一个父节点即可

//找到前一个节
var findPrevious = function(currNode) {
  return function(key){
    while (!(currNode.next == null) &&
      (currNode.next.data != key)) {
      currNode = currNode.next;
    }
    return currNode;      
  }
}(headNode);

//插入方法
this.remove = function(key) {
  var prevNode = findPrevious(key);
  if (!(prevNode.next == null)) {
    //修改链表关系
    prevNode.next = prevNode.next.next;
  }
};

ログイン後にコピー

测试代码：

<!doctype html><button id="test1">插入多条数据</button>
<button id="test2">删除Russellville数据</button><div id="listshow"><br /></div><script type="text/javascript">
 //////////
 //创建链表 //
 //////////
 function createLinkList() {

 //创建节
 function createNode(data) {
  this.data = data;
  this.next = null;
 }

 //初始化头部节
 //从headNode开始形成一条链条
 //通过next衔接
 var headNode = new createNode("head");

 //在链表中找到对应的节
 var findNode = function createFindNode(currNode) {
  return function(key) {
  //循环找到执行的节，如果没有返回本身
  while (currNode.data != key) {
   currNode = currNode.next;
  }
  return currNode;
  }
 }(headNode);

 //找到前一个节
 var findPrevious = function(currNode) {
  return function(key) {
  while (!(currNode.next == null) &&
   (currNode.next.data != key)) {
   currNode = currNode.next;
  }
  return currNode;
  }
 }(headNode);


 //插入一个新节
 this.insert = function(data, key) {
  //创建一个新节
  var newNode = new createNode(data);
  //在链条中找到对应的数据节
  //然后把新加入的挂进去
  var current = findNode(key);
  //插入新的接，更改引用关系
  //1:a-b-c-d
  //2:a-b-n-c-d
  newNode.next = current.next;
  current.next = newNode;
 };

 //插入方法
 this.remove = function(key) {
  var prevNode = findPrevious(key);
  if (!(prevNode.next == null)) {
  //修改链表关系
  prevNode.next = prevNode.next.next;
  }
 };


 this.display = function(fn) {
  var currNode = headNode;
  while (!(currNode.next == null)) {
  currNode = currNode.next;
  fn(currNode.data)
  }
 };

 }


 var cities = new createLinkList();

 function create() {
 var text = '';
 cities.display(function(data) {
  text += '-' + data;
 });
 var div = document.createElement('div')
 div.innerHTML = text;
 document.getElementById("listshow").appendChild(div)
 }

 document.getElementById("test1").onclick = function() {
 cities.insert("Conway", "head");
 cities.insert("Russellville", "Conway");
 cities.insert("Carlisle", "Russellville");
 cities.insert("Alma", "Carlisle");
 create();
 }

 document.getElementById("test2").onclick = function() {
 cities.remove("Russellville");
 create()
 }

</script>

ログイン後にコピー

双链表

原理跟单链表是一样的，无非就是给每一个节增加一个前链表的指针

增加节

//插入一个新节
this.insert = function(data, key) {
  //创建一个新节
  var newNode = new createNode(data);
  //在链条中找到对应的数据节
  //然后把新加入的挂进去
  var current = findNode(headNode,key);
  //插入新的接，更改引用关系
  newNode.next   = current.next;
  newNode.previous = current
  current.next   = newNode;
};

ログイン後にコピー

删除节

this.remove = function(key) {
  var currNode = findNode(headNode,key);
  if (!(currNode.next == null)) {
    currNode.previous.next = currNode.next;
    currNode.next.previous = currNode.previous;
    currNode.next     = null;
    currNode.previous   = null;
  }
};

ログイン後にコピー

在删除操作中有一个明显的优化：不需要找到父节了，因为双链表的双向引用所以效率比单链要高

测试代码：

<!doctype html><button id="test1">插入多条数据</button>
<button id="test2">删除Russellville数据</button><div id="listshow"><br /></div><script type="text/javascript">

 //////////
 //创建链表 //
 //////////
 function createLinkList() {

 //创建节
 function createNode(data) {
  this.data = data;
  this.next = null;
  this.previous = null
 }

   //初始化头部节
 //从headNode开始形成一条链条
 //通过next衔接
 var headNode = new createNode("head");

 //在链表中找到对应的数据
 var findNode = function(currNode, key) {
  //循环找到执行的节，如果没有返回本身
  while (currNode.data != key) {
  currNode = currNode.next;
  }
  return currNode;
 }

 //插入一个新节
 this.insert = function(data, key) {
  //创建一个新节
  var newNode = new createNode(data);
  //在链条中找到对应的数据节
  //然后把新加入的挂进去
  var current = findNode(headNode,key);
  //插入新的接，更改引用关系
  newNode.next   = current.next;
  newNode.previous = current
  current.next   = newNode;
 };

 this.remove = function(key) {
  var currNode = findNode(headNode,key);
  if (!(currNode.next == null)) {
  currNode.previous.next = currNode.next;
  currNode.next.previous = currNode.previous;
  currNode.next     = null;
  currNode.previous   = null;
  }
 };

 this.display = function(fn) {
  var currNode = headNode;
  while (!(currNode.next == null)) {
  currNode = currNode.next;
  fn(currNode.data)
  }
 };

 }


 var cities = new createLinkList();

 function create() {
 var text = '';
 cities.display(function(data) {
  text += '-' + data;
 });
 var div = document.createElement('div')
 div.innerHTML = text;
 document.getElementById("listshow").appendChild(div)
 }

 document.getElementById("test1").onclick = function() {
 cities.insert("Conway", "head");
 cities.insert("Russellville", "Conway");
 cities.insert("Carlisle", "Russellville");
 cities.insert("Alma", "Carlisle");
 create();
 }

 document.getElementById("test2").onclick = function() {
 cities.remove("Russellville");
 create()
 }


</script>

ログイン後にコピー

git代码下载：https://github.com/JsAaron/data_structure.git

JavaScript のデータ構造とアルゴリズム (3): リンクされた list_javascript スキル