数据结构

  1. 数据结构在物理上分为连续和分散结构，在逻辑上分为线性和非线性结构

数组

初始化数组

1
2
3
// 初始化长度为5的数组，并填充0
let array = new Array(5).fill(0);
console.log(array);

访问数组元素

1
2
3
4
// 访问随机元素
let array = [1, 2, 3, 4, 5];

console.log(array[Math.floor(Math.random() * 5)]);

插入数组元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 元素后移动
let array = [1, 2, 3, 4, 5, 6, 7, 8];

function addItem(array, index, item) {
    if (index > array.length) return;
    for (let i = index; i < array.length; i++) {
        let temp = array[i];
        array[i] = item;
        item = temp;
    }
}


function addItem(array, index, item) {
    if (index > array.length) return;
    for (let i = array.length - 1; i > index; i--) {
        array[i] = array[i - 1];
    }

    array[index] = item;
}

删除元素

1
2
3
4
5
6
7
8
let array = [1, 2, 3, 4, 5, 6, 7, 8];
// 删除元素
function removeItem(array, index) {
    if (index >= array.length) return;
    for (let i = index; i < array.length - 1; i++) {
        array[i] = array[i + 1];
    }
}

遍历数组

1
2
3
4
5
6
7
8
9
// 遍历数组
array.forEach(item => item);
for (let item of array) {

}

for (let i = 0; i < array.length; i++) {

}

查找元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 查找元素
function find(array, item) {
    for (let i of array) {
        if (i === item) {
            return i;
        }
    }
}

function findIndex(array, item) {
    for (let i = 0; i < array.length; i++) {
        if (array[i] === item) {
            return i;
        }
    }

    return -1;
}

链表

链表结构

1
2
3
4
5
6
7
8
9
class ListNode {
    val;
    next;

    constructor(val, next) {
        this.val = val || 0;
        this.next = next || null;
    }
}

初始化链表

1
2
3
4
5
6
7
let node = new ListNode();

let temp = node;
for (let i = 1; i < 10; i++) {
    temp.next = new ListNode(i);
    temp = temp.next;
}

插入节点

1
2
3
4
5
6
function insert(p0, val) {
    let next = p0.next;
    let node = new ListNode(val);
    p0.next = node;
    node.next = next;
}

删除节点

1
2
3
4
5
6
7
// 删除no之后的首个节点
function remove(p0) {
    if (p0.next) {
        let temp = p0.next;
        p0.next = temp.next;
    }
}

查找节点

1
2
3
4
5
6
7
8
9
10
11
12
13
function find(head, target) {
    let index = 0;
    while (head !== null) {
        if (head === target) {
            return index;
        }

        index++;
        head = head.next;
    }

    return -1;
}

栈

栈的特点及其简单实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 先进先出
let stack = [];

// 入栈
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);

// 出栈
stack.pop();

// 访问栈顶元素
stack[stack.length - 1];

// 获取栈的大小
stack.length;

// 判断栈是否为空
stack.length === 0;

链表实现栈

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
class LinkedListStack {
    #stackPeek; // 栈顶元素
    #stackSize; // 栈大小

    constructor() {
        this.#stackPeek = null;
        this.#stackSize = 0;
    }

    get size() {
        return this.#stackSize;
    }

    push(val) {
        let node = new ListNode(val);
        node.next = this.#stackPeek;
        this.#stackPeek = node;
        this.#stackSize++;
    }
    pop() {
        const value = this.peek();
        this.#stackPeek = this.#stackPeek.next;
        this.#stackSize--;

        return value;
    }
    peek() {
        if (!this.#stackPeek) throw new Error('栈为空');
        return this.#stackPeek.val;
    }
    isEmpty() {
        return this.#stackSize === 0;
    }
    toArray() {
        let node = this.#stackPeek;
        const result = new Array(this.size);

        for (let i = 0; i < this.size; i++) {
            result[i] = node.val;
            node = node.next;
        }

        return result;
    }
}

数组实现栈

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
class ArrayStack {
    #stack;

