This is the 8th day of my participation in the August More Text Challenge. For details, see:August is more challenging

It’s not a textbook, it’s not a video, it’s a textbook, it’s a textbook, it’s a textbook, it’s a textbook, it’s a textbook, it’s a textbook, it’s a textbook, it’s a textbook, it’s a textbook, it’s a textbook, it’s a textbook, it’s a textbook, it’s a textbook, it’s a textbook, it’s a textbook, it’s a textbook. Just for reference anyway

1. Front-end JS builds a linked list structure

1.1 Unidirectional linked list structure

Here I’ll copy and paste the standard from the book: linear table chain storage, refers to the storage of data elements in a linear table through arbitrary storage locations. In order to establish the linear relationship of data elements, each node of the linked list needs to store not only the information of the element itself, but also a pointer pointing to its successor.

The simplest way to express the front end is like this:

const a = {
	data:'A'
	next: {data:'B'.next: {data:'C'.next: {data:'D'.next:null}}}}Copy the code

Follow a.ext.nex.nex.next exactly, except for a few ways to exercise our algorithmic thinking skills. From above, we can clearly see that the list structure can only access elements from the table header (a in the above example)

1.2 Extend an object to a linked list structure

const linksListHead = {data:'A'.next:null}
const linkNodeArray = [{data:'B'.next:null}, {data:'C'.next:null}, {data:'D'.next:null}]
Copy the code

How to turn linksListHead using linkNodeArray data into a linked list?

The first interpolation

const linksListHead = {data:'A'.next:null}
const linkNodeArray = [{data:'B'.next:null}, {data:'C'.next:null}, {data:'D'.next:null}]
function generateLinkedList(linkhd,dataArray){
	let L = linkhd
	dataArray.forEach( item= >{
		L.next = item;
		L = item
	})
	return linkhd
}
const linkedListA = generateLinkedList(linksListHead,linkNodeArray)
console.log( linkedListA )
Copy the code

Tail interpolation is to insert the tail node of a linked list structure, or based on the above data. The code of tail interpolation is as follows:

const linksListFoot = {data:'D'.next:null}
const linkNodeArray = [{data:'C'.next:null}, {data:'B'.next:null}, {data:'A'.next:null}]
function generateLinkedList(linkft,dataArray){
	let L = linkft
	dataArray.forEach( item= >{
		item.next = L
		L = item
	})
	return L
}
const linkedListA = generateLinkedList(linksListFoot,linkNodeArray)
console.log( linkedListA )
Copy the code

1.3 Deleting a Node

According to the index number to delete the list data here on the basis of the previous generated list data, we will carry out the deletion operation of the list.

To delete a node from a list, it is important to find the precursors of the node to be deleted (precursors. To do this we have the following code:

function deletLinkNodeByIndex(linkedList,index){
	let i = 0;
	let linkNode = linkedList;
	if(index-1 < -1) {console.error(cannot delete header elements)}while(i<index-1){
		linkNode = linkNode.next;
		i++
	}
	// Predrive node
	const preNode = linkNode;
	// The node to be deleted is the successor of the predecessor
	let deletNode = preNode.next;
	// The deleted node is replaced by its successor
	const deletNodeNext = deletNode.next;
	preNode.next = deletNodeNext;
	deletNode = null // Release the node
}
deletLinkNodeByIndex(linkedListA,2)
console.log(linkedListA)
Copy the code

In fact, the idea of deleting by value is similar to the above, that is, to delete by value to traverse the whole list, find the node of the value to be deleted, and then to find its predecessor, and then to find its successor

Table 1.4 o long

The basic idea is to start the next loop at the beginning of the node. When the value of.next is null, the loop ends.

2.1 Other Extensions

  1. Circular lists, according to what I said above, actually in the front-end JS domain, your head next point to the tail node object is good
  2. Two-way linked list, add a pre, just anaphora

The quiz has a leading bidirectional circular list L, with nodes of the structure {prev,data,next}, where prev and next are Pointers to their immediate predecessors and immediate successors, respectively. Now to delete the node pointed to by the pointer p, how do I delete it?