The basic concept of linked lists
In most languages, arrays are fixed in size, and the cost of inserting or removing items from the beginning or middle of an array is high because elements need to be moved. (such as the stack and queue we implemented earlier)
A linked list is an ordered collection of elements, but unlike an array, the elements in a linked list are not placed consecutively in memory. Each element consists of a node that stores the element itself and a reference (also known as a pointer or link) to the next element.
One advantage of linked lists over traditional arrays is that you don’t need to move other elements when you add or remove them. However, linked lists require the use of Pointers, so implementation of linked lists requires extra care. In an array, we can directly access any element anywhere, but to access an element in the middle of the list, we iterate through the list from the starting point (the header) until we find the desired element.
The basic method of linked lists
Push (Element) : Adds a new element to the end of the list. The diagram below:
Insert (Element, position) : Inserts a new element into a specific position in the list.
Insert the following header:
Insert elsewhere as follows:
GetElementAt (index) : Returns an element at a specific location in the list. If no such element exists in the list, undefined is returned.
Remove (element) : Removes an element from a linked list. The diagram below:
IndexOf (element) : returns the indexOf an element in the linked list. Returns -1 if the element is not in the list.
RemoveAt (position) : Removes an element from a specific position in the list.
IsEmpty () : Returns true if the list contains no elements, false if the list length is greater than zero.
Size () : Returns the number of elements in the list, similar to the length property of an array.
ToString () : Returns a string representing the entire list. Since the list item uses the Node class, you need to override the toString method inherited from the default JavaScript object to print only the value of the element.
Self-actualization of linked list structures
// one-way linked list
class Node{
// The structure of each node
constructor(value) {
this.value = value / / data domain
this.next = undefined / / pointer field}}class LinkedList{
constructor() {
this.count = 0 / / counter
this.head = undefined // Head, start node
}
push(value){ // Add a value to the tail
let node = new Node(value) // Instance generates node objects
let current // The node is currently traversed
if(!this.head){
this.head = node
// If the current list is empty, head is empty, so set the new node to the first list
}else{ // If the first list is not empty, then we count backwards
current = this.head // The list header is the node that has already been traversed.
while(current.next){ // If the pointer field of the current node is not empty, it is not the last node, then the loop condition is true, and the loop can continue. If the condition is false, the loop will not enter
current = current.next // As long as it is not the last node, the current traversal node points to the next node
}
current.next = node // If the loop is out of the loop at the end of the loop, the current pointer field points to the last node traversed
}
this.count++ // Every time a new value is added to the tail, the counter is incremented by one
return linkData
}
(i-1) => (I +1); (I +1) => (I +1); (I +1)
removeAt(index){ // Delete the node with the specified subscript from the linked list
if(index >= 0 && index < this.count){ If you want to delete a specified data item, the subscript must be greater than or equal to 0 and the list length must be smaller than or equal to 0
let current = this.head // The default is to use the header as the current node position
let beRemoved // Deleted
if(index = 0) {// delete the header if it is 0
beRemoved = current // Current is this.head
this.head = current.next // The header points to the next data, and the original data is deleted
}else{ // The next step in the for loop is very difficult to understand. Try drawing a diagram and plugging in the values 0, 1, 2, 3, 4
for(let i = 1; i < index; i++){ // Why start at 1, because we just excluded the 0th bit
current = current.next // At the end of the loop, the index is the index of the node to be deleted. Since I
}
beRemoved = current.next // From the above for loop, current is the previous node of the node to be deleted, so current-. next is the node to be deleted
current.next = current.next.next // The pointer field of the previous node of the current node points to the next node of the current node, and the current node is deleted
}
this.count-- // After deletion, the corresponding counter decreases by 1
return beRemoved // Returns the value of the deleted node}}removeValue(value){ // Remove the node with the specified value from the linked list
let current = this.head
let pre = null // The previous node of the deleted node
// When the header of the list is the value to be deleted, or when other nodes in the list are the values to be deleted
if(current.value === value){ // If the input value is equal to the value of the header
this.head = current.next // Just point the header to the next node of the original header
}else{ / / otherwise
for(let i = 1; i < this.count; i++){ // Loop through each node, looking for the value of the next node if the current node is not deleted
pre = current // Save i-1 to variable pre (current is this.head, current node becomes previous node)
current = current.next // The node I that needs to be removed (the next node of the current node becomes the current node)
if(current.value === value){ // When the value to be deleted is the same as the value of the current node
pre.next = current.next // The pointer field of the previous node (i-1) points to the node (I) that needs to be removed.
break // break deletes the first value that meets the condition. If break is not written, the loop continues, and all values that meet the condition are deleted}}}this.count-- // The counter decreases by 1
return 'has deleted the first value that matches the condition${value}`
}
pop(){ // Delete the last one
return this.removeAt(this.count - 1)}indexOf(value){ // Query the position of a value in the list, return the position index of the value
let current = this.head
if(value === current.value){ // The three equal signs must be identical and the data type must be the same
return 0
}
// If it is not bit 0, then the following loop is entered
for(let i = 1; i < this.count; i++){
current = current.next // It is not the 0th bit, so it keeps going back
if(value === current.value){
return i
}
}
return undefined // Return undefined if (' if '); // Return undefined if (' for ')
}
getNodeAt(index){ // Gets the value at the specified subscript position
if(index >=0 && index < this.count){
let current = this.head
if(index === 0) {return current
}else{
for(let i = 1; i < index; i++){
current = current.next // When the loop ends, I is the index of the node that preceded the specified node
}
return current.next
}
}
}
// If we want to insert a new node at the ith subscript, then i-1 points to the new node, and the new node points to I, and the new node is inserted
insert(value,index){ // Insert a new node at the specified subscript position
let node = new Node(value) // instantiate a node
if(index >= 0 && index <= this.count){ // The index value entered is within the length of the list
let current = this.head // Save the initial value
if(index === 0) {// Insert the beginning
this.head = node
this.head.next = current // The pointer field of the new starting value points to the old starting value
}else{
for(let i = 1; i < index; i++){
current = current.next // When the loop ends, the current variable to the left of the equals sign of the previous node where the new node is inserted is i-1
}
let nextEle = current.next // nextEle saves the original I
current.next = node // the pointer field of i-1 points to the newly inserted node
node.next = nextEle // The pointer field of the newly inserted node points to the original I
this.count++
}
}else{ // The entered index value exceeds the original length of the linked list
throw new Error("Index value error")}}unshift(value){ // Insert a new node at the head of the list
this.insert(value, 0)}isEmpty(){
return !this.count
}
size(){
return this.count
}
getHead(){ // Get the value of the current list header
return this.head.value
}
toString(){ // Convert to string output
let objString = ""
let current = this.head
if(! current){// If the list header does not exist
return "" / / return empty
}else{
do{ // Execute the do loop at least once before checking if the condition of the while satisfies the loop
objString = `${objString}.${current.value}`
current = current.next
}while(current) // Loop through do as long as the current value exists
return objString.slice(1) // Remove the comma after the first concatenation}}}let linkData = new LinkedList()
linkData.push(0)
linkData.push(1)
linkData.push(2)
linkData.push(3)
linkData.push(4)
Copy the codeBasic concepts of bidirectional linked lists
The difference between a bidirectional list and a regular list is that in a list, a node has only the link to the next node in the chain; In a bidirectional linked list, the links are bidirectional: one chain is one element down, and the other is one element ahead, as shown below:
// Two-way linked list
class DBNode{
// The structure of each node
constructor(value) {
this.value = value / / data domain
this.next = undefined // Next pointer field
this.pre = undefined // Last pointer field}}class LinkedList{
constructor() {
this.count = 0 / / counter
this.head = undefined // Head, start node
}
push(value){ // Add a value to the tail
let node = new DBNode(value) // Instance generates node objects
let pre = this.head
let current // The node currently traversed
if(!this.head){
this.head = node
// If the current list is empty, head is also empty, so set the new list to the first one
}else{ If the first link in the list is not empty, then we count backwards
current = this.head // The list head is the node that has been traversed
while(current.next){ // If the pointer field of the current node is not empty, it is not the last node
current = current.next // As long as it is not the last node, the current traversal of the node pointer field, to the next node
pre = current // Then the current node becomes the previous node pre, and only then can the current loop become the next node
}
current.next = node // If the loop breaks out of the loop after traversing the last node, the current last node's pointer field points to the newly added node
node.pre = pre // Add a new node. The first pointer field of node points to the previous node.
}
this.count++ // When a new value is added to the tail, the counter is incremented by one
}
removeAt(index){ // Delete the number of rows in the list
if(index >= 0 && index < this.count){ If you want to delete a specified data item, the subscript must be greater than or equal to 0 and the list length must be smaller than or equal to 0
let current = this.head
let beRemoved // Deleted
if(index = 0) {// delete the header if it is 0
beRemoved = current
this.head = current.next // The header points to the next data, and the original data is deleted
this.head.pre = undefined
// When the original header is deleted, the original 1 bit becomes the new header, but the original 1 bit pre is a value pointing to the deleted node, so we need to empty the original pointer undefined
}else{ // This step in the for loop can be understood by trying to draw a diagram and plugging in specific values 0, 1, 2, 3, 4
for(let i = 1; i < index; i++){ // Why start at 1, because we just excluded the 0th bit
current = current.next // When the loop ends, the node preceding the node to be deleted, i-1
}
beRemoved = current.next // Node I to be deleted
current.next.next.pre = current
Next indicates the node to be deleted, so current is the previous node to be deleted.
// So the last pointer field of the next node of the deleted node points to the previous node of the deleted node
current.next = current.next.next // The pointer field of the previous node of the current node points to the next node of the current node, and the current node is deleted
}
this.count--
return beRemoved
}
}
removeValue(value){ // Delete the node with the specified value in the linked list
let current = this.head
let pre = null // The previous node of the deleted node
if(current.value === value){ // If the input value is equal to the value of the header
this.head = current.next
this.head.pre = undefined // Same as removeAt above
}else{
for(let i =1; i < this.count; i++){
pre = current // Save i-1 to the variable pre
current = current.next // Node I to be deleted
if(current.value === value){ // When the value to be deleted is the same as the value of the node
pre.next = current.next // The pointer field of the previous node (i-1) points to the node (I) that needs to be removed.
current.next.pre = pre
Pre (i-1); pre (i-1); pre (i-1)
break // Delete the first value that meets the condition. If break is not written, continue the loop and delete all values that meet the condition}}}this.count--
}
pop(){ // Delete the last one
return this.removeAt(this.count - 1)}indexOf(value){ // Query the position of a value in the list, return the position index of the value
let current = this.head
if(value === current.value){ // The three equal signs must be identical and the data type must be the same
return 0
}
// If it is not bit 0, then the following loop is entered
for(let i = 1; i < this.count; i++){
current = current.next // It is not the 0th bit, so it keeps going back
if(value === current.value){
return i
}
}
return undefined // Return undefined if (' if '); // Return undefined if (' for ')
}
getNodeAt(index){ // Get the value of the specified position
if(index >=0 && index < this.count){
let current = this.head
if(index === 0) {return current
}else{
for(let i =1; i < index; i++){
current = current.next // When the loop ends, the previous node of the culled node
}
return current.next
}
}
}
insert(value,index){ // Insert a new node at the specified location
let node = new DBNode(value)
if(index >= 0 && index <= this.count){ // The index value entered is within the length of the list
let current = this.head // Save the initial value
if(index === 0) {// Insert the beginning
this.head = node
this.head.next = current // The pointer field of the new starting value points to the old starting value
current.pre = this.head // The field that precedes the previous starting value points to the latest starting value
}else{
for(let i = 1; i < index; i++){
current = current.next // When the loop ends, the current variable to the left of the equals sign of the previous node where the new node is inserted is i-1
}
let nextEle = current.next // nextEle saves the original I
current.next = node // the pointer field of i-1 points to the newly inserted node
node.next = nextEle // The pointer field of the newly inserted node points to the original I
node.pre = current
// When inserting the first bit, I =1, 1 is not less than 1, so there is no for loop, so current is this.head, and the previous field of the newly inserted node points to this.head
nextEle.pre = node
// The previous pointer field of nextEle, pre, points to the newly inserted node
this.count++
}
}else{ // The index value entered exceeds the list length
throw new Error("Index value error")}}isEmpty(){
return !this.count
}
size(){
return this.count
}
getHead(){
return this.head.value
}
toString(){
let objString = ""
let current = this.head
if(! current){// If the list header does not exist
return "" / / return empty
}else{
do{ // Execute the do loop at least once before checking if the loop condition is satisfied while
objString = `${objString}.${current.value}`
current = current.next
}while(current) // Loop through do as long as the current value exists
return objString.slice(1)}}}let linkData = new LinkedList()
Copy the code