什么是动态数据结构：动态数据结构是支持动态的更新操作，里面存储的数据是时刻在变化的，通俗一点讲，它不仅仅支持查询，还支持删除、插入数据。而且，这些操作都非常高效。如果不高效，也就算不上是有效的动态数据结构了。所以，红黑树算一个，支持动态的插入、删除、查找，而且效率都很高。

 划重点：学习数据结构和算法，要学习它的由来、特性、适用的场景以及它能解决的问题。

总结1

散列表：插入删除查找都是O(1), 是最常用的，但其缺点是不能顺序遍历以及扩容缩容的性能损耗。适用于那些不需要顺序遍历，数据更新不那么频繁的。

跳表：插入删除查找都是O(logn), 并且能顺序遍历。缺点是空间复杂度O(n)。适用于不那么在意内存空间的，其顺序遍历和区间查找非常方便。

红黑树：插入删除查找都是O(logn), 中序遍历即是顺序遍历，稳定。缺点是难以实现，去查找不方便。其实跳表更佳，但红黑树已经用于很多地方了。 

总结2

**基本数据结构：**

1.数组：连续的内存空间，支持按下标随机访问O(1)，删除和查找设计数据搬移效率是O(n) 试用场景：数据规模较小，不经常变动。

缺点：对于内存连续性要求高。插入删除操作效率低。

2.链表：查询效率不高O(n)，插入和删除效率高O(1)，并且内存申请可以不连续，适用场景是插入和删除多于查询操作。

缺点：查找效率低，实际上删除之前先要查找，所以实际删除效率也不高。

**动态数据结构：**

1.散列表：可以说是利用数组和链表两个基本数据结构设计了一个高效的动态数据结构。利用了数组的随机访问特性，用于满足根据某个属性来随机访问元素。基于key查找效率很高O(1).同时借助链表进行散列冲突解决方案，删除和插入操作效率也可以接近O(1).试用场景：海量数据随机访问、防止重复、缓存等。

缺点：需要设计合理的散列函数，并且要考虑散列冲突和动态扩容。

2.跳表：尽管散列表效率很高，但是散列表是无序的，跳表效率和散列表类似，并且支持区间序列的输出（因为基于链表）。使用场景：对有序元素的快速查找、插入和删除。

缺点：比较占用内存。

3.红黑树：红黑树是平衡二叉查找树的一种近似实现。红黑树和跳表类似，但是实现方式有所差异。红黑树存在的价值是，它可以实现比较高效的查找，删除和插入。虽然相比高度平衡的AVL树效率有所下降，但是红黑树不用耗费太多精力维护平衡。相比跳表，红黑树除了内存占用较小，其他性能并不比跳表更优。但由于历史原因，红黑树使用的更广泛。

缺点：实现比较复杂。

总结3

动态数据结构还包括以下几种：

1.链表：

优势：高效地数据插入、删除。

缺点：随机查找元素效率较低。

适用场景：适用于顺序访问数据，数据维护较频繁的场合。

2.哈希链表

优势：高效地数据插入、删除、随机查找元素。

缺点：需要设计一个好的散列函数，把元素均匀分散到散列表中。

适用场景：适用于在海量数据中随机访问数据的场合。

3.跳表

优势：高效地查找、插入、删除数据。

缺点：需要额外的空间来构建索引链表

适用场景：适用于需要高效查找数据的场合。

4.二叉查找树

优势：高效地查找、插入、删除数据，实现简单。

缺点：需要动态地维护左右子树的高度平衡，否则数据查找会退化成链表的顺序查找。

适用场景：适用于需要高效查找数据的场合。