各种数据结构的简单特点

1、列表

包括

（1）数组

【1】会在内存中开辟一个连续的内存空间

【2】随机访问的效率比链表高。数组只要给定下标，则可以直接定位到该下标所对应的元素，而链表每次都是从头节点开始遍历。

【3】对元素的增删操作的效率比链表低。这里说的是从数组的中间插入或删除一个元素，并且数组中元素很多，实验证明，在数组头部或结尾增加或删除一个元素的效率和链表差不多。

为什么？

比如，每次对数组中间某一个元素进行删除的操作，则此元素后面的所有元素都得往前面移动，耗费大量的时间和性能。

而对链表中间某一个元素进行删除的操作，只需将此节点的指针与前驱结点和后继节点断开即可，元素并没有发生移动。

这个特点，可以解释ArrayList与LinkedList之间的区别

 

（2）链表

【1】通过一个个指针将节点串起来

【2】对于元素的随机访问，需要使用计数器来访问指定的元素，并且只能从头节点开始访问，每访问一个节点，计数器加1，直到给定的“下标”，此操作很耗时，时间复杂度为O(N)

【3】增加元素和删除元素的效率很高

 

（3）队列

【1】不支持随机访问

【2】先进先出

【3】线程池中的线程就是从任务队列中取出任务

 

（4）栈

【1】不支持随机访问

【2】后进先出

 

 

2、树

（1）二叉树

【1】每个节点最多只有两个子节点

（2）搜索树

【1】二分查找，数组对半分的路径就是一个搜索树

【2】不一定是二叉树

（3）堆/优先队列

【1】按照顺序pop出元素

【2】优先队列中，以最小堆为例，树或子树根结点都是所在树或子树中最小的元素

 

3、栈、队列、优先队列中的元素弹出顺序

例 push(1)   push(3)   push(2)  pop()    pop()   pop()

（1）栈 

弹出顺序为 2，3，1   【后进先出】

（2）队列

弹出顺序为 1，3，2   【先进先出】

（2）优先队列

弹出顺序为 1，2，3   【从小到大，具有顺序性】

 

4、Map<K,V>和Set<K>接口

（1） HashMap/HashSet

【1】都基于哈希表的实现

【2】每个Object都有一个哈希值，上面两者实现类都基于这个哈希值

HashSet如何区分待插入元素重复？

先得到这个元素的hashCode，若HashSet中不存在此hashCode对应的元素，则直接将此元素插入到HashSet中

若HashSet中存在此hashCode对应的元素，将这些元素拿出来与待插入元素进行equals判断，若全相等，则不插入，否则插入

（2）TreeMap/TreeSet 

【1】K必须实现Comparable接口

【2】K被放入树中

 

 

5、图

（1）无向图

【1】每个节点都没有方向，边上可能有权重

（2）有向图

【1】每个节点是有方向的的

（3）有向无环图

【1】可以描述任务之间的关系