linearlist和linkedlist的区别 待整理

线性表在内存中是一块连续的存储空间;如:一个表中的内容是:【1,2,3】则它在内存中可能是如下存储的:1 2 3

优点:查找
      通过这个结构可以看出,只要知道了第一个元素在内存中所在的位置。就可以很容易的知道其他元素的位置。因为每一个元素占的空间是一样的。所以,
如果我们知道第一个元素:1在内存号:1000;而每一个元素占8个内存空间;
             则第二个元素:2所在的内存空间为:1000 + 8;
             依此类推。
总结:在线性表中访问数据元素是很快的。
 
缺点:添加、删除
它的缺点也正因为它是连续的一块内存空间。所以,如果往中间添加或在中间删除一个元素。都要移动其他的元素。
如:我在最前面加入一个元素:0.则 1,2,3都要往后移一位;或,我将1删除,则2,3都要往前移一位;
 
     估算一下运算时间:
在第一个元素处添加,要移动所有的元素。花费的时间是添加元素的时间(a) + 加上移动其他元素的时间(b).
在最后面加元素不需要移动任何元素。时间仅为添加元素的时间(a).
所以添加元素要的平均时间是 (b + 2a)/2;
删除操作和添加操作是一样的;
所以,当改变线性表长度的时间,它会在移动元素上花费大量的时间
总结:往中间添加或在中间删除元素时,都会涉及到大量的元素移动,改变线性表长度时也会涉及到大量元素的移动
 
在JAVA中。线性表的最直接应用就是数组:Array;但Array在初始化的时间必须规定其元素长度。
如:int[] arr = new int[5];必须规定其长度,但内容可以不填。它要知道长度,然后去开辟一块内存空间。一旦数组初始化,它就不能往里面添加,删除元素了。但可以将元素值设为空;
如果需要扩充数组长度,JAVA 提供了另一个类:ArrayList.
JAVA中所有的虚拟出来的数据容器都继承自接口:Collection;ArrayList继承自:List.而List又继承了 Collection;Collection提供了几种基本方 法:add();clear();remove();size();toArray();iterator()等;
ArrayList提供了较灵活的用法:
List<Long> lists = new ArrayList<Long>();
ArrayList<Long> lists = new ArrayList<Long>();
上面的用法使用了泛型。而且lists并未规定长度。它可以在程序中*扩充。但这一特点就意味着它可能在运行时因为将内存耗尽而出现问题;数组是规定长度的,所以如果内存不足,你根本初始化不了,一旦初始化了就可以随便用。
ArrayList,和Array都是数据结构中线性表的实现。
 
 
 
链表:
链表的存储是链式的,它不强迫数据是在一片连续的内存空间;它可以是分散存储的。所以,它的每个元素除了包括元素的值外,还要包括一些额外的信息;如:它的下一个元素在什么地方。
最基本的链式存储中的元素包括两部分:元素值和下个元素的位置;
可以如下理解:
内存空间:     值      下一元素空间
50              46           空
 .
100            10          200
 .
 .
200            16           50
当存在这个链的时候,我们肯定知道链头在哪,我们假设上面链头在内存空间100处。则上述的链表表示的数据形式是:[10,16,46];知道了链头在哪里,如果要查找其他元素。必须从链头开始,依次查找下一内存空间里的值;所以查找用的时间为N/2;显然就比线性表慢了。如果是删除或添加元 素。例,现在要将:[10,16,46]改成:[10,16,30,46];我们要做的是,将30放在内存中,假设它的内存地址是500;然后再将16这个值的下一元素空间的值改成500;并将30这一数值对应的下一元素空间值改成50(46这个值对应的内存空间);看起来要比线性表简单。但细看会发现: 要添加或删除一个元素,必须知道它的上一个元素是谁;但现在数据中存储的只有某一无线的下一个元素。如果要找上一个元素,则又要从链头开始遍历。这会浪费 大量时间,还不如线性表好用。所以这时候出现了另一链表:双链表.它和基本链表不同的是,每个元素里不但存储了下一个元素的空间,还存储了上一个元素的空间。
JAVA 中对链表的实现是通过类:LinkedList 来实现的。LinkedList 最终也是上溯到了Collection接口;
所以它也有上面说的诸如:add().clear()等方法。
 
 
参考:http://www.cnblogs.com/tianguook/archive/2012/02/14/2350845.html
上一篇:100个直接可以拿来用的JavaScript实用功能代码片段


下一篇:常用HTML转义字符,html转义符,JavaScript转义符,html转义字符表,HTML语言特殊字符对照表(ISO Latin-1字符集)