首页 > 安全资讯 >

高级java工程师-----vector和ArrayList和linklist的内部数据结构

13-02-22

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

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<E>  
    extends AbstractSequentialList<E>  
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable  
{  
    private transient Entry<E> header = new Entry<E>(null, null, null);  
    private transient int size = 0;  
}  
private static class Entry<E> {  
    E element;  
    Entry<E> next;  
    Entry<E> 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专门用于操作表头和表尾,可以当做堆、队列和双向队列操作。
 
相关文章
最新文章
热点推荐