Two way linked list: I'm no longer one-way driving

The journey of ants 2021-05-03 19:20:04
way linked list longer one-way


Unlike a single linked list , Each node of the two-way linked list contains data , It also includes pointers to its front and back nodes

img

In fact, double linked list is better than single linked list , A pointer to the previous node is added to the node

Now I'll write a double linked list , Implement some methods :

img

Let's first implement a node constructor :

class Node {
constructor(element) {
this.element = element; // Node data value 
this.next = null; // Front pointer 
this.prev = null; // The back pointer 
}
}
 Copy code 

The overall structure of two-way linked list

class DoubleLinkedList {
constructor() {
this.count = 0; // Record the number of nodes 
this.head = null; // Two way linked list head 
this.tail = null; // The tail of a two-way linked list 
}
// Add nodes at the end of the list 
add(element) {}
// Add a node at the specified location in the linked list 
addAt(index, element) {}
// Remove the node at the specified position in the linked list 
removeAt(index) {}
// Remove the specified node from the list 
remove(element) {}
// Flip list 
reverse() {}
// Swap the positions of the two nodes 
swap() {}
// Traversing the linked list 
traverse() {}
// Find the index of a node 
find() {}
// Check whether the linked list is empty 
isEmpty() {}
// The length of the query list 
length() {}
}
 Copy code 

The next step is to realize one by one

According to the location ( Indexes ) Find node , The next method will always use this method , Just encapsulate it as a method , In order to call

getElement(index) {
if (index >= 0 && index < this.count) {
let node = this.head;
// Loop to the node 
for (let i = 0; i < index; i++) {
node = node.next;
}
return node;
}
return undefined;
}
 Copy code 

1、 Add a node

img

1.1 Add a node at the tail

// Pass in a node 
add(element) {
// Create a node first 
const node = new Node(element);
// If the list is empty , That is, both the head node and the tail node are node 了 
if (this.head === null && this.tail === null) {
this.head = node;
this.tail = node
}
// If the linked list already has a head , Then add a node at the tail 
else {
node.prev = this.tail;
this.tail.next = node;
this.tail = node;
}
// Total number of nodes +1
this.count++;
}
 Copy code 

1.2 Add a node at the specified location in the linked list

addAt(index, element) {
if (index >= 0 && index <= this.count) {
const node = new Node(element);
// When inserted in the head 
if (index === 0) {
this.head.prev = node;
node.next = this.head;
this.head = node;
}
// Insert nodes at the end 
else if (index === this.count) {
this.add(element)
this.count--;
}
// Insert nodes in the middle 
else {
let current = this.getElement(index);
// First, set the relationship between the new node and the previous node 
node.prev = current.prev;
current.prev.next = node;
// Then set the new relationship with the next node 
node.next = current;
current.prev = node
}
this.count++;
return true
}
return false;
}
 Copy code 

2、 Remove node

img

2.1、 Remove the node at the specified position in the linked list

removeAt(index) {
if (index >= 0 && index < this.count) {
// Remove the head node 
if (index === 0) {
this.head = this.head.next;
this.head.prev = null;
}
// Remove tail nodes 
else if (index === this.count - 1) {
this.tail = this.tail.prev;
this.tail.next = null;
}
// Remove intermediate nodes 
else {
let current = this.getElement(index);
current.next.prev = current.prev
current.prev.next = current.next
}
this.count--;
return true
}
return undefined;
}
 Copy code 

2.2、 Remove the specified node from the list

Remove the specified node , The first step is to find the node

remove(element) {
let current = this.head;
while (current) {
if (current === element) {
// A linked list has only one node 
if (current === this.head && current === this.prev) {
this.head = null;
this.tail = null;
}
// Remove the head node 
else if (current === this.head) {
this.head = this.head.next;
this.head.prev = null;
}
// Remove tail nodes 
else if (current === this.tail) {
this.tail = this.tail.prev;
this.tail.next = null;
}
// Remove intermediate nodes 
else {
current.next.prev = current.prev;
current.prev.next = current.next;
}
this.count--;
}
current = current.next;
}
}
 Copy code 

5、 Flip list

reverse() {
let current = this.head;
let prev = null;
// First put the middle 
while (current) {
let next = current.next;
// hysteron proteron 
current.next = prev;
current.prev = next;
prev = current;
current = next
}
this.tail = this.head;
this.head = prev
}
 Copy code 

6、 Swap the positions of the two nodes

