Introduction to the implementation method of linked list of JavaScript data structure (picture and text)

Linked list is a common data structure. It is a structure that dynamically allocates storage. This article mainly introduces the implementation of linked lists in JavaScript data structures, which has a good reference value. Let’s take a look with the editor below

The previous poster discussed the implementation of data structure stacks and queues respectively. The data structures used at that time were all implemented using arrays, but sometimes arrays are not the most optimal. Optimal data structure, for example, when adding and deleting elements in an array, other elements need to be moved, and using the spit() method in JavaScript does not require access to other elements. If you find it slow when using arrays, consider using linked lists.

The concept of linked list

Linked list is a common data structure. It is a structure that dynamically allocates storage. The linked list has a "head pointer" variable, represented by head, which stores an address pointing to an element. Each node uses a reference of an object to point to its successor. A reference pointing to another node is called a chain.

Array elements are referenced by subscripts (positions), while linked list elements are referenced by their relationships. Therefore, the insertion efficiency of linked list is very high. The following figure demonstrates the insertion process of linked list node d:

Deletion process:

Object-based linked list

We define two classes, the Node class and the LinkedList class. Node is the node data, and LinkedList saves the methods for operating the linked list.

First look at the Node class:

function Node(element){
  this.element = element;
   this.next = null;
 }

element is used to save the data on the node, and next is used to save the link pointing to the next node.

LinkedList class:

function LinkedList(){
     this.head = new Node('head');
     this.find = find;
     this.insert = insert;
     this.remove = remove;
     this.show = show;
}

find() method, starting from the head node, searching along the linked list nodes until an element equal to the item content is found, then the node is returned, if not found Returns empty.

function find(item){
     var currentNode = this.head;//从头结点开始
     while(currentNode.element!=item){
         currentNode = currentNode.next;
     }
     return currentNode;//找到返回结点数据，没找到返回null
}

Insert method. As can be seen from the previous element insertion demonstration, there are four simple steps to insert:

1. Create a node

2. Find the target node

3. Modify the target node The next point of the point points to the link

4. Assign the next value of the target node to the next

function insert(newElement,item){
     var newNode = new Node(newElement);
     var currentNode = this.find(item);
     newNode.next = currentNode.next;
     currentNode.next = newNode;
 }

Remove() method of the node to be inserted. To delete a node, you need to first find the previous node of the deleted node. For this we define the method frontNode():

function frontNode(item){
     var currentNode = this.head;
     while(currentNode.next.element!=item&&currentNode.next!=null){
         currentNode = currentNode.next;
     }   
     return currentNode;
}

Three simple steps:

1. Create node

2. Find the previous node of the target node

3. Modify the next node of the previous node to point to the node n after the deleted node

function remove(item){
     var frontNode = this.frontNode(item);
     //console.log(frontNode.element);
     frontNode.next = frontNode.next.next;
 }

Show() method :

function show(){
     var currentNode = this.head,result;
     while(currentNode.next!=null){
         result += currentNode.next.element;//为了不显示head结点
         currentNode = currentNode.next;
     }
}

Test program:

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());

Output:

Doubly linked list

From It is very simple to traverse the linked list from the head node to the tail node, but sometimes, we need to traverse from back to front. At this point we can add a attribute to the Node object, which stores the link to the predecessor node. The poster uses the following diagram to illustrate the working principle of a doubly linked list.

First we add the front attribute to the Node class:

function Node(element){
  this.element = element;
  this.next = null;
   this.front = null;
 }

Of course, we also need to do the corresponding insert() method and remove() method accordingly Modification:

function insert(newElement,item){
  var newNode = new Node(newElement);
  var currentNode = this.find(item);
  newNode.next = currentNode.next;
  newNode.front = currentNode;//增加front指向前驱结点
  currentNode.next = newNode;
}
function remove(item){  
  var currentNode = this.find(item);//找到需要删除的节点
  if (currentNode.next != null) {
    currentNode.front.next = currentNode.next;//让前驱节点指向需要删除的节点的下一个节点
    currentNode.next.front = currentNode.front;//让后继节点指向需要删除的节点的上一个节点
    currentNode.next = null;//并设置前驱与后继的指向为空
    currentNode.front = null;    
  }  
}

Display the linked list in reverse order:

Need to add a method to the doubly linked list to find the last node. The findLast() method finds the last node in the linked list, eliminating the need to traverse the chain from front to back.

function findLast() {//查找链表的最后一个节点
  var currentNode = this.head;
  while (currentNode.next != null) {
    currentNode = currentNode.next;
  }
  return currentNode;
}

Realize reverse order output:

function showReverse() {
  var currentNode = this.head, result = "";
  currentNode = this.findLast(); 
  while(currentNode.front!=null){
    result += currentNode.element + " ";
    currentNode = currentNode.front;
  }
  return result;
}

Test program:

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list);
list.remove("b");
console.log(list.show());
console.log(list.showReverse());

Output:

Loop Linked list

Circular linked list is another form of linked storage structure. Its characteristic is that the pointer field of the last node in the list points to the head node, and the entire linked list forms a ring. Circular linked lists are similar to one-way linked lists, and the node types are the same. The only difference is that when creating a circular linked list, let the next attribute of its head node point to itself, that is:

head.next = head

This behavior It will be transmitted to each node in the linked list, so that the next attribute of each node points to the head node of the linked list. The poster uses the following figure to represent a circular linked list:

ModifyConstruction method:

function LinkedList(){
  this.head = new Node('head');//初始化
  this.head.next = this.head;//直接将头节点的next指向头节点形成循环链表
  this.find = find;
  this.frontNode = frontNode;
  this.insert = insert;
  this.remove = remove;
  this.show = show; 
}

这时需要注意链表的输出方法show()与find()方法，原来的方式在循环链表里会陷入死循环，while循环的循环条件需要修改为当循环到头节点时退出循环。

function find(item){
  var currentNode = this.head;//从头结点开始
  while(currentNode.element!=item&&currentNode.next.element!='head'){
    currentNode = currentNode.next;
  }
  return currentNode;//找到返回结点数据，没找到返回null
}
function show(){
  var currentNode = this.head,result = "";
  while (currentNode.next != null && currentNode.next.element != "head") {   
    result += currentNode.next.element + " ";
    currentNode = currentNode.next;
  }
  return result;
}

测试程序：

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());

测试结果：

The above is the detailed content of Introduction to the implementation method of linked list of JavaScript data structure (picture and text). For more information, please follow other related articles on the PHP Chinese website!