


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&¤tNode.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&¤tNode.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!

去掉重复并排序的方法:1、使用“Array.from(new Set(arr))”或者“[…new Set(arr)]”语句,去掉数组中的重复元素,返回去重后的新数组;2、利用sort()对去重数组进行排序,语法“去重数组.sort()”。

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于Symbol类型、隐藏属性及全局注册表的相关问题,包括了Symbol类型的描述、Symbol不会隐式转字符串等问题,下面一起来看一下,希望对大家有帮助。

怎么制作文字轮播与图片轮播?大家第一想到的是不是利用js,其实利用纯CSS也能实现文字轮播与图片轮播,下面来看看实现方法,希望对大家有所帮助!

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于对象的构造函数和new操作符,构造函数是所有对象的成员方法中,最早被调用的那个,下面一起来看一下吧,希望对大家有帮助。

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于面向对象的相关问题,包括了属性描述符、数据描述符、存取描述符等等内容,下面一起来看一下,希望对大家有帮助。

方法:1、利用“点击元素对象.unbind("click");”方法,该方法可以移除被选元素的事件处理程序;2、利用“点击元素对象.off("click");”方法,该方法可以移除通过on()方法添加的事件处理程序。

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于BOM操作的相关问题,包括了window对象的常见事件、JavaScript执行机制等等相关内容,下面一起来看一下,希望对大家有帮助。

foreach不是es6的方法。foreach是es3中一个遍历数组的方法,可以调用数组的每个元素,并将元素传给回调函数进行处理,语法“array.forEach(function(当前元素,索引,数组){...})”;该方法不处理空数组。


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

PhpStorm Mac version
The latest (2018.2.1) professional PHP integrated development tool

Safe Exam Browser
Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

SublimeText3 English version
Recommended: Win version, supports code prompts!

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)
