This article mainly introduces the JavaScript data structures of singly linked lists and circular linked lists, and introduces in detail how JavaScript implements singly linked lists and circular linked lists. Those who are interested can learn about the
data structure series. Foreword:
Data structure, as the basic knowledge of programmers, needs to be firmly grasped by each of us. Recently, I have also started a secondary study of data structures to make up for the pits I dug back then. . . . . . When I was in class, I just followed the lectures and did not implement any data structure personally, let alone use data structures to solve problems. Now it’s time to fill the hole. Struggle. I would like to remind the children who read my blog that if you are still in school, never despise the study of any basic course. The hole dug at this time will either need to be filled with double the effort. Either it will directly affect a person's ability, etc. . . . . . Don’t dig a hole for yourself
Let’s get to the point. Regarding the data structure knowledge of linked lists, here is a brief introduction:
Linked lists are non-linear and non-continuous data on physical storage units. Structure (which is linear in data logic), each of its nodes consists of two fields: the data field and the pointer field. The actual data is stored in the data field, and the pointer field stores pointer information, pointing to the next element or the previous element in the linked list. It is precisely because of the existence of pointers that the storage of linked lists is discontinuous in physical units.
The advantages and disadvantages of linked lists are equally obvious. Compared with linear lists, linked lists are more efficient in adding and deleting nodes, because they only need to modify pointer information to complete the operation, unlike linear lists (arrays) that require moving elements. Similarly, the length of a linked list is theoretically infinite (within the memory capacity), and the length can be changed dynamically, which has great advantages over linear lists. Correspondingly, since linear tables cannot randomly access nodes and can only be accessed through pointer traversal queries along the linked list, the efficiency of accessing data elements is relatively low.
The following is the JS part
The common methods and descriptions encapsulated in it:
| Method | Description |
|---|---|
| append(element) | Add node element to the end of the linked list |
| insert(position,element) | Insert node element to position position |
| removeAt(position) | Delete node according to index value position |
| remove(element) | Search and delete the given node element |
| remove() | Delete the last node in the linked list |
| indexOf(element) | Find and return the index value of the given node element |
| Judge whether the linked list is empty | |
| Get the length of the linked list | |
| Convert to string output | |
| Get the head node | |
| Get the tail node |
function LinkedList(){ /*节点定义*/ var Node = function(element){ this.element = element; //存放节点内容 this.next = null; //指针 } var length = 0, //存放链表长度 head = null; //头指针 this.append = function(element){ var node = new Node(element), current; //操作所用指针 if (!head){ head = node; }else { current = head; while(current.next){ current = current.next; } current.next = node; } length++; return true; }; this.insert = function(position, element){ if (position >= 0 && position <= length) { var node = new Node(element), current = head, previous, index = 0; if(position === 0){ node.next = current; head = node; }else{ while(index++ < position){ previous = current; current = current.next; } node.next = current; previous.next = node; } length++; return true; }else{ return false; } }; this.removeAt = function(position){ if(position > -1 && position < length){ var current = head, previous, index = 0; if (position === 0) { head = current.next; }else{ while (index++ < position){ previous = current; current = current.next; } previous.next = current.next; }; length--; return current.element; }else{ return null; } }; this.remove = function(element){ var current = head, previous; if(element === current.element){ head = current.next; length--; return true; } previous = current; current = current.next; while(current){ if(element === current.element){ previous.next = current.next; length--; return true; }else{ previous = current; current = current.next; } } return false; }; this.remove = function(){ if(length < 1){ return false; } var current = head, previous; if(length == 1){ head = null; length--; return current.element; } while(current.next !== null){ previous = current; current = current.next; } previous.next = null; length--; return current.element; }; this.indexOf = function(element){ var current = head, index = 0; while(current){ if(element === current.element){ return index; } index++; current = current.next; } return false; }; this.isEmpty = function(){ return length === 0; }; this.size = function(){ return length; }; this.toString = function(){ var current = head, string = ''; while(current){ string += current.element; current = current.next; } return string; }; this.getHead = function(){ return head; } }
function CircularLinkedList(){ var Node = function(element){ this.element = element; this.next = null; } var length = 0, head = null; this.append = function(element){ var node = new Node(element), current; if (!head) { head = node; node.next = head; }else{ current = head; while(current.next !== head){ current = current.next; } current.next = node; node.next = head; }; length++; return true; }; this.insert = function(position, element){ if(position > -1 && position < length){ var node = new Node(element), index = 0, current = head, previous; if (position === 0) { node.next = head; head = node; }else{ while(index++ < position){ previous = current; current = current.next; } previous.next = node; node.next = current; }; length++; return true; }else{ return false; } }; this.removeAt = function(position){ if(position > -1 && position < length){ var current = head, previous, index = 0; if (position === 0) { head = current.next; }else{ while (index++ < position){ previous = current; current = current.next; } previous.next = current.next; }; length--; return current.element; }else{ return null; } }; this.remove = function (element){ var current = head, previous, indexCheck = 0; while(current && indexCheck < length){ if(current.element === element){ if(indexCheck == 0){ head = current.next; length--; return true; }else{ previous.next = current.next; length--; return true; } }else{ previous = current; current = current.next; indexCheck++; } } return false; }; this.remove = function(){ if(length === 0){ return false; } var current = head, previous, indexCheck = 0; if(length === 1){ head = null; length--; return current.element; } while(indexCheck++ < length){ previous = current; current = current.next; } previous.next = head; length--; return current.element; }; this.indexOf = function(element){ var current = head, index = 0; while(current && index < length){ if(current.element === element){ return index; }else{ index++; current = current.next; } } return false; }; this.isEmpty = function(){ return length === 0; }; this.size = function(){ return length; }; this.toString = function(){ var current = head, string = '', indexCheck = 0; while(current && indexCheck < length){ string += current.element; current = current.next; indexCheck++; } return string; }; }
How to implement circular references between components in Vue.js
There are examples of asynchronous components in Vue
How to solve the maximum call stack error in nodejs
How to implement the blog management platform in Vue SpringBoot
The above is the detailed content of How to use singly linked lists and circular linked lists in JavaScript. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
