coolliyong.github.io

JavaScript数据结构和算法 数据结构总结1【数组】、【链表】、【散列表】、【字典】

数据结构和算法是针对各类场景而创造的,用于解决特定问题的。

数组

1. 优点:计算机中连续的内存,通过索引读取和修改速度极快O(1)。
2. 缺点:增加和删除复杂度相对大,因为通常数组的长度是固定的,很有可能牵一发动全身O(n)  

链表

1. 优点:不需要使用连续的内存,删除和新增、修改速度极快O(1)。
2. 缺点:线性结构,查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。

队列

1. 优点:线性存储空间,具有FIFO(First In First Out)特点,通常使用链表或数组来实现

1. 优点:线性存储空间,具有LIFO(Last In First Out)特点,通常使用链表或数组来实现

哈希表

1. 优点:是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。
2. 缺点:当产生了哈希冲突之后,查找复杂度会增加

字典 (关联数组)

1. 优点:“关联数组”是一种具有特殊索引方式的数组。不仅可以通过整数来索引它,还可以使用字符串或者其他类型的值(除了NULL)来索引它。