数据结构

一、前 言

数据结构是计算机科学中一门很重要的学科，可以说想要了解或者学习算法，数据结构必需要了解。我不是计算机毕业，数据结构大学的时候印象里好像是开过这么课的，但是好像是选修课，没有好好学。现在既然生活中吃了计算机有关的饭碗，那这门课还是有必要仔细学习。下面的数据结构内容来源于algorithms

1.链表-B

链表表示的是元素的线性集合状态，在计算机科学中对链表的定义不是由它们在内存中的物理位置作定义，相反，每个元素指向的是下一个元素从而组成的数据结构，这些元素一起表示一个序列。所以链表的一个缺点是访问时间是线性的，难以管道化。

我们先了解下单向链表，单项链表由两个部分组成，链表本身和链表节点。先看下链表节点：

[10|•] → [20|•] → [30|•] → NULL
 ↑head

• • 表示指针
• NULL 表示链表结束

  export default class LinkedListNodePL {
  
  constructor(value, next = null) {
  //格式判断必需为null或者LinkedListNode类型
  if (next !== null && !(next instanceof LinkedListNodePL)) {
           throw new TypeError('next must be null or LinkedListNodePL instance');
      }
           this.value = value; //赋值数据
           this.next = next; //赋值节点
      }
  /**
  * 所有值默认转string，如果需要其它转型自己传定义回调
  * @param {Function} callback
  */
  toString(callback) {
      if (typeof callback === 'function') {
          return callback(this.value);
      }
  // 处理常见数据类型
      if (this.value === null) return 'null';
      if (this.value === undefined) return 'undefined';
      if (typeof this.value === 'object') return JSON.stringify(this.value);
          return String(this.value);
      }
  
  setValue(value) {
      this.value = value;
      return this; // 支持链式调用
      }
  
  setNext(next) {
      this.next = next;
      return this; // 支持链式调用
      }
  /**
  * 创建新节点(静态工厂方法)
  * @param {*} value value
  * @param {LinkedListNodePL | null} next
  * @returns {LinkedListNodePL}
  */
  static create(value, next = null) {
      return new LinkedListNodePL(value, next);
      }
  }

import Comparator from '../../utils/comparator/Comparator';
import LinkedListNodePL from './LinkedListNodePL';

export default class LinkedListPL {
/**
* 链表对比函数
* @param {Function} compatatorFunction
*/
constructor(compatatorFunction) {
/** @var LinkedListNode */
this.head = null; //首  null | LinkedNodePL
/** @var LinkedListNode */
this.tail = null; //尾 null | LinkedNodePL
//对比实例
this.compare = new Comparator(compatatorFunction);
}
/**
* 添加值
* @param {*} value
*/
append(value) {
const newNode = new LinkedListNodePL(value);
//head不存在，说明链表暂时是空的，首尾都是value这个值
if (!this.head) {
this.head = newNode;
this.tail = newNode;
return this;
}
//将新节点添加到链表的末尾
this.tail.next = newNode;
this.tail = newNode;
return this;
}
/**
* 插入到链表固定某个值
* @param {*} value
* @param {number} rawIndex
*
*/

insert(value, rawIndex) {
const index = rawIndex < 0 ? 0 : rawIndex;
//如果rawIndex===0插入首部
if (index === 0) {
this.prepend(value);
} else {
let count = 1,
currentNode = this.head;
const newNode = new LinkedListNodePL(value); //创建新节点a,此时节点next为null
while (currentNode) {
if (count === index) break;
currentNode = currentNode.next;
count += 1;
}
if (currentNode) {
newNode.next = currentNode.next;
currentNode.next = newNode;
} else {
if (this.tail) {
this.tail.next = newNode;
this.tail = newNode;
} else {
this.head = newNode;
this.tail = newNode;
}}}}

/**
* @param {*} value
* @return {LinkedList}
*/
prepend(value) {
// Make new node to be a head.
const newNode = new LinkedListNodePL(value, this.head);
this.head = newNode;
// If there is no tail yet let's make new node a tail.
if (!this.tail) {
this.tail = newNode;
}
return this;
}

/**
* @param {function} [callback]
* @return {string}
*/
toString(callback) {
return this.toArray().map((node) => node.toString(callback)).toString();
}

  

/**
* @return {LinkedListNodePL[]}
*/
toArray() {
const nodes = [];
let currentNode = this.head;
while (currentNode) {
nodes.push(currentNode);
currentNode = currentNode.next;
}
return nodes;
}}


/**
 * @description 删除链表中所有值为value的节点
 * @param {*} value 想要删除的值
 * @returns 删除的节点
 */
delete(value) {
//判断链表是否为空
if (!this.head) return null;
//定义需要删除节点的变量
let deletedNode = null;
//判断删除节点是否是头节点compare比较函数，等于的时候输出0才会跳出，否则一直执行
while (this.head && this.compare.equal(this.head.value, value)) {
    deletedNode = this.head;
    this.head = this.head.next;
    }
    let currentNode = this.head;
    
    if (currentNode !== null) {
        while (currentNode.next) {
            if (this.compare.equal(currentNode.next.value, value)) {
                deletedNode = currentNode.next;
                currentNode.next = currentNode.next.next;
            } else {
                currentNode = currentNode.next;
            }}}
        if (this.compare.equal(this.tail.value, value)) {
            this.tail = currentNode;
        }
    //如果删除的节点是头节点，说明链表只有一个节点,始终返回的是最后一个被删除的匹配数;
    return deletedNode;
}

2.双向琏表-B

3.队列-B

4.栈-B

5.哈希表(散列)-B

6.堆-B

7.优先队列-B

8.字典树-A

9.树-A

10.二叉查找树-A

11.AVL 树-A

12.红黑树-A

13.线段树-A

14.树状数组-A

15.图-A

16.并查集-A

17.布隆过滤器-A