在大二我們學校的計算機大賽中，出了一道題目：要求證明對于數組和鏈表進行500次隨機訪問，比較他們的運行時間。這道題目對于我們程序員來說，可能潛在的答案是鏈表肯定是快的，但是結果呢？

其實數組在計算機中的存儲是一塊連續的內存，通過索引訪問；而鏈表則是不連續的存儲單元，通過指針關聯，這個基本知識大家都明白，數組中執行插入操作時，將插入點之后的元素依次后移一位，然后將新元素插入到騰出的位置。而進行刪除操作時則是將指定位置的元素刪掉，之后的元素依次前移一位，這看起來是是一個比較繁瑣的過程，而對于練筆哦啊，處理方式就很簡單了，需要在某個節點之后插入節點的時候，只需要將新節點的后繼指向該節點原本的后繼，再將該節點的后繼指向新節點即可，刪除節點則更為簡單，只需要讓被刪借點的前驅指向他的后繼即可。

稍微思考一下，所有人都會認為數組在這方面的效率很差，但是這份比較從根本上說來說是不公平的，無論是鏈表還是數組，插入和刪除都要兩個步驟，查找位置，和插入刪除，我們只關注了后者，那查找的實踐卻沒有計算在內，對于數組來說查找位置就是查找索引的位置，這在計算機的計算中可以忽略不計，而鏈表只要找到了位置，插入和刪除也就差不多完成了，所以二者的側重點有所不同。下面用代碼證明一下進行隨意10000次訪問二者所花費的時間：

package com.heima.jianjian;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;


public class TimeTest
{
public static void main(String[] args)
{
long[] timeBegin = new long[2];// 記錄開始時間
long[] timeEnd = new long[2];
Integer[] ia = new Integer[5000];
for (int i = 0; i < 5000; i++)
{
ia[i] = i;
}
int tempi;
Random r = new Random();
// 對ArrayList數組進行隨機訪問
List list = new ArrayList(Arrays.asList(ia));
timeBegin[0] = System.currentTimeMillis();
for (int i = 0; i < 10000; i++)
{
tempi = (Integer) list.get(r.nextInt(5000));


}
timeEnd[0] = System.currentTimeMillis();
// 對LinkedList進行隨機訪問


list = new LinkedList(Arrays.asList(ia));
timeBegin[1] = System.currentTimeMillis();
for (int i = 0; i < 10000; i++)
{
tempi = (Integer) list.get(r.nextInt(5000));


}
timeEnd[1] = System.currentTimeMillis();

System.out.println(timeEnd[0] - timeBegin[0]);
System.out.println(timeEnd[1] - timeBegin[1]);



}
}

輸出的結果分別是：5 和51毫秒 ；

可以明確的看出數組在隨機訪問執行上比鏈表快了將近十倍！

總結

以上是生活随笔為你收集整理的颠覆：链表在删除和插入的效率一定优于数组吗？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。