java ArrayList与LinkedList知识点

一 ArrayList

         1.  arraylist里面是通过数组实现的

 

/**
    * The array buffer into which the elements of the ArrayList are stored.
    * The capacity of the ArrayList is the length of this array buffer.
    */
   private transient Object[] elementData;

   /**
    * The size of the ArrayList (the number of elements it contains).
    *
    * @serial
    */
   private int size;

         2. arraylist初始化的时候可以指定大小，如果你知道大小，在创建的时候最好指定

 

 

public ArrayList(int initialCapacity) {
    super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
    this.elementData = new Object[initialCapacity];
    }

         3. arraylist添加元素的时候，需要判断存放元素的数组是否需要扩容（扩容大小是原来大小的1/2+1）

 

 

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

 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);
    }
    }

        4. arraylist 在指定位置添加元素或者移除指定位置元素，需要移动比较多的数据

 

 

public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(
        "Index: "+index+", Size: "+size);

    ensureCapacity(size+1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
             size - index);
    elementData[index] = element;
    size++;
    }

    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

 

          1. linkedlist是通过链表实现的，一个节点是一个对象，包含了自己前一个节点的和后一个节点的地址

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;

    Entry(E element, Entry<E> next, Entry<E> previous) {
        this.element = element;
        this.next = next;
        this.previous = previous;
    }
    }

         2. 添加元素是通过移动链表指针

 

 

public boolean add(E e) {
    addBefore(e, header);
        return true;
    }
private Entry<E> addBefore(E e, Entry<E> entry) {
    Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
    newEntry.previous.next = newEntry;
    newEntry.next.previous = newEntry;
    size++;
    modCount++;
    return newEntry;
    }

         3. 删除元素也是通过移动指针，所以理论上linkedlist比arraylist更适合添加和删除操作（不需要判断是否需要扩容，不需要移动大批的元素）

 

 

 public boolean remove(Object o) {
        if (o==null) {
            for (Entry<E> e = header.next; e != header; e = e.next) {
                if (e.element==null) {
                    remove(e);
                    return true;
                }
            }
        } else {
            for (Entry<E> e = header.next; e != header; e = e.next) {
                if (o.equals(e.element)) {
                    remove(e);
                    return true;
                }
            }
        }
        return false;
    }

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;
    }

         4. 获取元素需要遍历链表，比arraylist要慢

 

 

public E get(int index) {
        return entry(index).element;
    }
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)) {//size 右移一位表示除以2，其实就是看从前遍历快还是从后遍历快
            for (int i = 0; i <= index; i++)
                e = e.next;
        } else {
            for (int i = size; i > index; i--)
                e = e.previous;
        }
        return e;
    }

          5. linkedlist 迭代器，支持向前向后迭代，在迭代过程中移除元素。如果要遍历linkedlist，建议使用迭代器，因为如果使用get方法效率没迭代器高。（从get方法的源码可以看出）

 

 

private class ListItr implements ListIterator<E> {
private Entry<E> lastReturned = header;
private Entry<E> next;
private int nextIndex;
private int expectedModCount = modCount;

ListItr(int index) { //支持从指定位置开始迭代
    if (index < 0 || index > size)
    throw new IndexOutOfBoundsException("Index: "+index+
                        ", Size: "+size);
    if (index < (size >> 1)) {
    next = header.next;
    for (nextIndex=0; nextIndex<index; nextIndex++)
        next = next.next;
    } else {
    next = header;
    for (nextIndex=size; nextIndex>index; nextIndex--)
        next = next.previous;
    }
}

public boolean hasNext() {//是否有下一个
    return nextIndex != size;
}

public E next() { //下一个
    checkForComodification();
    if (nextIndex == size)
    throw new NoSuchElementException();

    lastReturned = next;
    next = next.next;
    nextIndex++;
    return lastReturned.element;
}

public boolean hasPrevious() { //是否有前一个
    return nextIndex != 0;
}

public E previous() { //前一个
    if (nextIndex == 0)
    throw new NoSuchElementException();

    lastReturned = next = next.previous;
    nextIndex--;
    checkForComodification();
    return lastReturned.element;
}

public int nextIndex() {
    return nextIndex;
}

public int previousIndex() {
    return nextIndex-1;
}

public void remove() { //删除元素
           checkForComodification();
           Entry<E> lastNext = lastReturned.next;
           try {
               LinkedList.this.remove(lastReturned);
           } catch (NoSuchElementException e) {
               throw new IllegalStateException();
           }
    if (next==lastReturned)
               next = lastNext;
           else
    nextIndex--;
    lastReturned = header;
    expectedModCount++;
}

public void set(E e) {
    if (lastReturned == header)
    throw new IllegalStateException();
    checkForComodification();
    lastReturned.element = e;
}

public void add(E e) {
    checkForComodification();
    lastReturned = header;
    addBefore(e, next);
    nextIndex++;
    expectedModCount++;
}

final void checkForComodification() {
    if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
}
   }