链表与数组

2018-12-03  本文已影响0人  Itsmely队长

数组和链表是两种基本的数据结构,他们在内存存储上的表现不一样,所以也有各自的特点。

大致总结一下特点和区别,拿几个人一起去看电影时坐座位为例。

数组:

1、在内存中,数组是一块连续的区域。 拿上面的看电影来说,这几个人在电影院必须坐在一起。
2、数组需要预留空间,在使用前要先申请占内存的大小,可能会浪费内存空间。 比如看电影时,为了保证10个人能坐在一起,必须提前订好10个连续的位置。这样的好处就是能保证10个人可以在一起。但是这样的缺点是,如果来的人不够10个,那么剩下的位置就浪费了。如果临时有多来了个人,那么10个就不够用了,这时可能需要将第11个位置上的人挪走,或者是他们11个人重新去找一个11连坐的位置,效率都很低。如果没有找到符合要求的作为,那么就没法坐了。
3、插入数据和删除数据效率低,插入数据时,这个位置后面的数据在内存中都要向后移。删除数据时,这个数据后面的数据都要往前移动。 比如原来去了5个人,然后后来又去了一个人要坐在第三个位置上,那么第三个到第五个都要往后移动一个位子,将第三个位置留给新来的人。 当这个人走了的时候,因为他们要连在一起的,所以他后面几个人要往前移动一个位置,把这个空位补上。
4、随机读取效率很高。因为数组是连续的,知道每一个数据的内存地址,可以直接找到给地址的数据。
5、不利于扩展,数组定义的空间不够时要重新定义数组。

链表:

1、在内存中可以存在任何地方,不要求连续。 在电影院几个人可以随便坐。
2、每一个数据都保存了下一个数据的内存地址,通过这个地址找到下一个数据。 第一个人知道第二个人的座位号,第二个人知道第三个人的座位号……
3、增加数据和删除数据很容易。 再来个人可以随便坐,比如来了个人要做到第三个位置,那他只需要把自己的位置告诉第二个人,然后问第二个人拿到原来第三个人的位置就行了。其他人都不用动。
4、查找数据时效率低,因为不具有随机访问性,所以访问某个位置的数据都要从第一个数据开始访问,然后根据第一个数据保存的下一个数据的地址找到第二个数据,以此类推。 要找到第三个人,必须从第一个人开始问起。
5、不指定大小,扩展方便。链表大小不用定义,数据随意增删。

各自的优缺点

数组的优点

1、随机访问性强
2、查找速度快

数组的缺点

1、插入和删除效率低
2、可能浪费内存
3、内存空间要求高,必须有足够的连续内存空间。
4、数组大小固定,不能动态拓展

链表的优点

1、插入删除速度快
2、内存利用率高,不会浪费内存
3、大小没有固定,拓展很灵活。

链表的缺点

1、不能随机查找,必须从第一个开始遍历,查找效率低。

操作 数组 链表
读取 O(1) O(n)
插入 O(n) O(1)
删除 O(n) O(1)
上一篇 下一篇

猜你喜欢

热点阅读