歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

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

Copyright © Linux教程網 All Rights Reserved