`
沈冠军
  • 浏览: 109882 次
  • 性别: Icon_minigender_1
  • 来自: 玉林
社区版块
存档分类
最新评论

数组与链表到底有啥区别?

阅读更多

数组与链表的区别:

数组就像身上编了号站成一排的人,要找第10个人很容易,根据人身上的编号很快就能找到。但插入、删除慢,要望某个位置插入或删除一个人时,后面的人身上的编号都要变。

链表就像手牵着手站成一圈的人,要找第10个人不容易,必须从第一个人一个个数过去。但插入、删除快。插入时只要解开两个人的手,并重新牵上新加进来的人的手就可以。删除一样的道理

1.从逻辑结构来看

可以用数组处理一组数据类型相同的数据,但不允许动态定义数组的大小,即在使用数组之前必须确定数组的大小。而在实际应用中,用户使用数组之前有时无法准确确定数组的大小,只能将数组定义成足够大小,这样数组中有些空间可能不被使用,从而造成内存空间的浪费。

数组必须事先定义固定的长度(元素个数),不能适应数据动态地增减的情况。当数据增加时,可能超出原先定义的元素个数,造成数组越界;当数据减少时,造成内存浪费。

 

链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项。因为数组中插入、删除数据项时,需要移动其它数据项,而链表的插入与删除时,只需要改变个别元素之间的关系即可,这大大提高了链表的删除与插入的速度。

链表是一种常见的数据组织形式,它采用动态分配内存的形式实现。需要时可以用new分配内存空间,不需要时用delete将已分配的空间释放,不会造成内存空间的浪费。而它们之间的区别可以从两个方面来分析

 

2.从内存存储来看

数组从栈中分配空间, 对于程序员方便快速,但是自由度小

链表从堆中分配空间, 自由度大但是申请管理比较麻烦.

Java中体统自带的动态数组与链表

         ArrayListLinkedList,这是Java中的动态数组和链表。动态数组其实比较简单,就是一个长度可以根据实际情况改变的数组。我们如果要查找某一个动态数组中的元素,可以通过get()方法来查找,只要知道该元素下标就可以了。
       
LinkedList,也就是链表,这个与我们所知道的一般链表稍有不同。一般的链表元素中,除了放这个结点的数据外,还指向下一个结点。一个指向下一个,就这样构成了链表。但是Java中的链表,除了放本来的数据和指向下一个结点外,还指向上一个结点。因此,Java中的LinkedList是双向的。那么有什么用呢?还有就是ArrayListLinkedList有什么区别?
       
这个就要从查找元素的效率和添加删除元素的效率来讲了。在动态数组中,如果我们要在某一个位置添加或者删除一个元素,剩下的每个元素都要相应地往前或往后移动。如果该动态数组中的元素很多,那么,每当我们添加或删除一个元素后,需要移动的元素就非常多,因此,效率就比较低。但是,如果我们使用LinkedList就不一样了。如果我们要在某一个位置添加一个元素,例如,要在A, C之间插入B。本来A是指向CC也指向A的。现在,只需要将B放到AC之间,同时让B向前指向A,向后指向C,并且让AC指向B,让CA指向B就可以了。如果该链表中元素非常多,我们只需做这个操作就可以了,并不需要移动剩下的元素。所以说LinkedList在添加和删除元素上的效率要比ArrayList高很多。而且,Java中有一个叫ListIterator的迭代器。该迭代器不仅可以向后迭代元素,还能向前迭代,而且还有add()来在某一位置添加元素,十分方便。不过说到查找效率的话就反过来了,是ArrayList的效率比LinkedList的效率高,因为你只要提供元素的下标即可。如果你不知道如何选择ArrayListLinkedList,就从这两个方面来考虑就行了。

     其实数组与链表无所谓谁更具有优势,这得要具体情况,所要实现的功能不同,它们所表现出来的优势就不一样,正所谓各有各的好处,只有知道了它们的特性,才能更好的利用它们···

分享到:
评论
1 楼 freewxy 2010-10-04  
“数组从栈中分配空间, 对于程序员方便快速,但是自由度小
链表从堆中分配空间, 自由度大但是申请管理比较麻烦.”能给解释一下不?--wxy

相关推荐

Global site tag (gtag.js) - Google Analytics