weixin_44877226
L'herbe
2020-11-11 23:23
采纳率: 38.9%
浏览 35
已采纳

数组与链表结构的优缺点

大佬详细讲一下,数组与链表结构的优缺点,谢谢了

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • u012039040
    一头小山猪 2020-11-18 20:05
    已采纳

    在比较两种数据结构优缺点的时候一般看存取方式和使用效率,目前在很多语言都可以直接使用数组和链表结构,所以代码实现的部分就直接略过了,先重点来说明一下结构的特点。

    数组:在初始化以后长度固定,是一整块连续的空间,说白了就是存储元素的地址是连续的,所以我们只要知道首个元素的位置,就可以顺次知道其他元素的存储地址,这就很适合使用索引下标的方式来操作。

    链表:链表是顺序表的一种,以链式的方式来进行存储,所以在每个节点中除了要保存集合元素外,还要存储下一个链表元素的位置信息或终止标识。(双向链表等可能需要存储更多信息)对于链表结构来说,增加或减少元素的个数都是很容易的,只需要节点之间的指向信息就可以了。

    在实际的使用中,由于很多语言都已经对结构进行了封装,使用起来很方便,而且调用的方法也没多大却别,如:ArrayList,LinkedList。所以需要重点关注的就是使用效率,在各种场景下如何选择。对于数据量比较小的场景,千条或者万条数据时这种差异是微乎其微的。

    对于集合的操作,主要是元素取用,插入,删除,替换。对于数组来说,由于本身结构的限制,如果删除或添加某一元素,必须重新构建一个数组,并将其他元素进行串位,才能保证结构的完备性,在使用时一定要注意这一点。所以可以看出,如果我们使用数组结构,涉及到元素的更新(插入、删除)时效率是很低的,但是由于存储连续,根据位置快速定位一个元素是很容易的。所以数组更适合元素的按位提取,不适合大量元素的增删。

    对于链表结构,特点刚好和数组相反,如果想在任何一个位置插入或删除一个元素,都只要修改节点中指向信息就可以了。加入目前链表中有a、c、d三个元素,a节点中存储了c元素的位置,c节点中存储了d节点的位置。如果想要在a与c中插入一个b元素,只需要构建一个元素内容为b的节点,然后将a指向b,b指向c就可以,删除也是同样修改指向。但是在进行元素查找时,由于元素存储位置并不是连续的,存储在每一个节点中,在按位置取出元素的时候需要逐个找下去。所以链表更适合元素的增删,不适合元素的按位提取。

    点赞 评论

相关推荐