Java集合框架也算是超超超高频被使用，同时也是经典数据结构的实现。
在讲集合框架之前，我们先简单回顾下数据结构的知识。有一点需要特别说明下：
数据结构≠数据类型
数组
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
这里涉及到线性表的概念，“线性”，说明这是一个只有头尾的结构，因此链表、队列、栈等也属于线性表结构，与之对应的就是非线性表，比如树、图等。
数组的定义中还有关键两个信息：连续内存和相同类型。连续内存说明这是一个内存紧凑型结构，这同时也是数组能够达到根据下标进行随机访问的原因。比如：
int[]a=newint[5];
定义一个int类型数组，长度为5，计算机会给数组a分配一个连续的内存空间比如~，首地址就是，有一个寻址公式：
a_address=首地址+i*占用字节
int在java里是4个字节，因此当我们想访问a[2]的元素时，根据寻址公式得到a[2]的元素地址是~。
有一点需要注意，数组根据下标随机访问元素的时间复杂度是O(1),但是查找某个元素的时间复杂度是O(n)，就算是排序好的，那也是O(logn),需要注意不能混淆。
数组有优点那么自然也存在缺点，由于数组的内存连续，当向数组中插入元素或者删除元素时，需要挪动数据，删除元素还涉及到删除后是否需要保持内存连续还是先标记后一次性删除整理（是不是有点类似垃圾回收里的清除算法）。
数组使用时还需要注意一点：越界异常。数组是一种非常省内存的数据结构，因此在平常开发中可以结合业务场景使用数组，达到内存的最优化。
链表
链表也是一种线性表结构，那它跟数组有什么区别？链表不需要连续内存，元素在内存中是可以分散开的。
链表常见的有单链表，双向链表和循环链表。
链表的内存是不连续的，那么他们之间是如何相互寻找的尼？这里就涉及到指针这个概念了，链表的每个结点除了存储数据外，还要存储一个指向下一个结点的指针，代码示意：
publicclassNode{privateNodenext;//下一个结点privateObjectobj;//数据}
——data,next——data,next——data,next——data,next——data,next——null
链表中第一个结点叫头结点，最后一个结点叫尾结点，头结点前面应该还有一个无意义的结点或者指针，存储指向头结点或者头节点数据的指针。
与数组相反，链表的插入和删除是非常高效的，O(1)时间复杂度，假如需要在A结点和B结点之间插入一个C结点：
old:Adata,Anext——Bdata,Bnextnew:Adata,Anext——Cdata,Cnext——Bdata,Bnext
把A结点的next指向C，C的next指向B即可，删除也一样。
这里需要注意下，插入和删除时间复杂度是O(1),但是执行插入和删除之前都需要先去查找，这个查找时间复杂度是O(n)，根据加法原则，最终复杂度还是O(n)。
由于内存的不连续因此链表无法像数组一样根据寻址公式来随机访问，链表需要逐个遍历因此时间复杂度是O(n)，查找也一样。
循环链表是单向链表的变形，尾结点的指针指向头结点，形成一个环，因此当处理具有环形结构的数据时非常适合。
双向链表也是单向链表的变形，每个结点不仅有next指针，还有一个pre指针。
Apre,Adata,Anext
双向链表相比单向链表有很多优势，最重要的一点就是支持双向遍历，这也是典型的空间换时间的思想，比如根据给定的指针进行插入或者删除，双向链表的时间复杂度就是O(1)，单向链表因为需要遍历寻找前驱结点，所以O(n)，当然如果根据给定的值去插入或者删除的话都是O(n)。
双向循环链表我想你应该知道长什么样了吧。
栈
栈是一种“操作受限”的线性表，只允许在一端插入和删除数据，FILO(先进后出)。
理论上数据或者链表是可以代替栈的，但是栈不需要暴露那么多接口，只需要出栈、入栈两个接口就够了，因此我们可以利用数组和链表的思想来实现栈。
数组特性的栈也叫顺序栈，链表特性的栈也叫链式栈，顺序栈的基础上再支持数组扩容，这就实现了一个动态扩容的顺序栈。
队列
队列也是一种“操作受限”的线性表，队列只有入队和出队操作，FIFO（先进先出）。
同样也可以基于数组和链表的特性实现队列，分别叫顺序队列和链式队列。
队列常见的有循环队列，阻塞队列，并发队列等。
循环队列就是头尾相连形成一个环，好处就是减少数据搬移的操作。
阻塞队列就是基本队列的变形，队列空时，取数据阻塞，队列满时插入数据阻塞，我们可以使用阻塞队列实现的“生产者——消费者”模型，通过阻塞队列可以很好地协调两者的速度。为了提高消费速度，一般会有多个消费者。
在多线程环境下，会有多个线程操作队列，那么就会涉及到线程安全问题，因此就有了并发队列，除了一般的加锁操作来保证外，还可以使用CAS操作来实现，提高性能。
跳表
跳表就是链表的优化版本，支持快速插入、删除和查找。单向链表，就算是排序好的单向链表查找一个数据也需要逐个遍历，效率很低，如何解决？增加索引层，比如把链表每2个结点提取一个结点到一级索引层，这样的话每次查找时先遍历索引层，根据结果再下沉到原始链表只需进行最多2次遍历即可，很明显提升了查找效率，类似我们也可以建议多层索引，查找效率进一步提高。这也是典型的空间换时间的思想，查找时间复杂度O(n)降到O(mlogn),这个m就是第一层索引是由几个节点提取决定的。索引我们知道是需要根据插入和删除操作动态更新的，比如插入时不更新索引的话，随着数据的增多，最终跳表会慢慢退化成链表。
这也是redis里sortset使用的底层数据结构之一。
散列表
散列表也叫哈希表（hash表）。散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，数组的演化。
举个例子，比如给一个班级的学生生成学号、、......
我们把、等学号经过一个方法计算出对应的数组下标，然后存储其信息，那么我再查找这个学生信息时就非常方便。、也就是我们所知的key，方法就是散列函数，算出来的下标其实就是散列值。
从上线的描述中我们发现散列函数尤为关键。真实的开发中能作为key的数据有很多，远远超过数组所能容纳的数量，因此再怎么完美的算法，最终都无法完全避免哈希冲突。当然这也并非是不可调和的矛盾，一般我们采用的方式是链表办法，当不同的key哈希后散列值一致，那么数据会以链表的方式存储在同一个位置上。
下一篇讲树，尤其是红黑树、B树和B+树。
mbond第21篇