Just a few words
In front-end development, linear structures that are often encountered include arrays, strings, and sets and maps in ES6. The most common one, I think, is counting groups. The linked list is also a linear collection of data elements. Unlike arrays and strings, the linear order of the elements in a linked list is not determined by their physical location in memory, but by the sequence of nodes pointing to each other. The purpose of this design is to solve the problem that arrays and other data structures need to know the size of the data in advance. The students who develop JS may not understand, because the array in JS is to support dynamic expansion.
Linked lists are fast to insert, reaching O(1) complexity, but their access time is linear, and faster access, such as random access, is not feasible. Arrays have a better cache location than linked lists. Today we will talk about the linked list and its implementation in JS.
Today’s hero — linked lists
A linked list is a chained access data structure that uses a set of storage cells with arbitrary addresses to store data elements in a linear list. The basic data in the linked list is represented by nodes, each node is composed of elements + Pointers, elements are storage units of data, Pointers are the address data connected to each node. Source of baidu
Linked list is divided into single linked list, double linked list and circular linked list, etc., one of the simplest to the number of single linked list
Singly linked lists
The nodes of a singly linked list have only two domains, one is the information domain and the other is the pointer domain. The information field holds the data information of the current node, the pointer field holds the address pointing to the next node, and the pointer field of the last node points to NULL. At this point, the origin of the name linked list is clear. As each node holds data, it points to the next node, and then the next node points to its next node as it continues to hold data, so the nodes are linked together, forming a chain.
Single linked list in JS implementation
A single linked list starts with head pointing all the way to NULL. In the chain node, data stores data, next stores the address data of the next node. So a single node is pretty easy to implement
class Node{
constructor(element){
/ / information domain
this.element = element;
/ / pointer field
this.next = null;
}
}
Copy the codeAt the same time, the linked list data should be added, deleted, changed and checked.
class SignleLinkLit{
constructor() {
// The initial header node
this.head = null
// Initial length
this.length = 0;
}
// Get the list
getList() {
return this.head;
}
// List length
size() {
return this.length;
}
// Whether the linked list is empty
isEmpty() {
return this.length === 0;
}
/ / append
append(element) {}
/ / search
search(list, element) {}
/ / insert
insert(position, element) {}
/ / remove
remove(element) {}
}
Copy the codeInstead of mentioning getList, Size, and isEmpty, let’s focus on the other four methods for manipulating linked list data.
Additional nodes
Due to the nature of linked lists, the append node simply traverses the tail node and points its pointer field to the node to be appended
// Append the node
append(element){
// Define the current node
const node = new Node(element);
// The variable used to help find the end of the chain
let temp = this.head;
if(!this.head){ // If the current head is empty, place element directly
this.head = node;
}else{
// INFO: When next of the node is null, we can confirm that the tail is found
while(temp.next){ // Loop to find the end of the chain
temp = temp.next;
}
temp.next = node;
}
this.length++;
}
Copy the codeSearch for nodes
Traverse the single strand from beginning to end to determine if the node is equal to the value searched, or true if it is equal, or false if it does not want to wait.
search(element){
if(!this.head) return false;
let temp = this.head;
while(temp){
if(temp.element === element) return true;
temp = temp.next
}
return false;
}
Copy the codeInsert the node
When position is 0, next points to head and assigns the node to this.head. Position is not 0, traverses to the node before position is inserted.
insert(position, element){
if(position < 0 || position > this.length) return null;
const node = new Node(element);
if(position === 0) {
node.next = this.head;
this.head = node;
}else{
let temp = this.head,
index = 0;
while(index < position){
temp = temp.next;
index++;
}
// Insert the next of the node to be inserted to the next of the current node
node.next = temp.next;
// Then point next of the current node to the node to be inserted
temp.next = node;
}
// The length is increased by one
this.length++;
}
Copy the codeRemove nodes
It also iterates through the single linked list, finds the nodes to be deleted, and deletes them. Note that if the node to be deleted is a head, you need to “redirect” the head separately.
remove(element){
if(!this.head) return;
if(this.head.element === element){
this.head = this.head.next;
this.length--;
return;
}
let curr = this.head,
prev = this.head;
while(curr){
if(curr.element ! == element){
prev = curr;
curr = curr.next;
}else{
prev.next = curr.next;
this.length--;
break;
}
}
}
Copy the codeDouble linked list
Whereas the previous single-linked list had only one direction from head to tail, this double-linked list has two directions from tail to end
So the single node element in the double list is different from the single node element in the list above:
class Node {
constructor(element) {
this.element = element;
// Precursors
this.prev = null;
// Next pointer
this.next = null;
}
}
Copy the codeDouble linked lists look like this:
class DoublyLinkedList{
constructor() {
// Initial header node
this.head = null;
// Initial tail node
this.tail = null;
// The length of the list
this.length = 0;
}
/ / operation
size(){
return this.length;
}
// Get the list
getList(isInverted = false) {
return isInverted ? this.tail : this.head;
}
// Clear the linked list
clear(){
this.head = this.tail = null;
this.length = 0;
}
// Whether the linked list is empty
isEmpty(){
return this.length === 0;
}
// Insert the node
insert(position, element);
// Delete the linked list node
removeAt(position){}
// Find the list node
search(element){}
}
Copy the codeInsert the node
I need to draw a little picture here to help you understand it. First initialize a node to be inserted, traverse to the previous position node of position in the linked list, insert the node to be inserted at this position, and process the front and back Pointers of the three surrounding nodes.
insert(position, element){
if(position < 0 || position > this.length) return null;
const node = new Node(element);
if(!this.head){
this.head = this.tail = node;
}else if(position === 0) {// Insert node is 0, need to adjust the head pointing
node.next = this.head;
this.head.prev = node;
// head points to the new head node
this.head = node;
}else if(position === this.length){ / / is the tail
this.tail.next = node;
node.prev = this.tail;
// tail Redirects
this.tail = node;
}else {
let temp = this.head,
index = 0;
while(index < position){
temp = temp.next;
index++;
}
temp.prev.next = node;
node.prev = temp.prev;
temp.prev = node;
node.next = temp;
}
this.length++;
}
Copy the codeRemove nodes
This is similar to a single linked list, where the list is first iterated, and the prev and next of the surrounding nodes are redirected after finding the nodes to be deleted.
removeAt(position){
if(!this.length || position < 0 || position > this.length - 1) return null;
let temp = this.head, index = 0;
if(this.length === 1) {// If there is only one node
this.clear();
}else if(position === 0) {
this.head.next.prev = null;
this.head = this.head.next;
}else if(position === this.length - 1) {
this.tail.prev.next = null;
this.tail = this.tail.prev;
}else{
while(index < position){
temp = temp.next;
index ++;
}
temp.prev.next = temp.next;
temp.next.prev = temp.prev;
}
this.length--;
return temp.element;
}
Copy the codeSearch node
Similar to a singly linked list, traversing the list from beginning to end returns true if an element is found, false otherwise.
search(element){
let temp = this.head;
while(temp){
if(temp.element === element) return true;
temp = temp.next;
}
return false;
}
Copy the codeDo the item
Leetcode21. Merge two ordered lists
Merges two ascending lists into a new ascending list and returns. A new list is formed by concatenating all the nodes of a given two lists.
Example:
Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4
// Definition for singly-linked list.
/ / the node
class ListNode {
constructor(val){
this.val = val;
this.next = null;
}
}
Copy the codeThe way I started
var mergeTwoLists = function(l1, l2) {
let res = new List();
while(l1 ! = =null&& l2 ! = =null) {
if (l1.element < l2.element) {
res.append(l1.element);
l1 = l1.next;
} else {
res.append(l2.element);
l2 = l2.next;
}
}
lettemp = ! l1 ? l2 : l1;
while (temp) {
res.append(temp.element);
temp = temp.next;
}
return res;
};
Copy the codeThere are more elegant ways to use recursion
var mergeTwoLists = function(l1, l2) {
if (l1 === null) {
return l2;
}
if (l2 === null) {
return l1;
}
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l2.next, l1);
return l2;
}
}
Copy the codePay attention to my public account
This article is formatted using MDNICE