    constructor() {
        this.#stack = [];
    }

    get size() {
        return this.#stack.length;
    }

    isEmpty() {
        return this.size === 0;
    }

    push(val) {
        return this.#stack.push(val);
    }

    pop() {
        if (this.isEmpty()) throw new Error('栈为空');
        return this.#stack.pop();
    }

    peek() {
        if (this.isEmpty()) throw new Error('栈为空');
        return this.#stack[this.size - 1];
    }

    toArray() {
        return this.#stack;
    }
}

队列

  1. 先进先出

初始化队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const queue = [];

// 入队
queue.push(1);
queue.push(3);
queue.push(5);
queue.push(7);

// 访问队首元素
console.log(queue[0]);
// 出队
console.log(queue.shift());
// 队列长度
console.log(queue.length);
// 队列是否为空
console.log(queue.length === 0);

链表实现队列

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
class Queue {
    #front; // 头节点
    #rear; // 尾节点
    #size; // 长度

    constructor() {
        this.#front = null;
        this.#rear = null;
        this.#size = 0;
    }

    get size() {
        return this.#size;
    }

    // 入队
    push(val) {
        const node = new ListNode(val);

        if (this.#front === null) {
            this.#front = node;
            this.#rear = node;
        } else {
            this.#rear.next = node;
            this.#rear = node;
        }

        this.#size++;
    }

    isEmpty() {
        return this.#size === 0;
    }

    pop() {
        const value = this.peek();
        this.#front = this.#front.next;
        this.#size--;

        return value;
    }

    peek() {
        if (this.isEmpty()) throw new Error('队列为空');
        return this.#front.val;
    }

    toArray() {
        let node = this.#front;
        let result = [];

        while(node !== null) {
            result.push(node.val);
            node = node.next;
        }

        return result;
    }
}

数组实现队列

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
class ArrayQueue {
    #nums;
    #front = 0; // 队首
    #rear = 0; // 队尾
    #size = 0;

    constructor(capacity) {
        this.#nums = new Array(capacity);
    }

    get capacity() {
        return this.#nums.length;
    }

    get size() {
        return this.#size;
    }

    isEmpty() {
        return this.#size === 0;
    }

    isFull() {
        return this.size === this.capacity;
    }

    push(val) {
        if (this.isFull()) throw new Error('队列已满');

        if (this.#front === this.#rear) {
            this.#nums[this.#front] = this.#nums[this.#rear] = val;
        } else {
            this.#nums[this.#rear] = val;
        }

        this.#rear++;
        this.#rear %= this.capacity;
        this.#size++;
    }

    peek() {
        if (this.isEmpty()) throw new Error('队列已满');
        return this.#nums[this.#front];
    }

    pop() {
        const value = this.peek();
        this.#front = (this.#front + 1) % this.capacity;
        this.#size--;

        return value;
    }

    toArray() {
        let result = [];

        for (let i = 0; i < this.#size; i++) {
            result.push(this.#nums[(this.#front + i) % this.capacity]);
        }

        return result;
    }
}

双向队列

初始化双向队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const deque = [];

// 队尾元素入队
deque.push(1);
deque.push(3);
deque.push(5);
deque.push(7);

// 队首元素入队
deque.unshfit(0);

// 队首元素
console.log(deque[0]);
// 队尾元素
console.log(deque[deque.length - 1]);

// 队首元素出队
deque.shfit();
// 队尾元素出队
deque.pop();

// 队列长度
console.log(deque.lengths)

链表实现双向队列

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
class ListNode {
    prev;
    next;
    val;

    constructor(val) {
        this.prev = null;
        this.next = null;
        this.val = val;
    }
}


class LinkedListDeque {
    #front;
    #rear;
    #size;

    constructor() {
        this.#front = null;
        this.#rear = null;
        this.#size = 0;
    }

    get size () {
        return this.#size;
    }

