This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.
preface
In front of the two articles, interaction is not good, may be the level is limited, may be not everyone’s appetite, because no one interaction, I do not know what is the problem, I also no matter, I just continue to write, try to do some fine tuning, write more categories, strive for interaction ~~
I am also learning the attitude to write the article, to ensure the original, do not guarantee correct, will continue to update
Here are some examples of javascript- Algorithm, github’s open source library and MDN
concept
A linked list is made up of a series of nodes, each of which holds data and a single reference to the next node, called a single list, or two reference addresses (a reference to the node before it and a reference to the next node, called a bidirectional list).
So a linked list can be discontinuous in memory compared to an array
| The characteristics of | The list | An array of | note |
|---|---|---|---|
| In-memory continuity | no | is | Add and delete in linked list is faster than array, but search is slower than array, so frequently add and delete, rarely query, use linked list first |
| Store content | Data + reference address | Only the data | So linked lists take up more memory space than arrays, so arrays are preferred for storing large amounts of data |
Common operations on linked lists
In JS, the array is language native support, in the array prototype provides a rich method for us to operate the array is very convenient. Linked lists also have some common operations that need to be manually supported
Unidirectional linked list implementation
I’m just going to implement a one-way list, and I’ll implement a two-way list when I have time
// Comparator.ts
type CompareFnReturn = 0 | -1 | 1
const defaultCompareFn = (a: any, b: any) = > {
if (a === b) {
return 0
}
return a > b ? 1 : -1
}
/** ** compares */
class Comparator {
compare = defaultCompareFn
constructor(compareFn? : (a:any, b: any) => CompareFnReturn) {
if (typeof compareFn === 'function') {
this.compare = compareFn
}
}
/** ** /
equal(a: any, b: any) {
return this.compare(a, b) === 1
}
/** * a < b */
lessThan(a: any, b: any) {
return this.compare(a, b) < 0
}
/** * a > b */
greaterThan(a: any, b: any) {
return this.compare(a, b) > 0
}
/** ** is greater than or equal to, and is less than or equal to, so I don't write it, so I use less than and greater than and then I take the opposite, plus */ if necessary
}
export default Comparator
Copy the code// SingleLinkedList.ts
import Comparator from './Comparator'
const ISSINGLELINKEDLIST = Symbol('isSingleLinkedList')
export type SingleLinkedListNodeType = SingleLinkedListNode | null | undefined
interface ExtendsSingleLinkedList extends SingleLinkedList {
[key: string] :any
}
class SingleLinkedListNode {
data = 0
next: SingleLinkedListNodeType = null
constructor(data: any, next: SingleLinkedListNodeType = null) {
this.data = data
this.next = next
}
}
type CallbackFn = (
nodeData: any, index? :number, SingleLinkedList? : ExtendsSingleLinkedList) = > any
/** * Check if a list is singly linked *@param data
* @returns* /
const isSingleLinkedList = (data: any) = > {
return!!!!! data? .[ISSINGLELINKEDLIST] }class SingleLinkedList {
// >>>>>>>>>>> static method >>>>>>>>>>>
/** * static methods also add */
static isSingleLinkedList = isSingleLinkedList
/** * Generates a linked list * from a pseudo-array or iterable@param ArrayLike pseudo-array objects or iterables *@param MapFn callback function *@param ThisArg callback function this points to *@returns A new linked list */
static from(
arrayLike: any, mapFn? :any, thisArg? :any
): ExtendsSingleLinkedList {
const singleLinkedList = new SingleLinkedList(
Array.from(arrayLike, mapFn, thisArg)
)
return singleLinkedList
}
/** * returns a new list of arguments *@param Args parameter list *@returns Returns a new linked list */
static of(... args:any[]): ExtendsSingleLinkedList {
const newSingleLinkedList = new SingleLinkedList(args)
return newSingleLinkedList
}
// <<<<<<<<<<< static method <<<<<<<<<<<
constructor(arr? :any[]) {
if (Array.isArray(arr)) {
arr.forEach((a) = > {
this.push(a)
})
}
const obj: ExtendsSingleLinkedList = new Proxy(this, {
get(target: ExtendsSingleLinkedList, p: string) {
// This [0] is used to retrieve the list value directly
if (Number.isInteger(+p)) {
return target.getPositionValue(+p)
}
return target[p]
},
set(target: ExtendsSingleLinkedList, key: any, data: any) {
if (key in target) {
target[key] = data
return true
}
This [0] = data; this[0] = data
target.changePositionValue(+key, data)
return true}})return obj
}
/** * the tag is singly linked */
[ISSINGLELINKEDLIST] = true
/** * add a single list method to the prototype */
isSingleLinkedList = isSingleLinkedList
/** * the first node, the header node */
head: SingleLinkedListNodeType = null
/** * last node, tail node */
tail: SingleLinkedListNodeType = null
/** * Number of linked list nodes */
length: number = 0
/** * Check whether the list is empty */
isEmpty(): boolean {
return this.length === 0
}
/** * to JSON string */
toJSONString(indent = 2) {
return JSON.stringify(this.null, indent)
}
/** * list to array *@returns Return the array */
toArray(): any[] {
let node = this.head
const arr = []
while (node) {
arr.push(node.data)
node = node.next
}
return arr
}
/** * to a readable string */
toReadString() {
let node = this.head
const arr: any[] = []
while (node) {
arr.push(node.data)
node = node.next
}
return The length of the linked list is:The ${this.length}
${arr
.map(
(a) => ` = = >${a}
`
)
.join(' ')}
`
}
/** ** comparison function */
compare = new Comparator()
/** * Clear the list *@returns Returns true * /
clear() {
this.head = this.tail = null
this.length = 0
return true
}
/** * insert * in the header@param Data Indicates the data to be accessed@returns Length Specifies the new length of the linked list */
unshift(data: any) :number {
/** * creates a node that by default points to the current head node */
const node = new SingleLinkedListNode(data, this.head)
/** * there are two cases * 1. The list was empty * 2. The original list was not empty */
if (this.isEmpty()) {
/** * all points to the new node, and the number of nodes is increased by one */
this.head = node
this.tail = node
this.length++
} else {
/** * point the head to the new node */
this.head = node
this.length++
}
return this.length
}
/** * inserts * from the tail@param Data Indicates the data to be inserted@returns Length Specifies the new length of the linked list */
push(data: any) :number {
/** * insert from the tail, there are two cases * 1. The list is empty, in this case, equivalent to inserting from the head * 2. Linked lists are not empty */
if (this.isEmpty()) {
this.unshift(data)
} else {
// The list is not empty, a new node needs to be created
const node = new SingleLinkedListNode(data)
// Point the next node from the previous tail to it
this.tail! .next = node// The tail points to it
this.tail = node
// The length of the list increases by one
this.length++
}
return this.length
}
/** * Removes a node from the end of the list and returns the value of the node *@returns Returns the value of the deleted node */
pop(): any {
/** * there are three cases * 1. The list is empty * 2. The list has only one node * 3. The linked list has more than one node */
if (this.isEmpty()) {
// Case 1, the list is empty, return undefined, do nothing else
return void 0
} else if (this.length === 1) {
// Case 2, the list has only one node
// Save the value of the end node
const tailData = this.tail? .data// Clear the linked list
this.clear()
// return the value of the endnode
return tailData
} else {
// Case 3, more than one node
let node = this.head
while (node) {
if (node.next === this.tail) {
// Find a node on the end node
// Save the value of the end node
const tailData = this.tail? .data// Change the previous node of the tail to the tail
node.next = null
this.tail = node
// The length of the list is reduced by one
this.length--
return tailData
}
}
}
}
/** * Removes the total node from the head of the list and returns its value *@returns Returns the deleted value */
shift(): any {
/** * can be divided into two cases * 1. The linked list length is less than 2, i.e. the list is empty or 1 * 2. The length of the linked list is greater than or equal to 2 */
if (this.length < 2) {
return this.pop()
} else {
// Save the header value
const headData = this.head? .data// Change the header orientation
this.head = this.head! .next// The length of the list is reduced by one
this.length--
return headData
}
}
/** * Determines whether a position is a valid position in the list *@param The position location *@returns Is a valid location */
isValidPosition(position: number) :boolean {
if (!Number.isInteger(position)) {
return false
} else if (0 <= position && this.length >= position) {
return true
} else {
return false}}/** * returns the node * at position@param The position location *@returns Returns the node */ at this location
getPositionNode(position: number): SingleLinkedListNodeType {
// Not a valid position, return null
if (!this.isValidPosition(position)) {
return null
}
// The valid position is between 0 and this.length
let node = this.head
let index = position
while(index ! = =0 && node) {
index--
node = node.next
}
return node
}
/** * returns the value * at the position@param The position location *@returns Returns the value */ at this position
getPositionValue(position: number) {
return this.getPositionNode(position)? .data }/** * Change the value of the node *@param The node node *@param Value Changes the value of a node *@returns Check whether the modification is successful */
changeNodeValue(node: SingleLinkedListNodeType, value: any) :boolean {
if (node) {
node.data = value
return true
} else {
return false}}/** * change to position *@param The position location *@param Data Indicates the value *@returns Check whether the modification is successful */
changePositionValue(position: number, data: any) {
const node = this.getPositionNode(position)
return this.changeNodeValue(node, data)
}
/ * * * *@param Value Specifies the data to be inserted *@param Data Benchmark data *@param After after the base data, the default is, false is before the base data */
insertValue(value: any, data: any, before = true) {
console.log(value, data, before)
}
/** * find the next node of this benchmark data *@param Data Benchmark data *@returns Returns the found node */
findNodeValueAfter(data: any): SingleLinkedListNodeType {
let node = this.findNodeValueBefore(data)
while (node) {}
return node
}
/** * find the node * before the benchmark data@param Data Benchmark data *@returns Returns the found node */
findNodeValueBefore(data: any): SingleLinkedListNodeType {
let node = this.head
while (node) {
if (this.compare.equal(data, node.data)) {
return node
}
node = node.next
}
return node
}
/** * This method is used to merge two or more singly linked lists. It does not change existing singly linked lists but returns a new list *@param Args single linked list array *@returns Concatenated single linked list */concat(... args: ExtendsSingleLinkedList[]): ExtendsSingleLinkedList {console.log(args)
return this.concatLinkedList(this. args) }/** * Merge two or more lists *@param FirstSingleLinked Base list *@param Args residual linked list *@returns Returns the new linked list */ after the mergeconcatLinkedList( firstSingleLinked: ExtendsSingleLinkedList, ... args: ExtendsSingleLinkedList[] ): ExtendsSingleLinkedList {if (args.length < 1) {
return firstSingleLinked
}
// todo
if (args.length === 1) {
// const newSingleLinkedList = new SingleLinkedList()
return firstSingleLinked
}
const [first, ...rest] = args
return this.concatLinkedList(first, ... rest) }// todo
/** * Shallowly copy a part of the list to another location in the same list without changing the length of the original list *@param Target 0 is the base index, copied to that position, or if it is negative, target evaluates from the end. If target is greater than the size of the linked list, replication will not occur. If target is greater than *@param start
* @param end
* @returns* /
copyWidthIn(
target: number,
start = 0, end? :number
): ExtendsSingleLinkedList {
console.log(target, start, end)
return this
}
/** * Tests whether all elements in a linked list can pass a function that returns a Boolean value *@param Fn Test function *@param ArgThis tests that the function's this refers to *@returns Does the test pass */every(fn: CallbackFn, argThis? :any) :boolean {
if (typeoffn ! = ='function') {
throw new TypeError()}if (this.isEmpty()) {
// Return true if the list is empty
return true
} else {
let node = this.head
let index = 0
while (node) {
const result = fn.call(argThis, node.data, index, this)
if(! result) {return false
}
node = node.next
index++
}
return true}}/** * Populates the value of all nodes in the list from the start index to the end index with a fixed value, excluding the end index *@param Value Indicates the filled value *@param Start Starts the index *@param End Terminates the index *@returns Modified linked list */
fill(value: any, start = 0, end? :number): ExtendsSingleLinkedList {
end = end ?? this.length
let node = this.head
let index = 0
while (node && index < end) {
if (index >= start) {
this.changeNodeValue(node, value)
}
node = node.next
index++
}
return this
}
/** * Create a new linked list containing all nodes * that pass the test function@param Fn Test function *@param ArgThis tests that the function's this refers to *@returns Returns a new linked list */filter(fn: CallbackFn, argThis? :any): ExtendsSingleLinkedList {
const newSingleLinkedList = new SingleLinkedList()
this.loop(
(
nodeData: any.index: number, singleLinkedList? : ExtendsSingleLinkedList ):boolean= > {
if (fn.call(argThis, nodeData, index, singleLinkedList)) {
newSingleLinkedList.push(nodeData)
}
return false})return newSingleLinkedList
}
/** * The function used in the inner loop *@param Fn callback *@returns Returns whether all test functions */ pass
protected loop(
fn: (
nodeData: any,
index: number,
SingleLinkedList: ExtendsSingleLinkedList
) => any
) {
let node = this.head
let index = 0
while (node) {
if (fn(node.data, index, this)) {
return true
}
index++
node = node.next
}
return false
}
/** * returns the first value in the list that satisfies the test function, otherwise undefined * is returned@param Fn Test function *@param ArgThis tests that the function's this refers to *@returns Returns the first value to pass the test function, otherwise undefined */ is returnedfind(fn: CallbackFn, argThis? :any) :any {
let findData
this.loop(
(
nodeData: any.index: number, singleLinkedList? : ExtendsSingleLinkedList ):boolean= > {
if (fn.call(argThis, nodeData, index, singleLinkedList)) {
findData = nodeData
return true
}
return false})return findData
}
/** * returns the index of the first node that satisfies the test function, if not found, -1 * is returned@param Fn Test function *@param ArgThis tests that the function's this refers to *@returns* /findIndex(fn: CallbackFn, argThis? :any) :number {
let findIndex = -1
this.loop(
(
nodeData: any.index: number, singleLinkedList? : ExtendsSingleLinkedList ):boolean= > {
if (fn.call(argThis, nodeData, index, singleLinkedList)) {
findIndex = index
return true
}
return false})return findIndex
}
/** * Execute the following test function * for each node in the list@param Fn Test function *@param ArgThis tests that the function's this refers to */forEach(fn: CallbackFn, argThis? :any) :void {
this.loop(
(
nodeData: any.index: number, singleLinkedList? : ExtendsSingleLinkedList ):boolean= > {
fn.call(argThis, nodeData, index, singleLinkedList)
return false})}/** * Determine if the list contains a value *@param ValueToFind Value to be searched *@param FromIndex The index to start looking for *@returns Contains */
includes(valueToFind: any, fromIndex = 0) :boolean {
let includes = false
this.loop((nodeData: any.index: number) :boolean= > {
if (nodeData === valueToFind && fromIndex <= index) {
return (includes = true)}return false
})
return includes
}
/** * In a linked list, searches for the specified value starting with the specified subscript and returns the found index *@param ValueToFind The value to be searched *@param FromIndex The index to start looking for *@returns Returns the index found, if not, returns -1 */
indexOf(valueToFind: any, fromIndex = 0) :number {
let index = -1
this.loop((nodeData: any.nodeIndex: number) :boolean= > {
if (nodeData === valueToFind && fromIndex <= nodeIndex) {
index = nodeIndex
return true
}
return false
})
return index
}
/ * * * *@param ValueToFind Value to be searched *@param FromIndex searches backwards from this position *@returns* /
lastIndexOf(valueToFind: any, fromIndex = this.length): number {
let index = -1
// Because the one-way list can not reverse order, we have to use the positive order to simulate the reverse order
this.loop((nodeData: any.nodeIndex: number) :boolean= > {
if (nodeData === valueToFind && fromIndex >= nodeIndex) {
index = nodeIndex
}
if (fromIndex <= nodeIndex) {
// Find the end position
return true
}
return false
})
return index
}
/** * concatenates all the elements in the list into a string * using a specific delimiter@param Separator the separator *@returns Returns the concatenated string */
join(separator = ', ') :string {
let str = ' '
this.loop((nodeData: any.nodeIndex: number) :boolean= > {
const isLast = this.length === nodeIndex + 1
str += nodeData + (isLast ? ' ' : separator)
return false
})
return str
}
/** * Creates a new list with the result that each element in the source list is called by the callback value * of the callback function@param Fn callback function *@param The argThis callback refers to *@returns Returns a new linked list */map(fn: CallbackFn, argThis? :any): ExtendsSingleLinkedList {
let newSingleLinkedList = new SingleLinkedList()
this.loop(
(
nodeData: any.index: number, singleLinkedList? : ExtendsSingleLinkedList ):boolean= > {
const result = fn.call(argThis, nodeData, index, singleLinkedList)
newSingleLinkedList.push(result)
return false})return newSingleLinkedList
}
/** * Performs the provided callback function on each element in the list, summarizing its results into a single return value *@param Callback callback function *@param InitialValue initialValue *@returns The sum value */
reduce(
callback: (
accumulator: any,
currentValue: any,
index: number,
singleLinkedList: ExtendsSingleLinkedList
) = > any, initialValue? :any) :any {
let result
this.loop(
(
nodeData: any.nodeIndex: number.singleLinkedList: ExtendsSingleLinkedList
): boolean= > {
if (nodeIndex === 0 && initialValue === void 0) {
// If no initial value is passed, the first element is used as the initial value
result = nodeData
} else {
result = callback(initialValue, nodeData, nodeIndex, singleLinkedList)
}
return false})return result
}
/** * inverts the elements in the list *@returns Reversed linked list */
reverse(): ExtendsSingleLinkedList {
const arr = this.toArray()
this.clear()
arr.forEach((a) = > this.unshift(a))
return this
}
/** * returns a new list from the start index to the end index *@param Begin Start Index contains *@param End The end index does not contain *@returns New linked list */
slice(begin = 0, end = this.length): ExtendsSingleLinkedList {
const newSingleLinkedList = new SingleLinkedList()
this.loop((nodeData: any.nodeIndex: number) :boolean= > {
// End index is not included
if (end <= nodeIndex) {
return true
}
// start index
if (begin <= nodeIndex) {
newSingleLinkedList.push(nodeData)
}
return false
})
return newSingleLinkedList
}
/** * returns whether at least one element in the list passes the test function *@param Fn Test function *@param ArgThis tests that the function's this refers to *@returns Returns whether the test passed */some(fn: CallbackFn, argThis? :any) :boolean {
let result = false
this.loop(
(
nodeData: any.nodeIndex: number.singleLinkedList: ExtendsSingleLinkedList
): boolean= > {
if (fn.call(argThis, nodeData, nodeIndex, singleLinkedList)) {
return (result = true)}return false})return result
}
// values
// toLocaleString
// splice
// sort
// reduceRight
// entries
// flat
// flatMap
// keys
}
export default SingleLinkedList
Copy the codeWrite in the last
List of previous articles
- Vue2 source code analysis nextTick
- Code snippet JS flow limiting scheduler