hi，大家好，我是阿荣，今天分享一些对数据结构和算法精华总结，希望对大家的面试或者工作有一定的帮助；
看完本文可以学到什么
知道哪些数据结构和算法在实际工作中最常用，最重要
理解一些设计上注意事项（经验总结）
掌握常用数据结构和算法核心知识点
数据结构工作中或者开源项目中最常用数据结构：数组/list+hash+tree
O(n)结构：list/栈/队列
O(1)结构：数组/hash/位图
O(logn)树形结构：红黑树/B+树/skiplist
数组
核心点：
1内存空间大小固定，如果支持动态扩展，需要内存迁移，有一定的性能代价，比如C++STL的vector结构；
2内存连续，对CPUcache友好，如果内存空间足够，能用数组就最好用数组结构；
3数组空间一般都是预分配的，不会频繁申请和释放，所以可以提供程序性能，这个做内存池优化的实现手段；
链表
核心点：
可以动态项扩缩容，比较节约空间；
链表编程边界case检查：
每个节点必须有个“指针“要么指向其他节点，要么为空，这样才能把链表串起来，任何操作都必须保证链表完整性，不允许节点无故脱链，所以任何操作之前，都要思考会不会导致节点脱链，如果不下心脱链就会存在内存泄漏风险；
链表作为最基础数据结构，很多高级结构：队列，栈，hash，二叉树，都是在链表基础上演化而来；
编程技巧
头结点解决什么问题？
头结点:是虚拟出来的一个节点，不保存数据。头结点的next指针指向链表中的第一个节点。对于头结点，数据域可以不存储任何信息，也可存储如链表长度等附加信息。头结点不是链表所必需的。
头指针:是指向第一个结点的指针,如果链表没有引入头结点，那么头指针指向的是链表的第一个结点。头指针是链表所必需的。
[注意]无论是否有头结点，头指针始终指向链表的第一个结点。如果有头结点，头指针就指向头结点。
1）对链表的删除、插入操作时，第一个结点的操作更方便
如果链表没有头结点，那么头指针指向的是链表的第一个结点，当在第一个结点前插入一个节点时，那么头指针要相应指向新插入的结点，把第一个结点删除时，头指针的指向也要更新。也就是说如果没有头结点，我们需要维护着头指针的指向更新。因为头指针指向的是链表的第一个结点，如果引入头结点的话，那么头结点的next始终都是链表的第一个结点。
2）统一空表和非空表的处理
有了头结点之后头指针指向头结点，不论链表是否为空，头指针总是非空，而且头结点的设置使得对链表的第一个位置上的操作与在表中其它位置上的操作一致，即统一空表和非空表的处理。
链表最常规操作
删除:遍历链表，找到删除的节点，保存删除节点的pre节点和next节点；
然后pre和next串起来
staticinlinevoid__list_del(structlist_head*prev,structlist_head*next){next-prev=prev;prev-next=next;}
再释放删除节点内存；
添加:遍历链表找到要加入位置（或者节点），保存该节点的pre节点和next节点，然后把新接入插入到链表中：
staticinlinevoid__list_add(structlist_head*new,structlist_head*prev,structlist_head*next){next-prev=new;new-next=next;new-prev=prev;prev-next=new;}
2快慢指针，快慢指针一般都初始化指向链表的头结点head，前进时快指针fast在前，慢指针slow在后，巧妙解决一些链表中的问题。比如：判定链表中是否含有环，寻找链表的中点,寻找距离尾部第K个节点等；
3dummynode，dummynode是链表问题中一个重要的技巧，中文翻译叫“哑节点”，使用通常针对单链表没有前向指针的问题，保证链表的head不会在删除操作中丢失，当链表的head有可能变化（被修改或者被删除）时，使用dummynode可以很好的简化代码，最终返回dummy.next即新的链表。
4通常链表有两种实现方式，一种是抽象独立型，一种是传统耦合型；
list作为常用数据结构，写代码时候经常会遇到，可以看一下传统list设计和抽象list设计有什么不一样。
一般的双向链表一般是如下的结构:
有个单独的头结点(head)
每个节点(node)除了包含必要的数据之外，还有2个指针(pre,next)
pre指针指向前一个节点(node)，next指针指向后一个节点(node)
头结点(head)的pre指针指向链表的最后一个节点
最后一个节点的next指针指向头结点(head)
传统list如下图：
传统的链表不同node类型，需要重新定义结构，不够通用化，还需要为node实现脱链、入链操作等。
我们需要抽象出一个“基类”来实现链表的功能，其他数据结构只需要简单的继承这个链表类就可以了。
抽象型list设计如下：
链表不是将用户数据保存在链表节点中，而是将链表节点保存在用户数据中
链表节点只有2个指针(prev和next)
prev指针指向前一个节点的链表节点，next指针指向后一个节点(node)的链表节点
如下图：
这样设计的好处是链表的节点将独立于用户数据之外，便于把链表的操作独立出来，和具体数据节点无关，这里可能有些人会问，数据节点怎么访问呢？通过一个container_of的宏从链表节点找到数据节点起始