Go语言视频零基础入门到精通

javalearner

ArrayList是用数组实现的，LinkedList是用双向链表实现的。
   
   
    ArrayList:
   
   
       内含两个成员变量：elementDate和size，elementData是对象数组类型的变量(Object[])，声明为transient，即序列化的时候不包括elementData这个变量。
   

   

   
   
    声明一个ArrayList对象时，若无参数，默认的数组大小是10。
   
   
     
     
      public ArrayList() {
      
   
      this(10);
      
         }
      
     
   

   
   
    trimToSize()方法，把数组的大小缩小到数组成员的个数，减少存储空间的使用。
   
   
     
     
      public void trimToSize() {
   modCount++;
   int oldCapacity = elementData.length;
   if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
   }
         }
      
     
     
  
   
   
     
   

     
   
  



  
   
  

  若新加成员后数组不够用，则使用ensureCapacity(int minCapacity)来扩大数组大小，新数组大小为原来的1.5倍加1
  

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

  list可以存储null元素。
  

  
  
get操作：
  

   
   
   
     public E get(
     int index) {
     
   RangeCheck(index);
     

     
   
     return (E) elementData[index];
     
         }
     
   
  

  
  
set操作：
  

  
  
  
  
   public E set(
   int index, E element) {
   
   RangeCheck(index);
   

   
   E oldValue = (E) elementData[index];
   
   elementData[index] = element;
   
   
   return oldValue;
   
         }
   
  
  

  
  
add操作：
  

  
  
  
  
   public
   boolean add(E e) {
   
   ensureCapacity(size + 1);   
   // Increments modCount!!
   
   elementData[size++] = e;
   
   
   return
   true;
   
         }
   
  
  

  
  
remove操作：
  

  
  
  
  
   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;
   
         }
   
  
  
  
  
   
   
     解释下remove操作，System.arraycopy操作通过复制index+1至index+1+numMoved-1的元素到index至index+numMoved-1来达到删除指定位置的元素，然后通过
   elementData[--size] = null;来让gc识别null元素并回收。
   
  
   

   LinkedList:
   
  
   内含2个成员变量header和size，header表示头节点。
   
  
   LinkedList用静态内部类Entry来表示一个节点，除了存储元素的数据外，还存储前驱节点和后驱节点。
   
  
   
   
get操作：
   
  
   
   
   
   
    public E get(
    int index) {
   
                 
    return entry(index).element;
   
         }
   
   
   
  
   
   
set操作：
   
  
   
   
   
   
    public E set(
    int index, E element) {
   
                 Entry<E> e = entry(index);
   
                 E oldVal = e.element;
   
                 e.element = element;
   
                 
    return oldVal;
   
         }
   
   
   
  
   
   
entry方法：
   
  
   
   
   
   
    private Entry<E> entry(
    int index) {
   
   
    if (index < 0 || index >= size)
   
      
    throw
    new IndexOutOfBoundsException(
    "Index: "+index+
    ", Size: "+size);
   
                 Entry<E> e = header;
   
                 
    if (index < (size >> 1)) {
   
                        
    for (
    int i = 0; i <= index; i++)
   
                                 e = e.next;
   
                 }
    else {
   
                        
    for (
    int i = size; i > index; i--)
   
                                 e = e.previous;
   
                 }
   
                 
    return e;
   
         }
   
   
   
  
   entry(int index)方法是这样的，如果指定的位置小于size/2，则从头开始检索，如果大于size/2，则从尾开始检索。
   
  
   entry方法需要移动指针。故set操作需要较多的时间。
   
  
   
   
remove操作：
   
  
   
   
   
   
    private E remove(Entry<E> e) {
   
   
    if (e == header)
   
         
    throw
    new NoSuchElementException();
   

   
   E result = e.element;
   
   e.previous.next = e.next;
   
   e.next.previous = e.previous;
   
   e.next = e.previous =
    null;
   
   e.element =
    null;
   
   size--;
   
   modCount++;
   
                 
    return result;
   
         }
   
   
   
  
   remove方法很简单，只需要移动前驱节点和后继节点的指向即可。
   
  
   
总结：
   
  
   1：对set、get方法，因为ArrayList采用的是数组实现，故在常数时间里即可实现，而对LinkedList来说，它要移动指针来定位相应的元素，故需花多点的时间。
   
  
   
   
2：对insert、remove操作，ArrayList常需要移动数组元素，而LinkedList只要改变指针指向即可。
   
  
   


  
  
   
   

     
   

     
   
  

复制代码