※南投搬家公司費用需注意的眉眉角角，別等搬了再說!
上新台中搬家公司提供您一套專業有效率且人性化的辦公室搬遷、公司行號搬家及工廠遷廠的搬家服務
目錄
- 背景
- 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遍歷。
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
※產品缺大量曝光嗎?你需要的是一流包裝設計!
窩窩觸角包含自媒體、自有平台及其他國家營銷業務等，多角化經營並具有國際觀的永續理念。