Java数据结构

ArrayList

ArrayList即数组列表，是基于数组实现的，这个数组可以插入任何元素，只不过这个数组是可以按需扩容，可以进行数据拷贝的

ArrayList的构造

private static final int DEFAULT_CAPACITY = 10;
//默认初始化容量
private int size; 
//size指elementData中实际有多少元素
transient Object[] elementData;
//element.length指集合容量
//transient关键字只能修饰变量，不可修饰方法和类，该变量被序列化后将无法被访问
protected transient int modCount = 0;
//记录对list操作的次数

//无参构造
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//当使用无参构造时，给elementData数组赋值了一个空数组，这个空数组知道当无参构造时，第一次添加元素后如何扩容。构造时赋予空数组，而当第一次添加元素时，容量便会扩充到10

//有参构造
private static final Object[] EMPTY_ELEMENTDATA = {};
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
        //参数大于零且合法，便初始化一个数组便赋值给elementData
    } else if (initialCapacity == 0) {
        //参数为零，便将空数组赋值给elementData
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        //参数不合法，提示错误
        throw new IllegalArgumentException("Illegal Capacity: "+
                                  			initialCapacity);
    }
}

//使用指定collection来构造
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    //将collection c转化为数组并赋值给elementData
    if ((size = elementData.length) != 0) {、
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            //若elementData的数组类型不是object，就做一次转换
        elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

ArrayList的相关操作

//add 操作
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //对size进行自增操作，即成功添加新元素
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    //当使用无参构造时，添加一个元素时会将容量设置为默认10，并进行扩容
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    //确认是否需要扩容：即size+1是否会超出容量
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        //扩容，使用grow方法
        grow(minCapacity);
}

//grow操作，当添加元素发现容量不足或无参构造第一次添加元素时，需要扩容
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //将容量扩充至原大小的1.5倍，但是这个大小可能有大有小，所以需要if语句来进行判断
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //扩容后的容量还是很小，不满足需要的容量，则直接将需要的容量赋值给newCapacity
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        //扩容后的容量太大了，就改变扩容方式
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    //将原数组的大小扩充至newCapacity
    elementData = Arrays.copyOf(elementData, newCapacity);
}

//当扩大1.5倍后超出了最大范围，那么就干脆将大小设为最大范围
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

//remove操作
//输入索引
public E remove(int index) {
    //检测这个元素是否处于数组的最后一个位置
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        //若index不在最后一位，则将index+1开始向后的所有元素向前移动一位，相当于删除了index位置的元素
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    //将最后一位赋值为null
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}
//参数直接为指定元素
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

//get操作
public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}
//由于arraylist的底层基于数组，获取元素就很简单，直接调用数组访问即可

//迭代器
//由上述源码可知，在进行remove的时候，size是时刻动态变化的，所以不能对arrayList进行for循环遍历来remove元素，这样容易造成结果不准确甚至数组下标越界
public Iterator<E> iterator() {
    return new Itr();
}
//当创建迭代器时 list.iterator();会直接返回一个Itr对象


//ArrayList的内部类Itr实现了Iterator接口，该类有三个方法
private class Itr implements Iterator<E> {
    int cursor = 0 ;       // index of next element to return，下一个要访问的元素
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;//代表对ArrayList修改次数的期望值，初始为modCount

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        //判断expectedModCount是否和modCount相等
        checkForComodification();
        int i = cursor;
        //判断是否越界
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];//lastRet和cursor都自增1，并返回自增后的lastRet
    }

    public void remove() {
        //
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            //调用ArrayList的remove方法并将两个游标向前移动一位
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}
//如果要对ArrayList进行遍历操作，就要使用迭代器，且在remove之前必须hasnext和next

如何将ArrayList转换为普通数组？

ArrayList<Integer> list = new ArrayList<>();
Object[] o = list.toArray();

LinkedList

linkedlist与arraylist不同，后者基于一个被维护的数组来实现动态调整大小，而前者则是一个双向链表

链表的优势：当插入和删除比较频繁的时候，链表相较于数组能有更高的效率(通常情况下，也有特殊情况，比如arraylist的中间插入效率就要高一些)，但是查找效率却不高。

