在学习数据结构的过程中,了解到:
顺序存储:插入和删除的平均耗时(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 !
差距太大了……,终于知道顺序存储与链式存储之间的差距了。
分享到:
相关推荐
前面上传了线性表的顺序存储和链式存储,是为了方便学习数据结构的(喜欢用c语言描述版本)的朋友,现在把栈的顺序存储和链式存储上传,希望为同学们提供一个系统的学习数据结构的地方。
参考资料:《数据结构》(C语言版)严蔚敏&&吴伟民&&米宁著 要求选用顺序存储结构和二叉链表存储结构实现抽象数据类型二叉树的基本操作。有个亮点是利用字符在dos界面显示二叉树的结构形态。 里面包含了完整的源程序和...
数据结构线性表操作的一个实验: 实验要求 顺序和链式存储的线性表的创建、获取元素、插入和删除元素等基本操作的实现。 题目要求: 输入:一组整型数据A,一组...要求:A和B使用两种存储方式:顺序存储和链式存储。
用C实现,数据结构线性表的顺序和链式实现.
该文档饱含了数据结构课程中关于线性表的十二个基本操作的实现。对于不同的线性表的存储结构,利用C语言分别实现相应的算法
数据结构实验报告(1) 学院: 专业: 班级: "姓名 " "学号 " "实验组" " "实验时间 "2011-10-28 "指导教师" "成绩 " " "实验项目名称 "线性表的顺序存储结构 " "实 "1. 熟练掌握线性表的基本操作在顺序存储和链式...
栈-队列的顺序-链式储存结构(数据结构试验报告).pdf
中国大学MOOC上浙大的《数据结构》课程队列顺序存储&链式存储实现的代码。包括队列创建、入队、出队。
数据结构-基本算法-顺序栈(学生时代源码,调试可运行)
抽奖游戏: n个人围成一圈,由第一个人开始,依次报数,数到第m人,便抽出来作为中奖人,然后从他的下一个人数起,数到第m人,再抽出来作为中奖人,如此循环,直到抽出k个为止。问哪些人中奖了。...
使用c实现数据结构中的顺序表(链式存储): 功能: 1、头节点的创建 2、判断链表是否是 空\满 3、计算链表节点个数 4、插入节点(按 下标\元素) 5、删除节点(按 下标\元素) 6、按元素查询下标 7、打印链表 8、...
实验 二 基于链式存储结构 实现线性表的基本的 常见的运算 提示: ⑴ 提供一个实现功能的演示系统 ⑵ 具体物理结构和数据元素类型自行选定 ⑶ 线性表数据可以使用磁盘文件永久保存
学院: 专业: 班级: "姓名 " "学号 " "实验组" " "实验时间 "2011-11-11 "指导教师" "成绩 " " "实验项目名称"线性表的链式存储结构 " "实"了解和掌握线性表的逻辑结构和链式存储结构,掌握单链表的基本算法" "验...
C语言中栈的顺序存储和链式存储
掌握线性表的基本操作:建表、插入、删除、输出等运算在顺序存储结构和链式存储结 构上的实现; 3. 通过本次实习加深对高级语言C语言的使用(特别是函数参数、指针类型、链表的使用) 。熟悉线性表的基本运算在两种...
算法与数据结构(一)线性表的顺序存储与链式存储(Swift版) 定义线性表节点的结构.pdf
第三章 栈和队列 顺序存储结构和链式存储结构
数据结构与算法(C语言)线性表(顺序存储、链式存储) 定义线性表节点的结构.pdf
数据结构_线性表的链式存储 实验目的 1. 掌握线性表的链式存储结构。 2. 能熟练地利用链式存储结构实现线性表的基本操作。 3. 能熟练地掌握链式存储结构中算法的实现。 实验内容 1. 分别用头插法和尾插法建立带头...
数据结构实验带源码,包括顺序表、链表、栈和队列的顺序存储和链式存储、串和数组、图、数、查找和排序。数据结构实验带源码,包括顺序表、链表、栈和队列的顺序存储和链式存储、串和数组、图、数、查找和排序。数据...