月度归档:2016年04月

从数据结构的角度看ArrayList与LinkedList

数组应该是大部分开发者最常用的数据结构,而链表使用频率则相对小一些。对于Java开发者而言,数组和链表这两种数据结构分别对应Java集合类中ArrayList和LinkedList。对我而言,至少在Java开发中,我99%以上都是使用ArrayList。
为了避免上述的情况,就从数据结构的角度来分析一下这两者的优缺点以及使用场景。

数组

数组很简单,就是一段相同类型的元素的集合。用ArrayList简单的创建一个集合:

ArrayList<Integer> arrays = new ArrayList<Integer>();
arrays.add(2);
arrays.add(4);
arrays.add(6);
arrays.add(8);

它在内部的数据结构即为数组,类似下面:

int[] arrays = {2,4,6,8};

此时,如果我们想要在索引为2的位置插入一个元素5,使数组变成{2,4,5,6,8}。如下图:

arraylist

Java中对应操作为:

arrays.add(2, 5);

这时ArrayList内部其实做了下面这些事情:

  1. 动态扩大数组;
  2. 将原来数组索引为2及其后面所有的元素向后移动;
  3. 插入新元素5到索引为2的位置。

对于删除某个元素也是类似的操作,所以现在应该可以看出数组的随机访问速度应该是不错的,而随机存储效率比较低。

链表

链表有单向链表、双向链表和循环链表,LinkedList使用的是非循环双向链表。双向链表的每一个元素为一个节点,每个节点都有一个直接前驱,数据域,直接后继。同样用LinkedList简单创建一个集合:

LinkedList<Integer> linkedList = new LinkedList<Integer>();
linkedList.add(2);
linkedList.add(4);
linkedList.add(6);
linkedList.add(8);

它在内部的数据结构即为链表,同样如果想要在索引为2的位置添加一个5,对应的图如下:

linkedlist

 

Java中对应操作为:

linkedList.add(2, 5);

这时LinkedList内部其实做了下面这些事情:

  1. 同样先检查是否超出边界;
  2. 对半查找出原来索引为2的节点将其前驱改为新增节点5;
  3. 将新增节点5的前驱改为4,后继改为6;
  4. 节点4的后继改为5。

同样对于链表中节点的删除也是如此,只要修改指针指向即可,而不必像数组那样大费周章的移动。由此可见链表的优点是随机存储效率高,而缺点就是随机访问效率较低。

总结

比较完数组与链表的优缺点,现在对于它们各自的使用场景应该更清楚了。
数组适合在大量随机访问集合的情况下使用,而链表更适合在大量随机存储,即大量的添加删除时使用。

THE END