常见的数据结构

发表于 | 更新于: | 分类于

队列 栈 链表 集合 hash表 树 图

1) 队列 先进先出 （排队）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Queue{
    constructor(){
        this.queue = [];
    }
    enqueue(element){
        this.queue.push(element);
    }
    dequeue(){
        this.queue.shift();
    }
}
let queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.dequeue();
console.log(queue.queue); // [ 2 ]
2）栈 先进后出 （喝水）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Stack{
    constructor(){
        this.stack = [];
    }
    put(element){
        this.stack.push(element);
    }
    pop(){
        this.stack.pop();
    }
}
let stack = new Stack();
stack.put(1);
stack.put(2);
stack.pop();
console.log(stack.stack); // [ 1 ]
3) 链表 ( 单项链表 双向链表 循环链表)

操作数据不需要破坏数据的原有结构
现在实现单向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// 描述：整个链表是一个类 每个节点也是一个类
class Node{ // 代表链表中的某一个节点
    constructor(element){
        this.value = element;
        this.next = null;
    }
}
class LinkList{
    constructor(){
        this.head = null;
        this.length = 0;
    }
    insert(position, element){
        let node = new Node(element);
        if(!this.head){
            this.head = node;
        }else{
            let index = 0;
            let current = this.head;
            let prev = null;
            while (index++ < position) {
                prev = current;
                current = current.next;
            }
            prev.next = node;
            node.next = current;
        }
        this.length ++;
    }
    append(element){
        let node = new Node(element);
        if(!this.head){
            this.head = node;
        }else{
            // 这里 为了找到链的最后一个 让它的next指向当前node
            let index = 0; // 从0项开始查找
            let current = this.head; // 先把链表的头拿出来 开始查找
            while (++index < this.length) {
                current = current.next; // 如果当前不是最后一项就把这个人的下一项继续查找
            }
            current.next = node;
        }
        this.length ++;
    }
}
let ll = new LinkList();
console.log("----1----");
ll.append(1); //这里这个append是自定义的方法，表示向链表中加入节点
console.log(JSON.stringify(ll))
console.log("----2----");
ll.append(2);
console.log(JSON.stringify(ll))
console.log("----3----");
ll.append(3);
console.log(JSON.stringify(ll))
/*
执行结果：
----1----
{"head":{"value":1,"next":null},"length":1}
----2----
{"head":{"value":1,"next":{"value":2,"next":null}},"length":2}
----3----
{"head":{"value":1,"next":{"value":2,"next":{"value":3,"next":null}}},"length":3}
*/

let ll = new LinkList();
ll.append(1); //这里这个append是自定义的方法，表示向链表中加入节点
ll.append(2);
ll.append(3);
ll.insert(1,100); // 往1和2之间插
console.log(JSON.stringify(ll));
// 执行结果：
// {"head":{"value":1,"next":{"value":100,"next":{"value":2,"next":{"value":3,"next":null}}}},"length":4}

Array是一块顺序的内存，增加值的时候内存要移动，链表的话不用改变原本的数据位置

4） 集合 放置不能重复的项
1
2
3
4
5
6
let set = new Set();
set.add(1);
set.add(2);
set.add(3);
console.log(set); // Set { 1, 2, 3 }
// Set的特点是key value 相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Set{
    constructor(){
        this.set = {};
    }
    add(element){
        if( !this.set.hasOwnProperty(element)){ // 不能重复
            this.set[element] = element;
        }
    }
}
let set = new Set();
set.add(1);
set.add(1);
set.add(2);
console.log(set); // Set { set: { '1': 1, '2': 2 } }
// 感觉还是跟原来的不太一样 es6里面的set、map看一下
5) Map hash表 图
1
2
3
4
5
6
let map = new Map();
map.set('abc', 123);
map.set('bbb', 456);
// 这里组成的是一张表，abc对应的是123.bbb对应的是456
console.log(map.get('abc')); // 123
console.log(map.size); // 2

取的时候通过map.get(‘abc’)可以马上拿到123
特点：性能高，而且它不是索引，可以放字符串，数组的话只能放索引，而且它取值的时候可以通过key直接取出来 ，模拟hash如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Map{
    constructor(){
        this.arr = [];
    }
    calc(key){
        let total = 0;
        for(let i = 0; i < key.length; i++){
            total += key[i].charCodeAt();//ASCII
        }
        return total % 100;
        // % 代表如果这个表我最多能存100个（0-99项），想要存10个就%10
    }
    set(key, value){
        key = this.calc(key);
        this.arr[key] = value;
    }
    get(key){
        key = this.calc(key);
        return this.arr[key];
    }
}
// 这里将key（'abc','bbb'）的值转成索引存到数组里面，然后通过key去数组里面找;
// 如果第一项就%出来是99项，那数组前面就都是空项了，所以这个hash表有个特点：松散，如果重复的话可以再加个链表，可以hash+链表的结构存储
// 特点取值快 而且es6已经提供了，可以直接使用
// 运行如下：
let map = new Map();
map.set('abc', 123);
map.set('bbb', 456);
console.log(map.get('abc')); // 456
console.log(map); // Map { arr: [ <94 empty items>, 456 ] }
6） 二叉树 (二叉查找树)

数据存储方式 小的放左边 大的放右边
树的的遍历 递归 查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Node{ // 一个一个的节点
    constructor(element){
        this.element = element;
        this.left = null;
        this.right = null;
    }
}
class Tree{
    constructor(){
        this.root = null; // 树的跟
    }
    insert(root, newNode){
        if(newNode.element < root.element){
            if(root.left == null){
                root.left = newNode;
            }else{
                this.insert(root.left, newNode);
            }
        }else{
            if(root.right == null){
                root.right = newNode;
            }else{
                this.insert(root.right, newNode);
            }
        }
    }
    add(element){
        let node = new Node(element);
        if( !this.root){
            this.root = node;
        }else{
            this.insert(this.root, node);
        }
    }
}
let tree = new Tree;
tree.add(100);
console.log(tree); //Tree { root: Node { element: 100, left: null, right: null } }
tree.add(60);
tree.add(150);
console.log(tree);
console.log(JSON.stringify(tree));
// {"root":{"element":100,"left":{"element":60,"left":null,"right":null},"right":{"element":150,"left":null,"right":null}}}

红黑树
图 树之间的节点产生关联 邻接表 可以稍微了解下