數據結構:用實例分析ArrayList與LinkedList的讀寫性能_包裝設計

作者:

※南投搬家公司費用需注意的眉眉角角，別等搬了再說!

上新台中搬家公司提供您一套專業有效率且人性化的辦公室搬遷、公司行號搬家及工廠遷廠的搬家服務

目錄

  • 背景
  • ArrayList
  • LinkedList
  • 實例分析
    • 1、增加數據
    • 2、插入數據
    • 3、遍曆數據
      • 3.1、LinkedList遍歷改進
  • 總結

背景

ArrayList與LinkedList是Java編程中經常會用到的兩種基本數據結構，在書本上一般會說明以下兩個特點：

  • 對於需要快速隨機訪問元素，應該使用ArrayList。
  • 對於需要快速插入，刪除元素，應該使用LinkedList。

該文通過實際的例子分析這兩種數據的讀寫性能。

ArrayList

ArrayList是實現了基於動態數組的數據結構：

private static final int DEFAULT_CAPACITY = 10;
...
transient Object[] elementData;
...
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

LinkedList

LinkedList是基於鏈表的數據結構。

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
...    
transient Node<E> first;
transient Node<E> last;
...
private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

實例分析

  • 通過對兩個數據結構分別增加、插入、遍歷進行讀寫性能分析
1、增加數據
public class ArrayListAndLinkList {
    public final static int COUNT=100000;
    public static void main(String[] args) {

        // ArrayList插入
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
        Long start = System.currentTimeMillis();
        System.out.println("ArrayList插入開始時間：" + sdf.format(start));

        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < COUNT; i++) {
            arrayList.add(i);
        }

        Long end = System.currentTimeMillis();
        System.out.println("ArrayList插入結束時間：" + sdf.format(end));
        System.out.println("ArrayList插入" + (end - start) + "毫秒");


        // LinkedList插入
        start = System.currentTimeMillis();
        System.out.println("LinkedList插入開始時間：" + sdf.format(start));
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < COUNT; i++) {
            linkedList.add(i);
        }
        end = System.currentTimeMillis();
        System.out.println("LinkedList插入結束時間：" + sdf.format(end));
        System.out.println("LinkedList插入結束時間" + (end - start) + "毫秒");
     }
}

輸出如下：
兩者寫入的性能相差不大！

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

網動廣告出品的網頁設計，採用精簡與質感的CSS語法，提升企業的專業形象與簡約舒適的瀏覽體驗，讓瀏覽者第一眼就愛上她。

2、插入數據

在原有增加的數據上，在index:100的位置上再插入10萬條數據。

public class ArrayListAndLinkList {
    public final static int COUNT=100000;
    public static void main(String[] args) {

        // ArrayList插入
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
        Long start = System.currentTimeMillis();
        System.out.println("ArrayList插入開始時間：" + sdf.format(start));

        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < COUNT; i++) {
            arrayList.add(i);
        }
        for (int i = 0; i < COUNT; i++) {
            arrayList.add(100,i);
        }

        Long end = System.currentTimeMillis();
        System.out.println("ArrayList插入結束時間：" + sdf.format(end));
        System.out.println("ArrayList插入" + (end - start) + "毫秒");


        // LinkedList插入
        start = System.currentTimeMillis();
        System.out.println("LinkedList插入開始時間：" + sdf.format(start));
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < COUNT; i++) {
            linkedList.add(i);
        }
        for (int i = 0; i < COUNT; i++) {
            linkedList.add(100,i);
        }
        end = System.currentTimeMillis();
        System.out.println("LinkedList插入結束時間：" + sdf.format(end));
        System.out.println("LinkedList插入結束時間" + (end - start) + "毫秒");
     }
}

輸出如下：
ArrayList的性能明顯比LinkedList的性能差了很多。

看下原因：
ArrayList的插入源碼：

  public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

ArrayList的插入原理：在index位置上插入后，在index後續的數據上需要做逐一複製。

LinkedList的插入源碼：

public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
 }
 ...
  void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

LinkedList的插入原理：在原來相互鏈接的兩個節點（Node）斷開，把新的結點插入到這兩個節點中間，根本不存在複製這個過程。

3、遍曆數據

在增加和插入的基礎上，利用get方法進行遍歷。

public class ArrayListAndLinkList {
    public final static int COUNT=100000;
    public static void main(String[] args) {

        // ArrayList插入
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
        Long start = System.currentTimeMillis();
        System.out.println("ArrayList插入開始時間：" + sdf.format(start));

        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < COUNT; i++) {
            arrayList.add(i);
        }
        for (int i = 0; i < COUNT; i++) {
            arrayList.add(100,i);
        }

        Long end = System.currentTimeMillis();
        System.out.println("ArrayList插入結束時間：" + sdf.format(end));
        System.out.println("ArrayList插入" + (end - start) + "毫秒");


        // LinkedList插入
        start = System.currentTimeMillis();
        System.out.println("LinkedList插入開始時間：" + sdf.format(start));
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < COUNT; i++) {
            linkedList.add(i);
        }
        for (int i = 0; i < COUNT; i++) {
            linkedList.add(100,i);
        }
        end = System.currentTimeMillis();
        System.out.println("LinkedList插入結束時間：" + sdf.format(end));
        System.out.println("LinkedList插入結束時間" + (end - start) + "毫秒");

        // ArrayList遍歷
        start = System.currentTimeMillis();
        System.out.println("ArrayList遍歷開始時間：" + sdf.format(start));
        for (int i = 0; i < 2*COUNT; i++) {
            arrayList.get(i);
        }
        end = System.currentTimeMillis();
        System.out.println("ArrayList遍歷開始時間：" + sdf.format(end));
        System.out.println("ArrayList遍歷開始時間" + (end - start) + "毫秒");

        // LinkedList遍歷
        start = System.currentTimeMillis();
        System.out.println("LinkedList遍歷開始時間：" + sdf.format(start));
        for (int i = 0; i < 2*COUNT; i++) {
            linkedList.get(i);
        }
        end = System.currentTimeMillis();
        System.out.println("LinkedList遍歷開始時間：" + sdf.format(end));
        System.out.println("LinkedList遍歷開始時間" + (end - start) + "毫秒");

    }
}

輸出如下：

兩者的差異巨大：
我們看一下LInkedList的get方法：從頭遍歷或從尾部遍歷結點

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
 ...
 Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
3.1、LinkedList遍歷改進

我們採用迭代器對LinkedList的遍歷進行改進：

		...
		// LinkedList遍歷
        start = System.currentTimeMillis();
        System.out.println("LinkedList遍歷開始時間：" + sdf.format(start));
        Iterator<Integer> iterator = linkedList.iterator();
        while(iterator.hasNext()){
            iterator.next();
        }
        end = System.currentTimeMillis();
        System.out.println("LinkedList遍歷開始時間：" + sdf.format(end));
        System.out.println("LinkedList遍歷開始時間" + (end - start) + "毫秒");

再看下結果：
兩者的遍歷性能接近。

總結

  • List使用首選ArrayList。對於個別插入刪除非常多的可以使用LinkedList。
  • LinkedList，遍歷建議使用Iterator迭代器，尤其是數據量較大時LinkedList避免使用get遍歷。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

※產品缺大量曝光嗎?你需要的是一流包裝設計!

窩窩觸角包含自媒體、自有平台及其他國家營銷業務等，多角化經營並具有國際觀的永續理念。