线性表

数据元素的排列方式是线性的

顺序表 ：顺序表是在计算机中以数组的形式保存的线性表

• 结构
  1. 除了头尾，其他的元素依次首尾相连
  2. 在内存中是一块连续的存储空间，每个元素占用相同的空间，所以顺序表支持随机访问
  3. e[i]=e[1]+e[i-1]*length, 1<=i<=n,length是单个元素所占的空间
• Java数组
  1. Java在定义数组的时候，在堆里面分配一个连续的固定大小的空间，用于存放基本数据类型或者对象的引用。
  2. 顺序表支持随机存取，所以Java数组用任意下标访问元素都很快
  3. 由于顺序表必须是连续的，所以对元素的增加和删除必须移动它之后的所有元素，会很慢，所以Java数组本身并没有实现增删功能
  4. 可以用System.arrayCopy或者org.apache.commons.lang3.ArrayUtils删除数组元素

单向链表

• 结构
  1. 每个元素都有一个指向下一个元素位置的指针，当知道插入删除发生的位置时，比较高效
  2. 在内存中不是连续的，所以findKey操作需要遍历链表

双向链表

• 结构
  1. 对比单向链表，除了有next之外，还有prev

栈Stack

• 结构
  1. 先进后出，从顶部插入或者删除
  2. 链表实现或者数组实现，后者更常见

队列Queue

• 结构
  1. 先进先出的，从尾部入队，从头部出对
  2. 链表实现，数组实现，循环数组实现
• 应用
  1. 每一个实际生活中的排队都可以是一个队列

树

将每个节点的儿子放在树节点的链表中

二叉树 ： 只有两个子节点，可以直接链接到他们

• 表达式树

二叉查找树

• 结构
  1. left小于节点，right大于节点
  2. 节点实现Comparable
  3. 重复元可通过节点计数实现
• 方法
  1. contains/findMin/findMax/search ： 快！
  2. insert
  3. 删除比较麻烦,也可以通过惰性删除的策略减少这种麻烦

AVL树 ： 平衡二叉查找树

• 结构
  1. 每个节点的左子树和右子树的高度最多差1
  2. 理想平衡树的高度 = log2(N-1)-1,如果高度为40，就有1万亿个节点
  3. AVL树的高度 = 1.44*log2(N+2)-1.328,所以AVL树高度不会差太多但是实现会方便很多
• 方法
  1. balance: 通过单旋转或者双旋转来满足插入后AVL的平衡条件
  2. insert之后需要需要balance平衡

Java 集合类

集合关系图： http://www.jianshu.com/p/4345069ada16

AbstractCollection

• contains(Object o)
• containsAll(Collection<?> c)
• addAll(Collection<? extends E> c)
• remove(Object o)
• removeAll(Collection<?> c)
• retainAll(Collection<?> c)
• toArray()
• toString()
• 以上所有的实现的方法原理都是基于Iterator遍历操作

AbstractList : extends AbstractCollection, implate

• 实现了iterator()方法
  1. 维护了一个光标，next()会移动光标, next()调用实现类各自的get(int index)方法
  2. remove()会删除next()返回的元素，remove()调用实现类各自的remove(int index)方法
  3. 在remove()后的任何对此集合操作都会使得遍历器不合法,每调用一次remove()之前必须调用一次next()
• 实现了listIterator方法
  1. 相比iterator()多了previouse相关操作
  2. 多了add(E e)/set(E e)

ArrayList : extends AbstractList implements RandomAccess

• 特点
  1. 通过动态数组实现，也就是顺序表
  2. 非线程安全
  3. 有序
  4. 支持随机访问，删除慢
• 方法
  1. get(int index)/set(int index, E e)方法速度快
  2. add(E e)方法在数组未满之前很快，如果数组已满，自动扩大1.5倍,jdk1.6初始大小为10,jdk1.7以后初始大小为0，使用的时候变为10，节约内存
  3. trimToSize()方法可以去除未使用的数组节点，节省内存空间
  4. remove(Object o)/remove(int i)/add(int index, E e)方法通过System.arrayCopy方法移动它之后的元素，速度会比较慢，但是比遍历集合快很多
• 使用场景
  1. ArrayList适合单线程操作，不适合有很多remove操作的方法
• 排序
• 去重

Vector

• Vector与ArrayList的区别是Vector是线程安全的,在多线程的情况下考虑使用Vector

Stack

• 特点
  1. Java对栈的数组实现
  2. 继承自Vector，线程安全，由于用有Vector随机写入和删除能力，所以Stack并不是一个纯粹的栈，另一种stack实现参照ArrayDeque
  3. 速度快
• 方法
  1. peek/push/pop 查询，加入或删除顶部
  2. search(Object o)查询元素位置
• 使用场景
  1. 以后查看本书

LinkedList

• 特点
  1. jdk1.6通过循环双向链表实现,jdk1.6有header,header不占用集合元素,header和集合元素组成循环双向链表。jdk1.7+用的是双向链表实现。
  2. 非线程安全
  3. 有序
  4. 不支持随机访问，删除慢,添加快，已知位置的删除块
• 方法
  1. get(int index)/set(int index, E e)方法从头或者从尾开始遍历到index节点，使用迭代器进行遍历的get/set会快很多
  2. add(E e)/addLast(E e)方法添加到集合尾部，addFirst(E e)方法添加到集合头部，速度快
  3. getFirst()和getLast()同样很快
  4. remove(Object o)需要从头遍历找到元素，然后删除/remove(int index)和get(int index)一样,使用迭代器进行删除会很快
  5. removeFirst/removeLast/remove()和getFirst()/getLast()一样
• 使用场景
  1. 在元素位置已知的情况下删除操作会快
  2. 在随机get和随机remove[remove(int index)/remove(Object o)]的情况下速度非常慢，避免使用
  3. 在大量add操作和只需要用迭代器进行遍历(get/remove)的时候使用

原文：https://www.cnblogs.com/judesheng/p/10622417.html