数组的优点:
数组的缺点:
链表的优点:
链表在物理上是动态地分配储存空间,不要求连续性,但是要求逻辑上的连续。它需要存储每个元素在内存中的地址,以及它相邻元素的地址,然后像链条一样把各元素链起来,保证了在逻辑上的连续性。
比如:
单链表,每个元素除了存储本身的值外,还存储了前驱的引用,也就是存储了前驱所在的内存地址信息。
双链表就是不仅存储了前驱的引用还存储了后继的引用.
增加元素的时候,只需给增加元素添加其前元素或后元素的地址;删除元素的时候,修改目标元素前驱和后驱的首位连接地址. 故此为增删快。
链表的缺点:
内存中的存储形式可以分为连续存储和离散存储两种。因此,数据的物理存储结构就有连续存储和离散存储两种,它们对应了我们通常所说的数组和链表。
因为数组是连续存储的,在操作数组中的数据时就可以根据离首地址的偏移量直接存取相应位置上的数据,但是如果要在数据组中任意位置上插入一个元素,就需要先把后面的元素集体向后移一位为其空出存储空间。
与之相反,链表是离散存储的,所以在插入一个数据时只要申请一片新空间,然后将其中的连接关系做一个修改就可以,但是显然在链表上查找一个数据时就要逐个遍历了。
考虑以上的总结可见,数组和链表各有优缺点。在具体使用时要根据具体情况选择。当查找数据操作比较多时最好用数组;当对数据集中的数据进行添加或删除比较多时最好选择链表。
数组就像身上编了号站成一排的人,要找第10个人很容易,根据人身上的编号很快就能找到。但插入、删除慢,要望某个位置插入或删除一个人时,后面的人身上的编号都要变。当然,加入或删除的人始终末尾的也快
链表就像手牵着手站成一圈的人,要找第10个人不容易,必须从第一个人一个个数过去。但插入、删除快。插入时只要解开两个人的手,并重新牵上新加进来的人的手就可以。删除一样的道理。
总结:
数组静态分配内存,链表动态分配内存;
数组在内存中连续,链表不连续;
数组元素在栈区,链表元素在堆区;
数组利用下标定位,时间复杂度为o(1),链表定位元素时间复杂度o(n);
数组插入或删除元素的时间复杂度o(n),链表的时间复杂度o(1);
如对本文有疑问, 点击进行留言回复!!
网友评论