    isEmpty() {
        return this.size === 0;
    }

    // 添加队首元素
    pushFirst(val) {
        let node = new ListNode(val);

        if (this.size === 0) {
            this.#front = node;
            this.#rear = node;
        } else {
            this.#front.prev = node;
            node.next = this.#front;
            this.#front = node;
        }

        this.#size++;
    }

    // 添加队尾元素
    pushLast(val) {
        let node = new ListNode(val);

        if (this.size === 0) {
            this.#front = node;
            this.#rear = node;
        } else {
            this.#rear.next = node;
            node.prev = this.#rear;
            this.#rear = node;
        }

        this.#size++;
    }

    // 获取队首元素
    peekFirst() {
        if (this.isEmpty()) throw new Error('队列为空');
        return this.#front.val;
    }

    // 获取队尾元素
    peekLast() {
        if (this.isEmpty()) throw new Error('队列为空');
        return this.#rear.val;
    }

    // 队首出列
    popFirst() {
        const value = this.peekFirst();
        const temp = this.#front.next;
        if (temp !== null) {
            temp.prev = null;
        }
        this.#front.next = null;
        this.#front = temp;
        this.#size--;
        return value;
    }

    // 队尾出列
    popLast() {
        const value = this.peekLast();
        const temp = this.#rear.prev;

        if (temp !== null) {
            temp.next = null;
        }

        this.#rear.prev = null;
        this.#rear = temp;
        this.#size--;

        return value;
    }

    // 打印
    toArray() {
        let temp = this.#front;
        let result = [];

        while(temp !== null) {
            result.push(temp.val);
            temp = temp.next;
        }

        return result;
    }
}

数组实现双向队列

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
class ArrayDeque {
    #nums;
    #front;
    #rear;
    #size;

    constructor(capacity) {
        this.#nums = new Array(capacity);
        this.#front = 0;
        this.#rear = 0;
        this.#size = 0;
    }

    get capacity() {
        return this.#nums.length;
    }

    get size() {
        return this.#size;
    }
    
    isEmpty() {
        return this.size === 0;
    }

    isFull() {
        return this.size === this.capacity;
    }

    index(index) {
        return (index + this.capacity) % this.capacity;
    }

    pushFirst(val) {
        if (this.isFull()) throw new Error('队列已满');

        if (this.size === 0) {
            this.#nums[this.#front] = val;
            this.#nums[this.#rear] = val;
        } else {
            this.#front = this.index(this.#front - 1);
            this.#nums[this.#front] = val;
        }

        this.#size++;
    }

    pushLast(val) {
        if (this.isFull()) throw new Error('队列已满');

        if (this.size === 0) {
            this.#nums[this.#front] = val;
            this.#nums[this.#rear] = val;
        } else {
            this.#rear = this.index(this.#rear + 1);
            this.#nums[this.#rear] = val;
        }

        this.#size++;
    }

    peekFirst() {
        if (this.isEmpty()) throw new Error('队列为空');
        return this.#nums[this.#front];
    }

    peekLast() {
        if (this.isEmpty()) throw new Error('队列为空');
        return this.#nums[this.#rear];
    }

    popFirst() {
        const value = this.peekFirst();
        this.#front = this.index(this.#front + 1);
        this.#size--;
        return value;
    }

    popLast() {
        const value = this.peekLast();
        this.#rear = this.index(this.#rear - 1);
        this.#size--;
        return value;
    }

    toArray() {
        let result = [];
        for (let i = 0; i < this.size; i++) {
            result.push(this.#nums[this.index(this.#front + i)]);
        }

        return result;
    }
}

哈希表

哈希表常用操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
let map = new Map();

map.set(1283, 10);
map.set(175, 18);
map.set(1, 888);

map.get(1);
map.delete(1283);

for (let [k, v] of map.entries()) {
    console.log(k, 'key');
    console.log(v, 'value');
}

for (let k of map.keys()) {
    console.log(k, 'key');
}

for (let v of map.values()) {
    console.log(v, 'value');
}

哈希表简单实现

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
74
75
76
77
78
79
80
81
82
83
84
85
class Pair {
    key;
    value;

    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
}

class HashMap {
    #buckets;