//内部类node的源码
//一个对象对应一个节点
    private static class Node<E> {
       //元素的引用
       //如果为null,表示没有存储任何元素，如果不为null,表示存储了某种类型的元素
       E item;
       //下一个节点的引用
       //引用代表了对象的十六进制地址值,所以也可以注释为:下一个节点在内存中的地址
       //如果为null,可能是空链表，也可能是尾节点
       Node<E> next;
       Node<E> prev;
       Node(Node<E> prev, E element, Node<E> next) {
          //元素的引用初始化
          this.item = element;
          //上一个节点的引用初始化
          this.next = next;
          //下一个节点的引用初始化
          this.prev = prev;
       }
    }

//变量
transient int size = 0;
//元素数量
transient Node<E> last;
//首节点的固定引用，必须先创建首节点，才能创建下一个节点
transient Node<E> first;
//尾节点的固定引用

//头插
private void linkFirst(E e) {
    //再创建一个指针f指向首节点
	final Node<E> f = first;
    //前指针为空，后指针指向f
	final Node<E> newNode = new Node<>(null, e, f);
    //将first首指针指向newnode，代表newnode成为新的首元素
	first = newNode;
    //若f指向的元素为空，证明加入newnode前链表为空，那么newnode既是首元素，也是尾元素
	if (f == null) last = newNode;
    //若不为空，将前指针指向newnode，形成双向链表
	else f.prev = newNode;
	size++; modCount++;
}
//linkedlist的头插效率非常高，因为arraylist的头插需要进行大量的移位，元素复制的操作，还可能需要进行扩容，而链表只需调整指针的指向即可

//尾插
void linkLast(E e) {
    //与头插大同小异
	final Node<E> l = last;
    //最后一个节点的next为null
	final Node<E> newNode = new Node<>(l, e, null);
	last = newNode;
	if (l == null) first = newNode;
	else l.next = newNode;
	size++; modCount++;
}
//出乎意料地是，linkedlist的尾插效率却比arraylist要低，因为arraylist无需进行移位拷贝操作，而linkedlist则需要创建对象，后者要耗时许多

//中间插入
public void add(int index, E element) {
    //输入索引和元素，检查索引范围是否合法
	checkPositionIndex(index);
    //若索引为size则进行尾插
	if (index == size) linkLast(element);
    //不是，则进行中间插入
	else inkBefore(element, node(index));
}
Node<E> node(int index) {
	// assert isElementIndex(index);
    //size>>1：size的一半，判断元素在左半区间，还是右半区间
	if (index < (size >> 1)) {
        //在左半区间，操纵first指针找到index元素
		Node<E> x = first;
		for (int i = 0; i < index; i++)
		x = x.next;
		return x;} 
    else {
        //在右半区间，操纵last指针找到index元素
		Node<E> x = last;
		for (int i = size - 1; i > index; i--)
		x = x.prev;
		return x;}
}
void linkBefore(E e, Node<E> succ) {
	// assert succ != null;
    //在index所指的元素之前插入新元素
	final Node<E> pred = succ.prev;
	final Node<E> newNode = new Node<>(pred, e, succ);
	succ.prev = newNode;
	if (pred == null) first = newNode;
	else pred.next = newNode;
	size++; modCount++;
}
//在数据量较大的时候，中间插入相比arrayList仍然会消耗较多的时间，所以CRUD效率不是绝对的可以分高下，需要根据应用场景和数据量等来综合考量

//删除节点
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
	unlink(x);
	return true;
		}
	}
} else {
	for (Node<E> x = first; x != null; x = x.next) {
    if (o.equals(x.item)) {
	unlink(x);
	return true;
		}
	}
}
return false;
}
//解链操作，即将这个元素从链表中移除
E unlink(Node<E> x) {
// assert x != null;
	final E element = x.item;
	final Node<E> next = x.next;
	final Node<E> prev = x.prev;
    //若上个结点为空，则直接将首指针指向next
	if (prev == null) first = next; 
    //断掉x的prev指针
    else {prev.next = next;x.prev = null;}
    //若下一个结点为空，则直接将尾结点指向prev
	if (next == null) last = prev;
    //断掉x的next指针
    else {next.prev = prev;x.next = null;}
	x.item = null;
	size--;
	modCount++;
	return element;
	}