标签归档：LinkedList

从数据结构的角度看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