Java核心数据结构总结

JDK提供了一组主要的数据结构的实现，如List、Set、Map等常用结构，这些结构都继承自java.util.collection接口。List接口List有三种不同的实现，ArrayList和Vector使用数组实现，其封装了对内部数组的操作。LinkedList使用了循环双向链表的数据结构，LinkedList链表是由一系列的链表项连接而成，一个链表项包括三部分：链表内容、前驱表项和后驱表项。LinkedList的表项结构如图：LinkedList表项间的连接关系如图：可以看出，无论LinkedList是否为空，链表都有一个header表项，它即表示链表的开头也表示链表的结尾。表项header的后驱表项便是链表的第一个元素，其前驱表项就是链表的最后一个元素。对基于链表和基于数组的两种List的不同实现做一些比较：1、增加元素到列表的末尾：在ArrayList中源代码如下：public boolean add（E e） {
ensureCapacityInternal（size + 1）; // Increments modCount！！
elementData[size++] = e;
return true;
}add（）方法性能的好坏取决于grow（）方法的性能：private void grow（int minCapacity） {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + （oldCapacity >> 1）;
if （newCapacity - minCapacity < 0）
newCapacity = minCapacity;
if （newCapacity - MAX_ARRAY_SIZE > 0）
newCapacity = hugeCapacity（minCapacity）;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf（elementData, newCapacity）;
}可以看出，当ArrayList对容量的需求超过当前数组的大小是，会进行数组扩容，扩容的过程中需要大量的数组复制，数组复制调用System.arraycopy（）方法，操作效率是非常快的。在LinkedList源码中add（）方法：public boolean add（E e） {
linkLast（e）;
return true;
} linkLast（）方法如下：void linkLast（E e） {
final Node<E> l = last;
final Node<E> newNode = new Node<>（l, e, null）;
last = newNode;
if （l == null）
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}LinkedList是基于链表实现，因此不需要维护容量大小，但是每次都新增元素都要新建一个Node对象，并进行一系列赋值，在频繁系统调用中，对系统性能有一定影响。性能测试得出，在列表末尾增加元素，ArrayList比LinkedList性能要好，因为数组是连续的，在末尾增加元素，只有在空间不足时才会进行数组扩容，大部分情况下追加操作效率还是比较高的。更多详情见请继续阅读下一页的精彩内容： http://www.linuxidc.com/Linux/2016-03/129625p2.htm