单链表、双链表、循环单链表、循环双链表、哈希表、hashmap

单链表：拥有指向下一节点的指针。查找元素须要从头结点遍历数组

双链表：拥有指向上一节点和下一节点的指针。相对于单链表，在找当前节点的前一节点时比较方便，占用空间比单链表大。函数

单循环链表：单链表中，从一已知结点出发，只能访问到该结点及其后续结点，没法找到该结点以前的其它结点。而在单循环链表中，从任一结点出发均可访问到表中全部结点，这一优势使某些运算在单循环链表上易于实现。性能

双循环链表：能够从任何结点开始任意向前向后双向访问。设计

单链表和单循环链表：只能在当前结点后插入和删除。3d

双链表：能够在当前结点前面或者后面插入，能够删除前趋和后继（包括结点本身）。指针

存储：单链表和单循环链表存储密度大于双链表。对象

哈希表：在哈希表中进行添加，删除，查找等操做，性能十分之高，不考虑哈希冲突的状况下，仅需一次定位便可完成，时间复杂度为O(1)。咱们要新增或查找某个元素，咱们经过把当前元素的关键字 经过某个函数映射到数组中的某个位置，经过数组下标一次定位就可完成操做。blog

　　　　　　　　存储位置 = f(关键字)内存

　　其中，这个函数f通常称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。例如：hash

当咱们对某个元素进行哈希运算，获得一个存储地址，而后要进行插入的时候，发现已经被其余元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证获得的存储地址绝对不发生冲突。哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap便是采用了链地址法，也就是数组+链表的方式，

hashmap：简单来讲，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，若是定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操做很快，仅需一次寻址便可；若是定位到的数组包含链表，对于添加操做，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，不然新增；对于查找操做来说，仍需遍历链表，而后经过key对象的equals方法逐一比对查找。因此，性能考虑，HashMap中的链表出现越少，性能才会越好。