swap(index1, index2) {
if (index1 >= 0 && index1 < this.count && index2 >= 0 && index2 < this.count) {
let node1 = this.getElement(index1)
let node2 = this.getElement(index2)
// Give Way index1 Always less than index2, Convenient for later search and exchange 
if (index1 > index2) {
return this.swap(index2, index1)
}
// Exchange the values of two nodes 
[node1.element, node2.element] = [node2.element, node1.element]
return true
}
return undefined;
}
 Copy code 

7、 Traversing the linked list

display() {
if (!this.isEmpty()) {
let current = this.head;
let result = '';
while (current) {
result += current.element
current = current.next
if (current) {
result += '->';
}
}
return result;
}
return undefined;
}
 Copy code 

8、 Find the index of a node

find(element) {
let current = this.head;
let index = 0
while (current) {
if (current === element) {
return index;
}
current = current.next;
index++;
}
return undefined
}
 Copy code 

9、 Check whether the linked list is empty

isEmpty() {
return this.count === 0
}
 Copy code 

10、 The length of the query list

length() {
return this.count;
}
 Copy code 

Integration :

// Implement a node constructor 
class Node {
constructor(element) {
this.element = element;
this.next = null;
this.prev = null;
}
}
// Double linked list 
class DoubleLinkedList {
constructor() {
this.count = 0; // Record the number of nodes 
this.head = null; // Two way linked list head 
this.tail = null; // The tail of a two-way linked list 
}
// Traverse a method , Loop to the target location 
getElement(index) {
if (index >= 0 && index < this.count) {
let node = this.head;
for (let i = 0; i < index; i++) {
node = node.next;
}
return node;
}
return undefined;
}
// Add nodes at the end of the list 
add(element) {
// Create a node first 
const node = new Node(element);
// If the list is empty 
if (this.head === null && this.tail === null) {
this.head = node;
this.tail = node
}
// If the linked list already has a head , Then add a node at the tail 
else {
node.prev = this.tail;
this.tail.next = node;
this.tail = node;
}
this.count++;
}
// Add a node at the specified location in the linked list 
addAt(index, element) {
if (index >= 0 && index <= this.count) {
const node = new Node(element);
// When inserted in the head 
if (index === 0) {
this.head.prev = node;
node.next = this.head;
this.head = node;
} else if (index === this.count) {
this.add(element)
this.count--;
}
// When the head is not inserted 
else {
let current = this.getElement(index);
// First, set the relationship between the new node and the previous node 
node.prev = current.prev;
current.prev.next = node;
// Then set the new relationship with the next node 
node.next = current;
current.prev = node
}
this.count++;
return true
}
return false;
}
// Remove the node at the specified position in the linked list 
removeAt(index) {
if (index >= 0 && index < this.count) {
// Remove the head node 
if (index === 0) {
this.head = this.head.next;
this.head.prev = null;
}
// Remove tail nodes 
else if (index === this.count - 1) {
this.tail = this.tail.prev;
this.tail.next = null;
}
// Remove intermediate nodes 
else {
let current = this.getElement(index);
current.next.prev = current.prev
current.prev.next = current.next
}
this.count--;
return true
}
return undefined;
}
// Remove the specified node from the list 
remove(element) {
let current = this.head;
while (current) {
if (current === element) {
// A linked list has only one node 
if (current === this.head && current === this.prev) {
this.head = null;
this.tail = null;
}
// Remove the head node 
else if (current === this.head) {
this.head = this.head.next;
this.head.prev = null;
}
// Remove tail nodes 
else if (current === this.tail) {
this.tail = this.tail.prev;
this.tail.next = null;
}
// Remove intermediate nodes 
else {
current.next.prev = current.prev;
current.prev.next = current.next;
}
this.count--;
}
current = current.next;
}
}
// Flip list 
reverse() {
let current = this.head;
let prev = null;
while (current) {
let next = current.next;
// hysteron proteron 
current.next = prev;
current.prev = next;
prev = current;
current = next
}
this.tail = this.head;
this.head = prev
}
// Swap the positions of the two nodes 
swap(index1, index2) {
if (index1 >= 0 && index1 < this.count && index2 >= 0 && index2 < this.count) {
let node1 = this.getElement(index1)
let node2 = this.getElement(index2)
// Give Way index1 Always less than index2, Convenient for later search and exchange 
if (index1 > index2) {
return this.swap(index2, index1)
}
// Exchange the values of two nodes 
[node1.element, node2.element] = [node2.element, node1.element]
return true
}
return undefined;
}
// Traversing the linked list 
display() {
if (!this.isEmpty()) {
let current = this.head;
let result = '';
while (current) {
result += current.element
current = current.next
if (current) {
result += '->';
}
}
return result;
}
return undefined;
}
// Find the index of a node 
find(element) {
let current = this.head;
let index = 0
while (current) {
if (current === element) {
return index;
}
current = current.next;
index++;
}
return undefined
}
// Check whether the linked list is empty 
isEmpty() {
return this.count === 0
}
// The length of the query list 
length() {
return this.count;
}
}
 Copy code 

