Data structure Fundamentals

• The list

Features:

Find node O(n); Insert and delete node O(1);

Application Scenarios:

1. Dynamic memory allocation within the operating system
2. LRU cache elimination algorithm

// Create a linked list
var MyLinkedList = function() {
    this.head = null
    this.tail = null
    this.length = 0
};

var ListNode = function(val) {
    this.val = val
    this.next = null
}

MyLinkedList.prototype.get = function(index) {
    if (index >=0 && index < this.length) {
        let i = 0
        let cur = this.head
        while (i < index) {
            cur = cur.next
            i ++
        }
        return cur.val
    } else {
        return -1}}; MyLinkedList.prototype.addAtHead =function(val) {
    const lastHead = this.head
    const node = new ListNode(val)
    this.head = node
    this.head.next = lastHead
    if (!this.tail) {
        this.tail = node
        this.tail.next = null
    }
    this.length ++
};

MyLinkedList.prototype.addAtTail = function(val) {
    const lastTail = this.tail
    const node = new ListNode(val)
    this.tail = node
    if (lastTail) {      
        lastTail.next = this.tail
    }
    if (!this.head) {
        this.head = node
        this.head.next = null
    }
    this.length ++
};

MyLinkedList.prototype.addAtIndex = function(index, val) {
    if (index === this.length) {
        this.addAtTail(val)
    } else if (index <= 0) {
        this.addAtHead(val)
    } else if (index > 0 && index < this.length) {
        let i = 0
        let prev = this.head
        while (i < index - 1) {
            prev = prev.next
            i ++
        }
        const node = new ListNode(val)
        node.next = prev.next
        prev.next = node
        this.length ++
    }
};

MyLinkedList.prototype.deleteAtIndex = function(index) {
    if (index > 0 && index < this.length) {
        let i = 0
        let prev = null
        let cur = this.head
        while (i < index) {
            prev = cur
            cur = cur.next
            i ++
        }
        prev.next = cur.next
        if (index === this.length - 1) {
            this.tail = prev
        }
        this.length --
    } else if (index === 0) {
        this.head = this.head.next
        this.length --
    }
};
/ / print
const output = function(head) {
  let cur = head
  while (cur) {
    console.log(cur.val)
    cur = cur.next || null}};Copy the code

• The queue

Application Scenarios:

1. CPU Hyper-threading technology (virtual quad-core)
2. Thread pool task queue (buffer)

The monotonous queue

Solve the interval maximum problem

The team

Move to the end of the team, removing elements that previously broke monotony from the end of the team (maintaining monotony)

Out of the team

If the first element is out of range, the element is removed from the team first

features

The first element is always the maximum value of the range

// m is the sliding window size
const monotoneQueue = (arr, m) = > {
  let queue = []
  for (let i = 0; i < arr.length; i++) {
    while (queue.length && arr[queue[queue.length - 1]] > arr[i]) {
      queue.pop()
    }
    queue.push(i)
    if (i - queue[0] === m) queue.shift()
    if (i + 1 < m) continue
    console.log(arr[queue[0]])}}Copy the code

• The stack

Characteristic: Full inclusion between events

Application Scenarios:

1. Operating system thread stack
2. Expression evaluation

Monotonous stack

Maintain recent (large/small) relationships

const monotoneStack = (arr) = > {
  // monotonically increasing
  let stack = []
  // The nearest less than value can be found before storing it
  let prev = new Array(arr.length).fill(-1)
  // The nearest less than value can be found
  let next = new Array(arr.length).fill(arr.length)
  for (let i=0; i<arr.length; i++) {
    while (stack.length && arr[stack[stack.length-1]] > arr[i]) {
      next[stack[stack.length-1]] = i
      stack.pop()
    }
    if(! stack.length) { prev[i] = -1
    } else {
      prev[i] = stack[stack.length-1]
    }
    stack.push(i)
  }
  console.log(prev)
  console.log(next)
}
// input  [6,7,9,0,8,3,4,5,1,2]
/ / prev [1, 1, 1,3,3,5,6,3,8]
/ / next,3,3,10,5,8,8,8,10,10 [3]
Copy the code

• The tree

classification

Binary tree

• Each node has a maximum degree of 2
• There is one more node with degree 0 than with degree 2

Complete binary tree

• A tree with empty nodes only at the right of the last level
• Child node I => Left child: 2I; Right child: 2i+1
• To store (an array) in contiguous space.

Full binary tree

There are only nodes of degree 0 and degree 2

Perfect binary tree

Every floor is full

application

Nodes represent collections, edges represent relationships, and are used to handle lookups

	The heap	Maintenance collection is the most valuable weapon
