Java常用数据结构

Java中有几种常用的数据结构，主要分为Collection和map两个主要接口（接口只提供方法，并不提供实现），而程序中最终使用的数据结构是继承自这些接口的数据结构类。

一、几个常用类的区别
1．ArrayList: 元素单个，效率高，多用于查询
2．Vector: 元素单个，线程安全，多用于查询
3．LinkedList:元素单个，多用于插入和删除
4．HashMap: 元素成对，元素可为空
5．HashTable: 元素成对，线程安全，元素不可为空
二、Vector、ArrayList和LinkedList
大多数情况下，从性能上来说ArrayList最好，但是当集合内的元素需要频繁插入、删除时LinkedList会有比较好的表现，但是它们三个性能都比不上数组，另外Vector是线程同步的。所以：
如果能用数组的时候(元素类型固定，数组长度固定)，请尽量使用数组来代替List；
如果没有频繁的删除插入操作，又不用考虑多线程问题，优先选择ArrayList；
如果在多线程条件下使用，可以考虑Vector；
如果需要频繁地删除插入，LinkedList就有了用武之地；
如果你什么都不知道，用ArrayList没错。
三、Collections和Arrays
在Java集合类框架里有两个类叫做Collections（注意，不是Collection！）和Arrays，这是JCF里面功能强大的工具，但初学者往往会忽视。按JCF文档的说法，这两个类提供了封装器实现（Wrapper Implementations）、数据结构算法和数组相关的应用。
想必大家不会忘记上面谈到的“折半查找”、“排序”等经典算法吧，Collections类提供了丰富的静态方法帮助我们轻松完成这些在数据结构课上烦人的工作：
binarySearch：折半查找。
sort：排序，这里是一种类似于快速排序的方法，效率仍然是O(n * log n)，但却是一种稳定的排序方法。
reverse：将线性表进行逆序操作，这个可是从前数据结构的经典考题哦！
rotate：以某个元素为轴心将线性表“旋转”。
swap：交换一个线性表中两个元素的位置。
……
Collections还有一个重要功能就是“封装器”（Wrapper），它提供了一些方法可以把一个集合转换成一个特殊的集合，如下：
unmodifiableXXX：转换成只读集合，这里XXX代表六种基本集合接口：Collection、List、Map、Set、SortedMap和SortedSet。如果你对只读集合进行插入删除操作，将会抛出UnsupportedOperationException异常。
synchronizedXXX：转换成同步集合。
singleton：创建一个仅有一个元素的集合，这里singleton生成的是单元素Set，
singletonList和singletonMap分别生成单元素的List和Map。
空集：由Collections的静态属性EMPTY_SET、EMPTY_LIST和EMPTY_MAP表示。

ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步

LinkedList实现了List接口，允许null元素。此外LinkedList提供额外的get，remove，
insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），
队列（queue）或双向队列（deque）。

Vector非常类似ArrayList，但是Vector是同步的。

Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。
基本的push和pop方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，
search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

Set是一种不包含重复的元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)=false，
Set最多有一个null元素。

Hashtable继承Map接口，实现一个key-value映射的哈希表。任何非空（non-null）的对象都可作为key或者value。

HashMap和Hashtable类似，不同之处在于HashMap是非同步的，并且允许null，即null value和null key。

WeakHashMap是一种改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，
那么该key可以被GC回收。

Java 线性表

ArrayList类

使用普通的数组来存储对象太过麻烦，因为数组的一个很大的弱点就是长度从一开始就固定了，所以Java提供了另一个容器 java.util.ArrayList 集合类,让我们可以更便捷的存储和操作对象数据。

ArrayList是一个可变大小的数组。它允许存储所有元素，包括null，它是基于数组实现的List类。

ArrayList没有同步。size，isEmpty，get，set方法运行时间为常数。

该类封装了一个动态再分配的Object[]数组，每一个类对象都有一个capacity属性，表示它们所封装的Object[]数组的长度，当向ArrayList中添加元素时，该属性值会自动增加。

但是她的add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。
每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加。

如果想ArrayList中添加大量元素，可使用ensureCapacity方法一次性增加capacity，可以减少增加重分配的次数提高性能。

ArrayList类常用方法

构造方法：ArrayList()：构造一个初值为空，容量为10 的list。ArrayList(Collection<? extends E> c)：构造一个元素包含collection的list，顺序按照iterator来进行。c表示这个集合，需要用来代替原来list中的元素。ArrayList(int initialCapacity)：构造一个指定容量的空数组。使用方法：add(Object element)： 向列表的尾部添加指定的元素。size()： 返回列表中的元素个数。get(int index)： 返回列表中指定位置的元素，index从0开始。add(int index, Object element)： 在列表的指定位置插入指定元素。set(int i, Object element)： 将索引i位置元素替换为元素element并返回被替换的元素。clear()： 从列表中移除所有元素。isEmpty()： 判断列表是否包含元素，不包含元素则返回 true，否则返回false。contains(Object o)： 如果列表包含指定的元素，则返回 true。remove(int index)： 移除列表中指定位置的元素，并返回被删元素。remove(Object o)： 移除集合中第一次出现的指定元素，移除成功返回true，否则返回false。iterator()： 返回按适当顺序在列表的元素上进行迭代的迭代器。

LinkedList类

LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作，LinkedList 是非同步的。

LinkedList 实现 List 接口，能对它进行队列操作。

LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。

LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。

LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。

JDK1.6的时候是Entry结点实现的，JDK1.7开始改用Node结点实现。

LinkedList也是线性表类之一，与ArrayList相比，两者存在一些相同点和区别。

ArrayList 底层是数组结构，适合多查询，少插入删除元素。

LinkedList 底层是链表结构，适合多插入，删除元素，少查询操作。

常用方法

构造：
public LinkedList() {header.next = header.previous = header;}public LinkedList(Collection<? extends E> c) {this();addAll(c);｝常用方法：public void addFirst(Object element)：向链表表头添加一个新节点，该节点中的数据是参数element指定的对象。public void addLast(Object element)：向链表表尾添加一个新节点，该节点中的数据是参数element指定的对象。public  Object removeFirst()：删除第一个节点并返回这个节点中的对象。public  Object removeLast()：删除最后一个节点并返回这个节点中的对象。public Object remove(int index)：删除指定位置的节点。public Object get(int index)：得到指定位置的节点。public Object getFirst()：得到链表第一个节点的对象。public Object getLast()：得到链表最后一个节点的对象int indexOf(Object element) ：返回节点对象element在链表中首次出现的位置，如果链表中无此节点的对象则返回-1public int lastIndexOf(Object element)：返回节点对象element在链表中最后出现的位置，如果链表中无此节点的对象则返回-1public Object set(int index,Object element)：将当前链表index位置节点中的对象替换成参数element指定的对象，返回被替换对象public int size()：返回链表的长度即节点个数。