Java核心数据结构总结

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性能要好，因为数组是连续的，在末尾增加元素，只有在空间不足时才会进行数组扩容，大部分情况下追加操作效率还是比较高的。

更多详情见请继续阅读下一页的精彩内容：