Let's call :

// First instantiate a bidirectional linked list object 
let DLL = new DoubleLinkedList();
// Tail add 
DLL.add(1);
DLL.add(2);
// Add... Anywhere 
DLL.addAt(0, 3);
DLL.addAt(3, 6);
// Traverse 
console.log(DLL.display()); // 3->1->2->6
// Delete... According to location 
DLL.removeAt(3);
// Swap two nodes 
DLL.swap(0, 2)
console.log(DLL.display()); // 2->1->3
// Flip 
DLL.reverse();
// Is the list empty 
console.log(DLL.isEmpty()); // false
// Chain length 
console.log(DLL.length()); // 3
 Copy code 

summary :

  • So you'll find that implementing a linked list is nothing more than adding ( Add a node ) Delete ( Delete node ) Change ( In exchange for ) check ( Traverse )
  • Adding and deleting nodes is nothing more than modifying the pointer of nodes
版权声明
本文为[The journey of ants]所创,转载请带上原文链接,感谢
https://qdmana.com/2021/05/20210503191542840o.html

  1. CSS layout
  2. Application scenario explanation of Vue dynamic component
  3. Redux learning notes 04 -- using multiple reducers to manage data
  4. After three months of typescript writing, what have I learned?
  5. Node family - what is a callback?
  6. React -- a simple implementation of render & create element
  7. JS learning simple usage of jquery
  8. Seamless love
  9. 小白前端入门笔记(12),设置哑链接
  10. Small white front-end entry notes (12), set dumb links
  11. Vue2. X opens composition API and TSX
  12. Interview record and thinking of social recruitment for one and a half years (Alibaba, Tencent, baidu offer)
  13. Flex learning notes
  14. The most essential closure article in the eastern hemisphere
  15. 2021-05-03 hot news
  16. Sword finger offer -- reverse order pair in array (JS Implementation)
  17. Working process of scaffold
  18. Use decorator mode to strengthen your fetch
  19. [JS] scope (Introduction)
  20. Employment information statistics network (interface document)
  21. Analysis of MVC
  22. [middle stage] please stay and join me in the backstage
  23. Understanding front end garbage collection
  24. [continuous update] front end special style implementation
  25. Flutter product analysis and package reduction scheme
  26. XPath positioning
  27. 前端开发css中的flex布局的使用
  28. The use of flex layout in front end development CSS
  29. JQuery核心函数和静态方法
  30. JQuery core functions and static methods
  31. Node family - understanding of blocking and non blocking
  32. 热点微前端Microfrontend的讨论:谷歌AdWords是真实的微前端
  33. Vue source code analysis (2) initproxy initialization proxy
  34. What's TM called react diff
  35. Summary of common front end data structure
  36. Useeffect in hooks
  37. [encapsulation 02 design pattern] Command pattern, share meta pattern, combination pattern, proxy pattern, strategy pattern
  38. Front end notes: virtual Dom and diff of vue2. X
  39. The best code scanning plug-in of flutter
  40. The simplest plug-in for rights management of flutter
  41. 21. Object oriented foundation "problems and solutions of object traversal"
  42. Discussion on hot micro front end: Google AdWords is a real micro front end
  43. Usecallback and usememo for real performance optimization
  44. 【前端圭臬】十一:从规范看 JavaScript 执行上下文(下)
  45. [front end standard] 11: Javascript execution context from the perspective of specification (2)
  46. Hexagonal六角形架构ReactJS的实现方式 - Janos Pasztor
  47. Transaction of spring's reactive / imperative relational database
  48. The implementation of hexagonal hexagonal reactjs Janos pasztor
  49. HTTP状态码:402 Payment Required需要付款 - mozilla
  50. HTTP status code: 402 payment required - Mozilla
  51. Factory mode, constructor mode and prototype mode
  52. Build the scaffold of react project from scratch (Series 1: encapsulating a request method with cache function based on Axios)
  53. Cocos Quick Start Guide
  54. Comparison of three default configurations of webpack5 modes
  55. A case study of the combination of flutter WebView and Vue
  56. CSS: BFC and IFC
  57. A common error report and solution in Vue combat
  58. JS: this point
  59. JS: prototype chain
  60. JavaScript series -- promise, generator, async and await