java集合 - ArrayList 和LinkedList

ArrayList是可增长数组，当存储的数组不足时，根据capacity值进行创建新的增长后的数组，然后将旧的数组拷贝到新的数组中。查找快，增删慢的特性。

初始化

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
// 默认的容量
    private static final int DEFAULT_CAPACITY = 10;
 
    private static final Object[] EMPTY_ELEMENTDATA = {}; 
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 // 数组内容
    transient Object[] elementData;  

 // 数组大小
    private int size;   
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        }
    }
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
  
复制代码

add的过程

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // size+1 是需要的长度，进行判断大小是否足够，也是最小的需要的容量
        elementData[size++] = e;
        return true;
    }
    
   private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
    
     private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
// 需要的最小长度，如果大于现有的长度，则增长
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
 
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
     private void grow(int minCapacity) {
     // 增长旧的容量的一般
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果最小的需要容量比现有的再增长一般还要高 ，则按照minCapacity
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 一般    这里都是负值
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 生成新数组    
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
 
 
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0)  
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }
 
 
 
复制代码

remove的过程

public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        E oldValue = (E) elementData[index]; // 获取到remove的元素，

        int numMoved = size - index - 1;
        if (numMoved > 0)// 向前复制移动一位
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        elementData[--size] = null;// 最后一个元素为null

        return oldValue;
    }

}
复制代码

LinkedList

linkedList 是一个链表，增删快，查找慢的特性。双链表 每个节点都有指向前一个和下一个节点的引用。

add("")的过程

public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
 void linkLast(E e) {
    // 持有到尾节点的引用
        final Node<E> l = last;
      //创建新的节点  ，初始化前节点，value，next节点为null。
        final Node<E> newNode = new Node<>(l, e, null);
      //  last节点指向新节点。
        last = newNode;
      // 如果第一个元素，last 和first节点都是新节点 
      // 否则 让前一个节点的next指向新节点
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
    
    
复制代码

remove(1)的过程

public E remove(int index) {
       return unlink(node(index));
    }
  // 查找到index上的元素
  Node<E> node(int index) { 
  // 如果index 小于size的一半，从头开始查找，
  // 否则 从末尾开始查找 
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
            // 通过next，不停的找到下一个对象
                x = x.next;
            return x;
        } else {
       // 从尾部 递减
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }	
// 找到该节点后，获取 该节点的前一个和下一个节点。	
 E unlink(Node<E> x) { 
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
// 如果前一个节点为null，则该节点是第一个节点，
        if (prev == null) {
            first = next;
        } else {
 // 将前一个节点的next指向下一个节点       
            prev.next = next;
            x.prev = null;
        }
// next 为null 则是尾节点，last则是前一个节点
        if (next == null) {
            last = prev;
        } else {
 // next的前一个等于前一个       
            next.prev = prev;
            x.next = null;
        }
        // 
        x.item = null;
        size--;
        modCount++;
        return element;
    }
    
复制代码

C++版本的ArrayList

#include <malloc.h>
 

template<class E>
class ArrayList {
private:
    // 长度，数组，当前角标
    E *array = NULL;// 当前数组的指针
    int len = 0;// 数组大小
    int index = 0;// 当前角标
public:
    ArrayList();

    ArrayList(int len);

    void add(E e);

    E remove(int index);

    E get(int index);

    ~ArrayList();

    int size();

    // 拷贝构造函数

private:
    void ensureCapacityInternal(int capacity);

    void grow(int capacity);
};

//-------------------- 实现 -----------------------//

template<class E>
ArrayList<E>::ArrayList() {}

// 每次实现方法都得添加
template<class E>
ArrayList<E>::ArrayList(int len) {
    if (len <= 0) {
        return;
    }
    this->len = len;
    this->array = (E *) malloc(sizeof(E) * len);
}

template<class E>
ArrayList<E>::~ArrayList() {
    if (this->array) {
        free(this->array);
        this->array = NULL;
    }
}

template<class E>
int ArrayList<E>::size() {
    return this->index;
}

template<class E>
void ArrayList<E>::add(E e) {
    ensureCapacityInternal(index + 1);  // Increments modCount!!
    this->array[index++] = e;
}

template<class E>
void ArrayList<E>::ensureCapacityInternal(int capacity) {
    if (this->array == NULL) {
        capacity = 10;
    }
    if (capacity - len > 0) {
        // 创建新的数组
        grow(capacity);
    }
}

// 扩容数组的大小
template<class E>
void ArrayList<E>::grow(int capacity) {
    // 扩容
    int new_len = len + (len >> 1);
    if (capacity - new_len > 0) {
        new_len = capacity;
    }

    // 创建新的数组
    E *new_arr = (E *) malloc(sizeof(E) * new_len);

    if (this->array) {
        // 原来的数据拷贝进来
        memcpy(new_arr,this->array, sizeof(E) * index);// sizeof(E)*index 字节
        free(this->array);// 内存泄漏
    }

    this->array = new_arr;
    this->len = new_len;
}

template<class E>
E ArrayList<E>::get(int index) {
    return this->array[index];
}

template<class E>
E ArrayList<E>::remove(int index) {
    // 自己做 remove 和 拷贝构造函数
}
复制代码