Linked list in JavaScript ES6
JavaScript(ES6) data structure and algorithm -- linked listLike arrays, linked lists can be used to store a series of elements, but the implementation mechanism of lists and arrays is completely different. Show Before learning the linked list, let's first understand the shortcomings (disadvantages) of the array:
Advantages over array linked list:
What is a linked listThe structure of the linked list has been briefly mentioned above. Let's clearly understand what the linked list structure is in the way of diagram. As shown in the above figure, in the linked list, each element contains two attributes, that is, the value item of the element and the next element. Next points to the next node. At the same time, a pointer head in the linked list points to the first element of the linked list, and the last element points to null. Common operations in linked list
Encapsulated one-way linked list structureclass Node { constructor(element) { // Save element this.element = element; // Point to the next element this.next = null; } } class LinkedList { constructor() { this.head = null; this.length = 0; } // -Add a new item to the end of the linked list. append(element) append(element) { // Create a Node object based on element const newNode = new Node(element); // Add to the end, judge whether the head of the linked list structure is empty (if it is empty, it means there are no nodes in the linked list), and assign the newly created node to the head, which indicates that there are existing nodes in the linked list if (!this.head) { this.head = newNode; } // If the head is not empty (indicating that there are already nodes in the linked list), first define a variable to assign the head node to current (that is, point to the first node), //Use the while loop to judge whether the next node exists in turn. If it does not exist, assign the newly created node to the next attribute of the last node else { let current = this.head; while (current.next) { current = current.next; } current.next = newNode; } this.length++; } // -Inserts a new item into a specific location in the linked list. insert(position,element) position indicates the position where the element is inserted insert(position, element) { // Judge whether the input value is out of range if (position < 0 || position > this.length) return false; // Create a new node const newNode = new Node(element); // Insert element // Determine whether the position of the inserted element is in the head node if (position === 0) { // The inserted node assigns the node pointing to the head node to the next attribute of the inserted node at the first newNode.next = this.head; //Then assign the newly inserted node to the head node this.head = newNode; } // To insert a node in another location, you need to point the previous node of the new node in the insertion location to the new node, and then point the next attribute of the new node to the next node else { let index = 0; let current = this.head; // Insert the previous position of the node let previous = null; while (index++ < position) { previous = current; current = current.next; } previous.next = newNode; newNode.next = current; } this.length++; // Indicates successful insertion return true; } // -Get the element of the corresponding position. get(position) get(position) { if (position < 0 || position > this.length - 1) return null; // When finding the elements at the specified location, you need to look back one by one until the specified location is found, and assign the node next attribute of this location to the variable current let index = 0; let current = this.head; while (index++ < position) { current = current.next; } return current.element; } // -Returns the index of the element in the linked list. If there is no such element in the linked list, - 1 is returned. indexOf(element) indexOf(element) { let current = this.head; let index = 0; while (current) { if (current.element === element) { return index; } index++; current = current.next; } return -1; } // -Modify an element at a location. update(position ,element) update(position, element) { let result = this.removeAt(position); this.insert(position, element); return result; } // -Removes an item from a specific location in the list. removeAt(position) removeAt(position) { if (position < 0 || position > this.length - 1) return null; let current = this.head; let previous = null; let index = 0; if (position === 0) { this.head = current.next; } else { while (index++ < position) { previous = current; current = current.next; } previous.next = current.next; } this.length--; return current.element; } // -Remove an item from the linked list. remove(element) remove(element) { const index = this.indexOf(element); if (index === -1) return; this.removeAt(index); } // -If the linked list does not contain any elements, it returns true. If the length of the linked list is greater than 0, it returns false. isEmpty() isEmpty() { return this.length === 0; } // -Returns the number of elements contained in the linked list. Similar to the array length property. size() size() { return this.length; } } module.exports = new LinkedList(); test const linkedList = require("./linkdeList"); // Test adding nodes to linked list linkedList.append("a"); linkedList.append("b"); linkedList.append("c"); linkedList.append("d"); linkedList.append("e"); console.log(linkedList); // Test inserting a node into the specified location const res = linkedList.insert("1", "f"); console.log(linkedList, res); // Test gets the element at the specified location console.log(linkedList.get(1)); // Test gets subscript value {} through element console.log(linkedList.indexOf("b")); // Test removes an item from a specific location in the list console.log(linkedList.removeAt(4)); console.log(linkedList); // The test modifies an element at a location console.log(linkedList.update(1, "www")); console.log(linkedList); // Test removes an item from the linked list console.log(linkedList.remove("a")); console.log(linkedList); Recognize two-way lists
A one-way linked list can only traverse from beginning to end or from end to end, that is, the connection process of the linked list is one-way. The principle of implementation is that there is a reference to the next node in the previous node. One way linked list has an obvious disadvantage. We can easily get the next node, but it is difficult to return to the previous node (we need to traverse from the beginning). However, in actual development, we often encounter the situation of returning to the previous node. Therefore, the two-way linked list can solve the situation that the one-way linked list is difficult to get the previous node.
The bidirectional linked list is implemented based on the unidirectional linked list. In fact, it is to add a reference (prev) pointing to the previous node in each node. The prev of the first node points to null and the next of the last node points to null (as shown in the figure below). In this way, the bidirectional linked list can effectively solve the problems raised above. However, the two-way linked list also has some disadvantages. Each time a node is inserted or deleted, it needs to deal with four references instead of two, which is also troublesome to implement. And it is equivalent to a one-way linked list, which must occupy more memory space. Encapsulated bidirectional linked listAccording to the requirements of the two-way linked list, we only need to inherit the one-way linked list to rewrite the three methods of adding, inserting and deleting according to the subscript const { LinkedList, Node } = require("./linkdeList"); class DoublyNode extends Node { constructor(element) { super(element); this.prev = null; } } class DoublyLinkedList extends LinkedList { constructor() { super(); this.tail = null; } // -Add a new item to the end of the linked list. append(element) append(element) { const newNode = new DoublyNode(element); if (this.head === null) { this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; newNode.prev = this.tail; this.tail = newNode; } this.length++; } // -Inserts a new item into a specific location in the linked list. insert(position,element) insert(position, element) { if (position < 0 || position > this.length) return false; const newNode = new DoublyNode(element); if (position === 0) { if (this.head == null) { this.head = newNode; this.tail = newNode; } else { newNode.next = this.head; this.head.prev = newNode; this.head = newNode; } } else if (position === this.length) { this.tail.next = newNode; newNode.prev = this.tail; this.tail = newNode; } else { let index = 0; let current = this.head; let previous = null; while (index++ < position) { previous = current; current = current.next; } previous.next = newNode; newNode.prev = previous; newNode.next = current; current.prev = newNode; } } // -Get the element of the corresponding position. get(position) // -Returns the index of the element in the linked list. If there is no such element in the linked list, - 1 is returned. indexOf(element) // -Modify an element at a location. update(position ,element) // -Removes an item from a specific location in the list. removeAt(position) removeAt(position) { if (position < 0 || position > this.length - 1) return null; let current = this.head; if (position === 0) { if (this.length === 1) { this.head = null; this.tail = null; } else { this.head = this.head.next; this.head.prev = null; } } else if (position === this.length - 1) { current = this.tail; this.tail.prev.next = null; this.tail = this.tail.prev; } else { let index = 0; let previous = null; while (index++ < position) { previous = current; current = current.next; } previous.next = current.next; current.next.prev = previous; } return current.element; } // -Remove an item from the linked list. remove(element) // -If the linked list does not contain any elements, it returns true. If the length of the linked list is greater than 0, it returns false. isEmpty() // -Returns the number of elements contained in the linked list. Similar to the array length property. size() } module.exports = DoublyLinkedList; test const DoublyLinkedList = require("./doubly_linkedList"); const doublyLinkedList = new DoublyLinkedList(); doublyLinkedList.append("a"); doublyLinkedList.append("b"); doublyLinkedList.append("c"); doublyLinkedList.append("d"); doublyLinkedList.append("e"); doublyLinkedList.append("f"); console.log(doublyLinkedList); doublyLinkedList.insert(1, "g"); console.log(doublyLinkedList); console.log(doublyLinkedList.get(1)); console.log(doublyLinkedList.indexOf("g")); console.log(doublyLinkedList.removeAt(1)); console.log(doublyLinkedList.update(0, "nnn")); console.log(doublyLinkedList.remove("f")); Posted by unix.root at Aug 24, 2021 - 4:40 AM Tag: ECMAScript Algorithm Javascript data structure linked list |