Struktur data dan algoritma dalam JavaScript (3): kemahiran senarai_javascript terpaut

Kita dapat melihat bahawa baris gilir dan tindanan dalam konsep JavaScript ialah struktur senarai linear khas dan struktur storan jujukan berasaskan tatasusunan yang agak mudah. Memandangkan penterjemah JavaScript telah dioptimumkan secara langsung untuk tatasusunan, tidak akan ada masalah panjang tetap tatasusunan dalam banyak bahasa pengaturcaraan (lebih sukar untuk ditambah selepas tatasusunan penuh, termasuk menambah dan memadam, semuanya perlu dalam tatasusunan) Semua elemen menukar kedudukan dan tatasusunan JavaScript sememangnya dioptimumkan secara langsung, seperti kaedah push, pop, shift, unshift, split, dll...)

Kelemahan terbesar struktur storan berjujukan jadual linear ialah mengubah susunan salah satu elemen akan menyebabkan perubahan dalam keseluruhan koleksi Sebabnya ialah storan dalam memori sememangnya koheren dan tidak mempunyai jurang. Memadamkan satu elemen secara semula jadi akan menggantikannya. Selepas pengoptimuman struktur ini, struktur storan rantaian muncul Untuk mengubah cara berfikir, kami tidak peduli sama sekali tentang susunan data Kami hanya perlu merekodkan kedudukan data seterusnya di dalam setiap elemen, jadi gunakan Senarai linear yang disimpan dalam mod pautan dipanggil senarai terpaut dalam struktur terpaut, data = (alamat maklumat)

Dalam struktur rantai, kita juga boleh memanggil alamat sebagai "rantai". Unit data ialah nod, jadi boleh dikatakan senarai terpaut ialah koleksi nod. Setiap nod mempunyai rujukan blok data yang menunjuk ke nod seterusnya

Elemen tatasusunan dirujuk secara logik berdasarkan hubungan kedudukan, manakala senarai terpaut dirujuk berdasarkan setiap elemen data menyimpan hubungan penunjuk rujukan

Kelebihan struktur ini sangat jelas apabila memasukkan sekeping data, anda tidak perlu risau tentang susunannya Anda hanya perlu menyambungkan arah "rantai"

Idea senarai terpaut dengan cara ini tidak terhad kepada tatasusunan Kita boleh menggunakan objek, selagi terdapat hubungan rujukan antara objek

Petunjuk biasanya termasuk senarai terpaut tunggal, senarai terpaut statik, senarai pautan bulat dan senarai terpaut dua kali

Senarai pautan tunggal: Ia adalah penghantaran ke bawah yang sangat mudah Setiap nod hanya merekodkan maklumat nod seterusnya Sama seperti Tony Leung dalam Infernal Affairs, ejen menyamar berkomunikasi dengan dalam talian dan luar talian melalui perantara terputus, maka saya tidak dapat membuktikan identiti saya, jadi ada ayat di akhir filem: "Saya seorang yang baik, siapa tahu?"

Senarai terpaut statik: Ia ialah senarai terpaut yang diterangkan oleh tatasusunan. Iaitu, setiap jadual dalam tatasusunan ialah "bahagian" yang mengandungi data dan penunjuk

Senarai pautan bulat: Oleh kerana senarai pautan tunggal hanya akan dihantar ke belakang, apabila sampai ke penghujung, ia akan menjadi sangat menyusahkan untuk kembali ke kepala, jadi rantai bahagian ekor disambungkan ke kepala untuk membentuk gelung

Senarai pautan berganda: Pengoptimuman untuk senarai pautan tunggal, supaya setiap bahagian boleh mengetahui siapa sebelum dan selepas, jadi selain medan penunjuk belakang, terdapat juga medan penunjuk hadapan, yang meningkatkan kecekapan carian, tetapi membawa beberapa isu reka bentuk Secara umumnya, kerumitan adalah untuk menukar ruang untuk masa

Ringkasnya, sebenarnya, senarai terpaut ialah kaedah pengoptimuman untuk struktur storan berjujukan dalam senarai linear Walau bagaimanapun, dalam bahasa JavaScript, disebabkan kekhususan tatasusunan (mengemas kini kedudukan rujukan secara automatik), kami boleh menggunakan objek untuk menyimpan senarai terpaut

Senarai pautan tunggal

Kami melaksanakan perhubungan senarai terpaut paling mudah

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

Rujuk terus pada objek nod seterusnya melalui objek nod seterusnya Pada mulanya, rujukan melalui senarai terpaut ini digunakan dalam kaedah kemudian dalam tertunda asynchronous jQuery, dan dalam jsderferre cho45 Jepun. . Terdapat satu lagi isu paling kritikal dalam pelaksanaan ini. Bagaimanakah kita boleh memasukkan data secara dinamik selepas bahagian yang dilaksanakan?

Jadi kita mesti mereka bentuk kaedah traversal untuk mencari data pada rantaian nod ini, kemudian cari data yang sepadan, masukkan bahagian baharu ke dalam rantai semasa dan tulis semula rekod lokasi

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

Ini ialah kaedah untuk mencari bahagian semasa, dengan melepasi bahagian headNode kepala asal untuk mencari seterusnya sehingga maklumat bahagian yang sepadan ditemui

Ini dilaksanakan menggunakan kaedah kari

Kemudian apabila memasukkan bahagian, hubungan penukaran untuk alamat senarai terpaut adalah seperti berikut

Dalam senarai terpaut a-b-c-d, jika anda ingin memasukkan f

selepas c(c.next->d)

a-b-c-f-d , kemudian c,next->f , f.next-d

Tambah bahagian melalui kaedah sisipan

//创建节
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);

//插入一个新节
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;
};

首先分离出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