Web Front-end
JS Tutorial
Introduction to the implementation method of linked list of JavaScript data structure (picture and text)
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&¤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!
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
Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
Compare complex data structures using Java function comparison
Apr 19, 2024 pm 10:24 PM
When using complex data structures in Java, Comparator is used to provide a flexible comparison mechanism. Specific steps include: defining the comparator class, rewriting the compare method to define the comparison logic. Create a comparator instance. Use the Collections.sort method, passing in the collection and comparator instances.
Java data structures and algorithms: in-depth explanation
May 08, 2024 pm 10:12 PM
Data structures and algorithms are the basis of Java development. This article deeply explores the key data structures (such as arrays, linked lists, trees, etc.) and algorithms (such as sorting, search, graph algorithms, etc.) in Java. These structures are illustrated through practical examples, including using arrays to store scores, linked lists to manage shopping lists, stacks to implement recursion, queues to synchronize threads, and trees and hash tables for fast search and authentication. Understanding these concepts allows you to write efficient and maintainable Java code.
In-depth understanding of reference types in Go language
Feb 21, 2024 pm 11:36 PM
Reference types are a special data type in the Go language. Their values do not directly store the data itself, but the address of the stored data. In the Go language, reference types include slices, maps, channels, and pointers. A deep understanding of reference types is crucial to understanding the memory management and data transfer methods of the Go language. This article will combine specific code examples to introduce the characteristics and usage of reference types in Go language. 1. Slices Slices are one of the most commonly used reference types in the Go language.
PHP data structure: The balance of AVL trees, maintaining an efficient and orderly data structure
Jun 03, 2024 am 09:58 AM
AVL tree is a balanced binary search tree that ensures fast and efficient data operations. To achieve balance, it performs left- and right-turn operations, adjusting subtrees that violate balance. AVL trees utilize height balancing to ensure that the height of the tree is always small relative to the number of nodes, thereby achieving logarithmic time complexity (O(logn)) search operations and maintaining the efficiency of the data structure even on large data sets.
Full analysis of Java collection framework: dissecting data structure and revealing the secret of efficient storage
Feb 23, 2024 am 10:49 AM
Overview of Java Collection Framework The Java collection framework is an important part of the Java programming language. It provides a series of container class libraries that can store and manage data. These container class libraries have different data structures to meet the data storage and processing needs in different scenarios. The advantage of the collection framework is that it provides a unified interface, allowing developers to operate different container class libraries in the same way, thereby reducing the difficulty of development. Data structures of the Java collection framework The Java collection framework contains a variety of data structures, each of which has its own unique characteristics and applicable scenarios. The following are several common Java collection framework data structures: 1. List: List is an ordered collection that allows elements to be repeated. Li
Hash table-based data structure optimizes PHP array intersection and union calculations
May 02, 2024 pm 12:06 PM
The hash table can be used to optimize PHP array intersection and union calculations, reducing the time complexity from O(n*m) to O(n+m). The specific steps are as follows: Use a hash table to map the elements of the first array to a Boolean value to quickly find whether the element in the second array exists and improve the efficiency of intersection calculation. Use a hash table to mark the elements of the first array as existing, and then add the elements of the second array one by one, ignoring existing elements to improve the efficiency of union calculations.
PHP SPL data structures: Inject speed and flexibility into your projects
Feb 19, 2024 pm 11:00 PM
Overview of the PHPSPL Data Structure Library The PHPSPL (Standard PHP Library) data structure library contains a set of classes and interfaces for storing and manipulating various data structures. These data structures include arrays, linked lists, stacks, queues, and sets, each of which provides a specific set of methods and properties for manipulating data. Arrays In PHP, an array is an ordered collection that stores a sequence of elements. The SPL array class provides enhanced functions for native PHP arrays, including sorting, filtering, and mapping. Here is an example of using the SPL array class: useSplArrayObject;$array=newArrayObject(["foo","bar","baz"]);$array
Learn the secrets of Go language data structures in depth
Mar 29, 2024 pm 12:42 PM
In-depth study of the mysteries of Go language data structure requires specific code examples. As a concise and efficient programming language, Go language also shows its unique charm in processing data structures. Data structure is a basic concept in computer science, which aims to organize and manage data so that it can be accessed and manipulated more efficiently. By in-depth learning the mysteries of Go language data structure, we can better understand how data is stored and operated, thereby improving programming efficiency and code quality. 1. Array Array is one of the simplest data structures
