Data structures and algorithms in JavaScript (3): linked list

We can see that the queue and stack in the JavaScript concept are both a special linear list structure and a relatively simple array-based sequential storage structure. Since the JavaScript interpreter has been directly optimized for arrays, there will not be the problem of fixed length of arrays in many programming languages (it is more difficult to add after the array is full, including adding and deleting, all need to be in the array) All elements change positions, and JavaScript arrays are indeed directly optimized, such as push, pop, shift, unshift, split methods, etc...)

The biggest disadvantage of the sequential storage structure of a linear table is that changing the arrangement of one of the elements will cause changes in the entire collection. The reason is that the storage in the memory is inherently coherent and has no gaps. Deleting one element will naturally make up for it. . After the optimization of this structure, the chain storage structure appeared. To change the way of thinking, we don't care about the arrangement of the data at all. We only need to record the position of the next data inside each element, so use The linear list stored in link mode is called linked list for short. In the linked structure, data = (information address)

In the chain structure, we can also call the address a "chain". A data unit is a node, so it can be said that the linked list is a collection of nodes. Each node has a data block reference pointing to its next node

Array elements are logically referenced based on positional relationships, while linked lists are referenced based on each data element saving a reference pointer relationship

The advantages of this structure are very obvious. When inserting a piece of data, you don’t need to worry about its arrangement at all. You just need to connect the directions of the "chain"

The idea of linked lists in this way is not limited to arrays. We can use objects, as long as there is a reference relationship between objects

Leads generally include singly linked lists, static linked lists, circular linked lists, and doubly linked lists

Singly linked list: It is a very simple downward transmission. Each node only records the information of the next node. Just like Tony Leung in Infernal Affairs, the undercover agent communicates with the online and offline through an intermediary. Once the intermediary is cut off, then I can't prove my identity, so there is a sentence at the end of the film: "I am a good person, who knows?"

Static linked list: It is a linked list described by an array. That is, each table in the array is a "section" containing data and pointers

Circular linked list: Since the singly linked list will only be passed backward, when reaching the end, it will be very troublesome to go back to the head, so the chain of the tail section is connected to the head to form a loop

Double linked list: Optimization for single linked list, so that each section can know who is before and after, so in addition to the back pointer field, there will also be a front pointer field, which improves the search efficiency, but brings some design issues Generally speaking, the complexity is to exchange space for time

To sum up, in fact, the linked list is an optimization method for the sequential storage structure in the linear list. However, in the JavaScript language, due to the particularity of the array (automatically updating the reference position), we can use objects to store the linked list. Structure

Singly linked list

We implement the simplest linked list relationship

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

Copy after login

Directly refer to the next node object through the next of the node object. Initially, the reference through the linked list is implemented. This chain idea is used in the then method in jQuery's asynchronous deferred, and in the jsderferre of Japan's cho45. . There is another most critical issue in this implementation. How do we dynamically insert data after the executed section?

So we must design a traversal method to search the data on this node chain, then find the corresponding data, insert the new section into the current chain, and rewrite the location record

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

Copy after login

This is a method to find the current section, by passing the original head headNode section to search next until the corresponding section information is found

This is implemented using the curry method

Then when inserting a section, the conversion relationship for the linked list address is as follows

In the linked list of a-b-c-d, if you want to insert an f

after c(c.next->d)

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

Add section via insert method

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

Copy after login

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

Copy after login

测试代码：

<!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>

Copy after login

双链表

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

增加节

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

Copy after login

删除节

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

Copy after login

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

测试代码：

<!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>

Copy after login

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

Data structures and algorithms in JavaScript (3): linked list_javascript skills