大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > vector和ArrayList和linklist的内部数据结构

vector和ArrayList和linklist的内部数据结构

关键词:vectorArrayListlinklistvect  阅读(737) 赞(16)

[摘要]本文主要是对vector和ArrayList和linklist的内部数据结构的讲解,希望对大家学习vector和ArrayList和linklist的内部数据结构有所帮助。

  Java面试中关于容器类List,Set是必问题目。但在我的面试经历中很难遇到满意的答复。大部分只能了解其大概使用方法,对其内部结构缺乏了解,错误的使用方式会导致性能大幅下降。

  首先介绍ArrayList,顾名思义内部数据结构是数组

  Java代码

  private transient Object[] elementData;

  private int size;

  public ArrayList(int initialCapacity){

  }

  在增加元素时,若容量不足进行扩充

  Java代码

  public void ensureCapacity(int minCapacity) {

  modCount++;

  int oldCapacity = elementData.length;

  if (minCapacity > oldCapacity) {

  Object oldData[] = elementData;

  int newCapacity = (oldCapacity * 3)/2 + 1;

  if (newCapacity < minCapacity)

  newCapacity = minCapacity;

  // minCapacity is usually close to size, so this is a win:

  elementData = Arrays.copyOf(elementData, newCapacity);

  }

  }

  新数组大小为之前数组大小*1.5+1 ,加上1保证oldCapacity为1的情况也能扩充为2

  (类似分页时总页数=(总记录数+ (每页记录数-1))/每页记录数算法)

  删除元素时通过 System.arraycopy把删除位置后的所有元素前移一个位置实现

  Vector中:

  [java]

  private void ensureCapacityHelper(int minCapacity) {

  int oldCapacity = elementData.length;

  if (minCapacity > oldCapacity) {

  Object[] oldData = elementData;

  int newCapacity = (capacityIncrement > 0) ?

  (oldCapacity + capacityIncrement) : (oldCapacity * 2);

  if (newCapacity < minCapacity) {

  newCapacity = minCapacity;

  }

  elementData = Arrays.copyOf(elementData, newCapacity);

  }

  }

  vector当增加数组大小时是默认扩展一倍

 

  Java代码

  public E remove(int index) {

  RangeCheck(index);

  modCount++;

  E oldValue = (E) elementData[index];

  int numMoved = size - index - 1;

  if (numMoved > 0)

  System.arraycopy(elementData, index+1, elementData, index,

  numMoved);

  elementData[--size] = null; // Let gc do its work

  return oldValue;

  }

  LinkedList大家都知道是通过链表实现,内部是一个双向链表

  Java代码

  public class LinkedList

  extends AbstractSequentialList

  implements List, Deque, Cloneable, java.io.Serializable

  {

  private transient Entry header = new Entry(null, null, null);

  private transient int size = 0;

  }

  private static class Entry {

  E element;

  Entry next;

  Entry previous;

  }

  插入和删除都只要改动前后节点的next和previous实现

  总结特点如下:

  类型 内部结构 顺序遍历速度 随机遍历速度 追加代价 插入代价 删除代价 占用内存

  ArrayList 数组 高 高 中 高 高 低

  LinkedList 双向链表 高 低 低 低 低 中

  所以:

  一般顺序遍历情况下使用ArrayList,但注意构造函数中设置初始大小

  尽量不对ArrayList进行插入或删除操作(删除尾部除外),若有多次删除/插入操作又有随机遍历的需求,可以再构建一个ArrayList,把复合条件的对象放入新ArrayList,而不要频繁操作原ArrayList

  经常有删除/插入操作而顺序遍历列表的情况下最适合使用Linkedlist

  综上所述:那么 Collection的List下的Vector和ArrayList和LinkedList有什么异同???

  首先vector和ArrayList都是基于Aarry的线性数组,vector是线程安全的而ArrayList不是,ArrayList动态增加数组大小的模式是当新增的大小超出了原有数组的范围,ArrayList就会在原来基础上增加到原来数组大小的1.5倍+1,加1是为了当数组大小为1时也能根据该流程将数组大小扩充到2.

  ArrayList和LinkedList的区别,ArrayList是线性数组而LinkedList是双向链表数组内部结构是节点元素和向前节点和向后节点,所以ArrayList查询的速度相对较快,LinkedList的插入删除更新相对较慢。另Linkedlist还提供了list没有提供的方法,linkedlist专门用于操作表头和表尾,可以当做堆、队列和双向队列操作。



相关评论