单链表与数组的区别

 : jank    :   : 6087    : 2018-01-04 14:18  数据结构和算法

关于单链表:

1、概念

                在单链表中由于数据元素的存储空间一般不是连续的,因此为了完善的表示单链表的逻辑结构,其中每一个数据元素必须由两部分构成:一部分是数据元素中的数据值,另一部分是数据元素的地址值。这两部分信息构成了单链表的一个节点。因此,在用单链表表示线性表时,每个结点的存储地址是任意的,即存储位置是无序的。

2、结构

                对于单链表来说,每个节点的结构都是(data,next),节点中有两个部分:data域—存放结点值的数据域,next—存放结点的直接后续的地址的链域。

 

数组与链表的区别:

1、基于空间的考虑

            数组的存储空间是静态,连续分布的,初始化的过大造成空间浪费,过小又将使空间溢出机会增多。而链表的存储空间是动态分布的,只要内存空间尚有空闲,就不会产生溢出;链表中每个节点出了数据域外,还有链域(指向下一个节点),这样空间利用率就会变高。

2、基于时间的考虑

            具体的来说 数组查询快,插入与删除慢,单链表查询慢,插入与删除快。细说的话:数组中任意节点都可以在O(1)内直接存储访问,而链表中的节点,需从头指针顺着链表扫描才能获取到;而链表任意位置进行插入和删除,都只需要修改指针,而数组中插入删除节点,平均要移动一半的节点。

 

           (静态)数组从栈中分配空间,对于程序员方便快速,但是自由度小。链表从堆中分配空间,自由度大但是申请管理比较麻烦。

              数组中的数据在内存中按顺序存储的,而链表是随机存储的!

              要访问数组中的元素可以按下标索引来访问,速度快,如果对他进行插入操作的话,就得移动很多元素,所以对数组进行插入操作效率很低!

              由于链表是随机存储的,链表在插入,删除操作上有很高的效率(相对于数组),如果要访问链表中的某个元素的话,就得从链表的头逐个遍历,直到找到所需要的元素为止,所以链表的随机访问的效率就比数组要低。


数组和链表的区别整理如下:

数组静态分配内存,链表动态分配内存;

数组在内存中连续,链表不连续;

数组元素在栈区,链表元素在堆区;

数组利用下标定位,时间复杂度为O(1),链表定位元素时间复杂度O(n);

数组插入或删除元素的时间复杂度O(n),链表的时间复杂度O(1)。


   

备案编号:赣ICP备15011386号

联系方式:qq:1150662577    邮箱:1150662577@qq.com