数组

数组是最为简单、最为常见的数据结构.

数组在内存中顺序储存,因此也很好的实现了逻辑上的顺序表

内存是由一个个连续的内存单元组成的，每一个内存单元都有自己的地址，在这些内存单元中，有的被其他数据占用，有的是空闲的.

数组中的每一个元素，都储存在小小的内存单元中，并且元素之间紧密排列，既不能打乱元素的储存顺序，也不能跳过某个储存单元进行储存.

数组的操作

数组读取元素时间复杂度为 O(1)

更新元素时间复杂度为 O(1)

插入(头部插入、中间插入、尾部插入、超范围插入)的时间复杂度为 O(n)，数组的扩容时间复杂度为O(n)

删除时间复杂度为O(n)

数组的优劣

数组拥有非常高效的随机访问能力, 只要给出下标，就可以用常量的时间找到对应的元素. 有一种高效查找元素的算法叫做二分查找，就是利用数组的这个优势.

数组的劣势体现在插入和删除元素方面，由于数组元素连续紧密的储存在内存中，插入、删除元素都会导致大量元素被迫移动，影响效率.

总体上数组适合读操作多，写操作少的场景

链表

链表是一种在物理上非连续、非顺序的数据结构，由若干节点(node)组成

单向链表

单向链表的每一个节点又包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节点的指针 next

1  interface Node{
2      data:any,
3      next:Node
4  }
5

链表中的第一个节点被称为头节点，最后一个节点被称为尾节点，尾节点的next指针指向空

与数组按照下标来随机寻找元素不同，对于链表的其中一个节点，只能根据节点A的next指针来找到下一个节点B，再根据节点B的next指针找到下一个节点C.......

双向链表

双向链表具有回溯到它前置节点的能力

双向链表的每一个节点除了拥有 data 和 next 指针, 还拥有指向前置节点的 prev 指针

链表的储存方式

如果说数组在内存中的储存方式是顺序储存，那么链表在内存中的储存方式则是随机储存

什么叫随机储存, 数组在内存中占用了连续完整的内存空间，而链表则是采用了见缝插针的方式，这样可以灵活有效的利用零散的碎片空间.

图中的箭头代表链表节点的next指针

链表的基本操作

1. 查找

在查找元素时，链表不像数组那样可以根据下标快速定位，只能从头节点开始，向后一个一个节点逐一查找, 所以时间复杂度为O(n)

2. 更新

尾部插入、头部插入、中间插入的时间复杂度都为O(1)

3. 删除

尾部删除、头部删除、中间删除的时间复杂度都为O(1)

实现代码

1    interface LinkedNodeType{
2        data: any;
3        next: LinkedNodeType | null;
4    }
5    
6    
7    class LinkedNode{
8        data: any
9        next: LinkedNodeType | null
10        public constructor(data: any){
11            this.data = data;
12            this.next = null;
13        }
14    }
15    
16    class LinkedData{
17        size: number;
18        head: LinkedNodeType|null;
19        last: LinkedNodeType|null;
20        constructor(){
21            this.size = 0; // 链表实际长度
22            this.head = null; // 头节点指针
23            this.last = null; // 尾节点指针
24        }
25    
26    
27        /**
28         * @description 插入元素操作
29         * @param {*} data  插入的元素
30         * @param {*} index 插入的位置
31         */
32        insert(data:any, index:number): void{
33            if(index < 0 || index > this.size) {
34                throw new Error('超出链表节点范围');
35            }
36            const node = new LinkedNode(data);
37            if(this.size === 0) {
38                // 插入头部
39                this.head = node;
40                this.last = node;
41            } else if(this.size === index){
42                // 插入尾部
43                (this.last as LinkedNode).next = node;
44                this.last = node;
45            } else {
46                // 插入中间
47                const prevNode = this.getNode(index - 1);
48                const nextNode = this.getNode(index + 1);
49                prevNode.next = node;
50                nextNode.next = nextNode;
51            }
52            this.size++;
53        }
54        /**
55         *
56         * @description 查找元素操作
57         * @param {number} index
58         * @memberof LinkedData
59         * @returns 返回查找的节点
60         */
61        getNode(index:number): LinkedNodeType {
62            if(index < 0 || index >= this.size) {
63                throw new Error('超出链表节点范围');
64            }
65            let temp = (this.head as LinkedNode);
66            for (let i = 0; i < index; i++) {
67                temp = (temp.next as LinkedNode);
68            }
69            return temp;
70        }
71    
72    
73        /**
74         * @description 删除节点
75         * @param {*} index
76         * @memberof LinkedData
77         */
78        remove(index:number): LinkedNodeType {
79            if(index < 0 || index >= this.size) {
80                throw new Error('超出链表节点范围');
81            }
82            let removeNode = null;
83            if(index === 0) {
84                // 删除头部节点
85                removeNode = this.head;
86                this.head = (this.head as LinkedNode).next;
87            } else if(index === this.size - 1) {
88                // 删除尾部节点
89                const preNode = this.getNode(index - 1);
90                removeNode = preNode.next;
91                preNode.next = null;
92                this.last = preNode;
93            } else {
94                // 删除中间节点
95                const prevNode = this.getNode(index - 1);
96                const nextNode = (prevNode.next as LinkedNode).next;
97                removeNode = prevNode.next;
98                prevNode.next = nextNode;
99            }
100            this.size--;
101            return removeNode as LinkedNode;
102        }
103        /**
104         * @description 输出链表
105         * @memberof LinkedData
106         */
107        outPut(): void{
108            let temp = this.head;
109            while(temp !== null){
110                console.log(temp.data)
111                temp = temp.next;
112            }
113        }
114    }
115    
116    
117    const link = new LinkedData();
118    link.insert('hello', 0);
119    link.insert('hi', 1);
120    link.insert('第三个', 2);
121    link.insert('第四个', 3);
122    link.remove(0);
123    link.outPut();
124

数组VS链表

数组和链表各有千秋:

数组更适合读多写少的操作，链表更适合读少，写多的操作

摘要总结自: 漫画算法小灰的算法之旅