Complete binary tree	Priority queue	Maintenance collection is the most valuable weapon
	The dictionary tree	String and related conversion problems of the magic weapon
Multi-fork tree/forest	AC automata	String and related conversion problems of the magic weapon
	Check and set	The magic weapon for connectivity issues
Binary sort tree	AVL tree	An underlying implementation of an important data retrieval container in the language standard library
	2-3 tree	An underlying implementation of an important data retrieval container in the language standard library
	Red and black tree	An underlying implementation of an important data retrieval container in the language standard library
	B – / B + tree tree	File system, an important data structure underlying a database

recursive

1. Data induction -> structural induction
2. Give recursive functions an explicit meaning
3. Thinking about boundary conditions
4. Implement the recursive process

/ / spanning tree
function TreeNode(val) {
  this.val = val
  this.left = this.right = null
}

const creatTree = function(src) {
  let root = new TreeNode()
  let result = new TreeNode()
  result = null
  let queue = []
  for (let i = 0; i < src.length; i++) {
    if (i == 0) {
      root = new TreeNode(src[i])
      result = root
      queue.push(root)
    }
    if (queue.length) {
      root = queue.shift()
    } else {
      break
    }
    if (i + 1 < src.length && src[i + 1]! = =null) {
      root.left = new TreeNode(src[i + 1])
      queue.push(root.left)
    }
    if (i + 2 < src.length && src[i + 2]! = =null) {
      root.right = new TreeNode(src[i + 2])
      queue.push(root.right)
    }
    i = i + 1
  }
  return result
}

Copy the code

The heap

Is a complete binary tree that deals with set maxima

Small cap pile

The value of the parent node is less than the value of the two children nodes in any three nodes

Big pile top

The value of the parent node is greater than the value of the two children nodes in any three nodes

// Implement the big top heap
class MaxHeap {
  constructor(data = []) {
    this.data = data
    // this.comparator = (a,b) => a-b
    this.heapify()
  }
  heapify() {
    if (this.size() < 2) return
    for(let i=1; i <this.size(); i++) {
      this.bubbleUp(i)
    }
  }

  peek() {
    if (this.size === 0) return null
    return this.data[0]}push(value) {
    this.data.push(value)
    this.bubbleUp(this.size() - 1)}pop() {
    if (this.size === 0) {
      return null
    }
    const result = this.data[0]
    const last = this.data.pop()
    if (this.size() ! = =0) {
      this.data[0] = last
      this.bubbelDown(0)}return result
  }
  
  swap(index1, index2){[this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]]
  }

  size() {
    return this.data.length
  }

  bubbleUp(index) {
    while(index > 0) {
      const parentInd = Math.floor((index-1) / 2)
      if (this.data[parentInd] < this.data[index]) {
        this.swap(index, parentInd)
        index = parentInd
      } else {
        break; }}}bubbelDown(index) {
    const lastIndex = this.size() - 1
    while(true) {
      const leftIndex = index * 2 + 1;
      const rightIndex = index * 2 + 2;
      let findIndex = index
      if (leftIndex<= lastIndex && this.data[leftIndex] > this.data[findIndex]) {
        findIndex = leftIndex
      }
      if (rightIndex<= lastIndex && this.data[rightIndex] > this.data[findIndex]) {
        findIndex = rightIndex
      }
      if(index ! == findIndex) {this.swap(index, findIndex)
        index = findIndex
      } else {
        break}}}}Copy the code

Check and set

The Quick – Find algorithm

Dyeing method: record the color of each node, and dye the connected points into the same color

The Quick – Union algorithm

Tree structure: Records the number of the parent node of each node, the two points that will be connected together, one of the parent nodes pointing to the other

Optimization 1 (Balance optimization)

When two sets are merged, the root node of the larger set serves as the root node of the new set

Optimization 2 (path compression)

When the parent of the current node is not the root node, the parent of the current node points to the parent of the parent node (node moved up)

Algorithm	Constructor	Union	Find
Quick-Find	N	N	1
Quick-Union	N	Tree height	Tree height
Weighted Quick-Union	N	1gN	1gN
Weighted Quick-Union With Path Compression	N	Near to 1	Near to 1

class UnionSet {
  constructor(size) {
    this.set = new Array(size)
    this.cnt = new Array(size)
    for(let i=0; i<size; i++) {
      this.set[i] = i
      this.cnt[i] = 1}}get(a) {
    return this.set[a] = this.set[a] === a ? a : this.get(this.set[a])
  }

  merge(a, b) {
    this.cnt[this.get(b)] += this.cnt[this.get(a)]
    this.set[this.get(a)] = this.get(b)
  }
}
Copy the code