数据结构学习-顺序存储跟链式存储

数据结构学习-顺序存储和链式存储
在学习数据结构的过程中，了解到：
顺序存储：插入和删除的平均耗时(n-1)/2，所以时间复杂度是O(n)；而查询操作的平均耗时 1，所以时间复杂度是O(1)；

链式存储：插入和删除操作：第一次操作，不知道i的位置，插入和删除操作的平均耗时(n-1)/2，给顺序存储相比没有什么优势，但是如果一次插入多条记录，那么由于知道了i的位置，后    面的插入所需要的时间就是1，那么链式存储的优势就显现出来了，所以对于插入和删除数据越频  繁的操作，链式存储的效率优势就越明显。查询操作：平均耗时(n-1)/2，所以时间复杂度是O(n)；

而Java中ArryList就是顺序存储，LinkedList就是双链式存储。

为了更直观的观察两种存储方式之间的区别，特举例进行说明：

package ArrayListVSLinkedList;import java.util.ArrayList;import java.util.Date;import java.util.LinkedList;/** * Created by IntelliJ IDEA. * User: luhba * Date: 13-7-6 * Time: 下午7:06 * To change this template use File | Settings | File Templates. */public class ArrayListVSLinkedList{     public static void ArrayListTest(long num)     {         ArrayList list = new ArrayList()  ;         long berforeTime= new Date().getTime();         for(int i=0;i<num;i++)         {             list.add(i,i);         }         long afterTime = new Date().getTime();         System.err.println("The process ArrayListTest used a total time is "+(afterTime-berforeTime) +" millisecondes !" );     }    public static void linkedList(long num)    {        LinkedList  list = new LinkedList();         long berforeTime= new Date().getTime();         for(int i=0;i<num;i++)         {             list.add(i,i);         }         long afterTime = new Date().getTime();         System.err.println("The process linkedList used a total time is "+(afterTime-berforeTime) +" millisecondes !" );    }    public static void main(String[] args)    {        ArrayListVSLinkedList.ArrayListTest(100000);        ArrayListVSLinkedList.linkedList(100000);    }}

执行的结果是：
The process ArrayListTest used a total time is 31 millisecondes !
The process linkedList used a total time is 32 millisecondes !

这个是为什么呢？顺序存储插入的速度竟然比链式存储的还要快？
答：这个例子是顺序存储的最理想的方式，不用向后移动一个element，所以速度相当。那么再举一个差别最大的例子：

package ArrayListVSLinkedList;import java.util.ArrayList;import java.util.Date;import java.util.LinkedList;/** * Created by IntelliJ IDEA. * User: luhba * Date: 13-7-6 * Time: 下午7:06 * To change this template use File | Settings | File Templates. */public class ArrayListVSLinkedList{     public static void ArrayListTest(long num)     {         ArrayList list = new ArrayList()  ;         long berforeTime= new Date().getTime();         for(int i=0;i<num;i++)         {             list.add(0,i);         }         long afterTime = new Date().getTime();         System.err.println("The process ArrayListTest used a total time is "+(afterTime-berforeTime) +" millisecondes !" );     }    public static void linkedList(long num)    {        LinkedList  list = new LinkedList();         long berforeTime= new Date().getTime();         for(int i=0;i<num;i++)         {             list.add(0,i);         }         long afterTime = new Date().getTime();         System.err.println("The process linkedList used a total time is "+(afterTime-berforeTime) +" millisecondes !" );    }    public static void main(String[] args)    {        ArrayListVSLinkedList.ArrayListTest(100000);        ArrayListVSLinkedList.linkedList(100000);    }}

执行的结果是：
The process ArrayListTest used a total time is 5468 millisecondes !
The process linkedList used a total time is 47 millisecondes !

差距太大了……，终于知道顺序存储与链式存储之间的差距了。

         

查看更多 下一篇