    constructor (capacity) {
        this.#buckets = new Array(capacity).fill(null);
    }

    static MODULE = 100;
    #hash(key) {
        return key % HashMap.MODULE;
    }

    get(key) {
        let index = this.#hash(key);
        let pair = this.#buckets[index];

        if (null !== pair) {
            return pair.value;
        } else {
            return null;
        }
    }

    set(key, value) {
        let index = this.#hash(key);
        this.#buckets[index] = new Pair(key, value);
    }

    delete(key) {
        let index = this.#hash(key);
        this.#buckets[index] = null;
    }

    entries() {
        let result = [];
        for (let bucket of this.#buckets) {
            if (bucket) {
                result.push(bucket);
            }
        }

        return result;
    }

    keys() {
        let result = [];
        for (let bucket of this.#buckets) {
            if (bucket) {
                result.push(bucket.key);
            }
        }

        return result;
    }

    values() {
        let result = [];

        for (let bucket of this.#buckets) {
            if (bucket) {
                result.push(bucket.value);
            }
        }

        return result;
    }

    print() {
        for (let bucket of this.#buckets) {
            if (bucket) {
                console.log(bucket.key + '=>' + bucket.value);
            }
        }
    }
}

哈希冲突与扩容

  1. 对于下面两个 key 来说，通过 hash 函数处理后的 key 值是相同的就出现了 hash 冲突
1
2
1136 % 100
1436 % 100
  1. 负载因子是哈希表的一个重要概念，其定义为哈希表的数量除以桶的数量，用于衡量哈希冲突的严重程度，也常被作为哈希表扩容的触发条件

哈希冲突的几种解决方案

  1. 链式寻址
  2. 开放寻址
    • 平方探测
    • 多次哈希
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// 链式寻址

class HashMap {
    #size; // 数量
    #capacity; // 容量
    #loadThres; // 负载因子阈值
    #extendRatio; // 扩容倍数
    #buckets; // 桶

    constructor() {
        this.#size = 0;
        this.#capacity = 4;
        this.#loadThres = 2.0 / 3.0;
        this.#extendRatio = 2;
        this.#buckets = new Array(this.#capacity).fill(null).map(x => []);
    }

    #hash(key) {
        return key % this.#capacity;
    }

    #loadFactor() {
        return this.#size / this.#capacity
    }

    #extend() {
        this.#capacity *= this.#extendRatio;
        let tempBuckets = this.#buckets;

        this.#buckets = new Array(this.#capacity).fill(null).map(x => []);
        this.#size = 0;

        for (let bucket of tempBuckets) {
            for (let pair of bucket) {
                this.put(pair.key, pair.value);
            }
        }
    }

    get(key) {
        let index = this.#hash(key);

        let buckets = this.#buckets[index];

        for (let pair of buckets) {
            if (pair.key === key) {
                return pair.value;
            }
        }

        return null;
    }

    put(key, value) {
        if (this.#loadFactor() > this.#loadThres) {
            this.#extend()
        }

        let index = this.#hash(key);
        let buckets = this.#buckets[index];

        for (let pair of buckets) {
            if (pair.key === key) {
                pair.value = value;
                return;
            }
        }

        let pair = new Pair(key, value);
        buckets.push(pair);
        this.#size++;
    }

    remove(key) {
        let index = this.#hash(key);
        let buckets = this.#buckets[index];

        let pairIndex = buckets.findIndex(item => item.key === key);

        if (pairIndex !== -1) {
            buckets.splice(pairIndex, 1);
            this.#size--;
        }
    }

    print() {
        for (let bucket of this.#buckets) {
            for (let pair of bucket) {
                console.log(pair.key + ' => ' + pair.value);
            }
        }
    }
}