Preface: why to study data structure, what can it help us? What can solve the problem, home data structure is not a specific programming language, it teaches us is a way of thinking, that is, how to store data in a better way and solve some problems, through learning data structure, can greatly broaden our thinking mode. Mastering data structure and algorithm will make us look at problems in different depth and solve problems from different perspectives. It is also a qualitative leap for the improvement of personal logical thinking.

The following are the following points to understand the principle and scenario of their implementation:

  • What is a stack
  • What is a queue
  • What is a linked list
  • What is a set
  • What is a dictionary
  • What binary tree

What is a linked list

This is probably the most common data structure to store multiple elements, arrays, or lists, but it has a drawback: arrays are all fixed in size, making it expensive to move and insert elements. A linked list store is an ordered collection of elements. Unlike an array, the elements of a linked list are not contiguous in memory. Each element is a reference from one element’s own node to the next element. As shown in the figure below:

How do I implement a linked list

  • Create a LinkedList class skeleton
  • Create a Node class that connects the linked list data structure
  • Enrich the data method of linked list
Create a LinkedList class

Initial three values:

  • The count:Represents the number of elements in the linked list
  • The head:Represents a data structure for a linked list
  • EqualsFn:Use an inner function that represents whether the elements in the list are equal or not
const defaultEquals = (a, b) => a === b

class LinkedList {
    constructor(equalsFn = defaultEquals){
        this.count = 0;  // 
        this.head = undefined
        this.equalsFn = equalsFn
    }
}
Create a Node class

Initial two values:

  • Element:Represents the value of the added list element
  • Next:Represents a pointer to the next linked list
class Node  {
    constructor(element){
        this.element = element
        this.next = undefined
    }
}
Ways to enrich linked lists
  • Push (element) :Adds a new element to the end of the list.
  • Insert (element, the position) :Inserts a new element at a specific location in the linked list.
  • GetElementAt (index) :Returns an element at a specific position in the linked list. If no such element exists in the list, undefined is returned
  • Remove (element) :Removes an element from a linked list.
  • IndexOf (element) :Returns the index of an element in a linked list. Returns -1 if the element is not in the list
  • RemoveAt (position) :Removes an element from a specific location in the linked list.
  • IsEmpty () :Returns true if the list contains no elements, or false if the list length is greater than 0.
  • The size () :Returns the number of elements in the linked list, similar to the length attribute of an array.
class LinkedList { constructor(equalsFn = defaultEquals){ this.count = 0; this.head = undefined this.equalsFn = equalsFn } push(element) { const node = new Node(element) let current; If (this.head == null) {this.head = node}else {// record the current reference = this.head; while (current.next ! = null) { current = current.next; } this.count ++} getElementAt(index){if(index >){this.count ++} return this.count ++} return this.count ++} return this.count ++  0 && index <= this.count ) { let node = this.head; let j = 0; while(j < index && node ! = null) {// assign node = node.next j++} return node; If (index >= 0 && index < this.count) {return 'undefined' If (index === 0) {this.head = current.next; }else { const previous = this.getElementAt(index - 1) current = previous.next; // Create a link to the next item in current and move it. Next = Current. Next} // Remove this. Count -- return Current.element} return undefined} // insert(element, element, element) index ){ if(index >=0 && index <= this.count) { const node = new Node(element); If (index === 0) {// Add const current = this.head; node.next = current this.head = node; }else {// Find const Previous = this.getElementAt(index-1); // The next reference in the linked list is const current = previous. Next; // Add a new linked list node to connect. Next = current; // Update entire list previous. Next = node; This. count ++ return true} return false} // return indexOf(element) {let current = this.head; this.count ++ return true} return false} for (let i = 0; i< this.count && current ! = null; I ++) {if(this.equalsfn (element, current.element)) {return I} // Current = current.next} return -1} const index = this.indexof (element) return This.removeAt (index)} // Get the number of lists (size() {return this.count} // Empty(){return this.size() === 0} // GetHead () {return this.head}}
test
const nodes = new LinkedList() nodes.push(10) nodes.push(20) nodes.push(30) nodes.push(40) nodes.push(50) nodes.push(60)  console.log(nodes.getHead())

The results are shown below:

Removes the specified linked list location:

const nodes = new LinkedList() nodes.push(10) nodes.push(20) nodes.push(30) nodes.push(40) nodes.push(50) nodes.push(60) // Removes the list nodes.removeAt(4) console.log(nodes.gethead ())

The results are shown below:

So what problem can linked lists solve?

Referring to the original topic of the buckle example, try to use the thinking of the linked list to solve

Remove duplicate elements from a sorted linked list

Answer key:

const nodes = new LinkedList() nodes.push(10) nodes.push(10) nodes.push(20) nodes.push(40) nodes.push(40) nodes.push(60) Var deleteDuplicates = function({head}) {// keep the reference relationship let cur = head; If (cur.element === cur.next. Element) {if(cur.element == cur.next. Element) {if(cur.element == cur.next. cur = cur.next } } return head }; let result = deleteDuplicates(nodes) console.log(result)

The above is a simple review of the basic implementation of the linked list and the scene application, in the actual demand scene there are very linked list structure types, such as: two-way linked list, circular linked list, ordered linked list and so on. Only a deep understanding of its internal implementation and methods in order to deal with complex projects in the exhibition.

The last

This article series refers to “learning JavaScript data structures and algorithms 3rd edition” to collate and conclude, I hope to help you.