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

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

数组的特点

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

链表的特点

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

各自的优缺点

数组的优点

  • 随机访问性强
  • 查找速度快 ## 数组的缺点
  • 插入和删除效率低
  • 可能浪费内存
  • 内存空间要求高,必须有足够的连续内存空间。
  • 数组大小固定,不能动态拓展

链表的优点

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

链表的缺点

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

算法复杂度

数组 链表
读取 O(1)
插入 O(n)
删除 O(n)

前面说的是单向链表和静态数组,下面简单介绍一下双向链表和动态数组。

动态数组和双向链表

动态数组

  • 动态数组其实比较简单,就是一个长度可以根据实际情况改变的数组。我们如果要查找某一个动态数组中的元素,可以通过get()方法来查找,只要知道该元素下标就可以了。
  • 在动态数组中,如果我们要在某一个位置添加或者删除一个元素,剩下的每个元素都要相应地往前或往后移动。如果该动态数组中的元素很多,那么,每当我们添加或删除一个元素后,需要移动的元素就非常多,因此,效率就比较低。

双向链表

  • 双向链表存放的除了本来的数据外,还有其前驱和后驱结点。
  • 双向链表增删效率就高多了。如果我们要在某一个位置添加一个元素,例如,要在1,3之间插入5。本来1是指向3,3也指向1的。现在,只需要将5放到1和3之间,同时让5向前指向1,向后指向3,并且让1从3指向5,让3从1指向5就可以了。如果该链表中元素非常多,我们只需做这个操作就可以了,并不需要移动剩下的元素。

总结

所以,双向链表在添加和删除元素上的效率要比动态数组高很多。java中系统同时提供了双向链表(LinkedList)和动态数组(ArrayList)两种机制。并且,Java中有一个叫ListIterator的迭代器。该迭代器不仅可以向后迭代元素,还能向前迭代,而且还有add()来在某一位置添加元素,十分方便。不过查找效率的话就反过来了,是动态数组的效率比双向链表的效率高,因为你只要提供元素的下标即可。

发表评论