自己写ArrayList后的心得

源码分析

ArrayList应该是Java工具类中最简单的一个。它的内部实现是一个数组，在首次加入元素时，ArrayList会创建一个默认大小的数组，之后的添加、删除、查询 *** 作都是对该数组进行 *** 作。而我自己写的ArrayList则是和LinkedList一样，基于链表实现。下面会一一比较两种方法的差别。

add方法

ArrayList源码的：

public void add(int index, E element) {
		//检查索引是否越界
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);
        //索引之后的元素向后自动移动一位
        System.arraycopy(elementData, index, elementData, index + 1,size - index);
        //将指定元素赋值
        elementData[index] = element;
        size++;
    }

我的add方法：

public void add(int index, Object obj) {
		//检查index是否越界
        if(index > size || index < 0) {
            return;
        }
        if(index == size) {
            this.add(obj);
            return;
        }
        Node node = new Node(obj, null, null);
        Node temp;
        //如果插入的是头部
        if(index == 0) {
            temp = this.tail;
            temp.next = node;
            node.previous = temp;
        }
        //其它地方
        else {
            Node insert = indexOf(index);
            Node previous = insert.previous;
            node.previous = previous;
            node.next = insert; // 要注意此时的节点为inset
            previous.next = node;
            insert.previous = node;
        }
        size++;
    }

不难看出，用链表的话我们每次都需要判断插入位置，因为头部之前没有链表了，即head没有东西。但也有好处：无需利用ArrayCopy将引索之后的元素移位。这里就体现出来了数组增加速度慢，代价大。

remove方法

ArrayList的：

public E remove(int index) {
    //检查索引值
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    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
    return oldValue;
}

我的：

public void remove(int index) {
        Node n;
        //移除的是第一个
        if (index == 0)
        {
            n = head.next;
            head = n;
            n.previous = null;
        } else if (index == size - 1) { // 移除的的是最后一个
            n = tail.previous;
            tail = n;
            n.next = null;
        } else {
            Node node = indexOf(index);
            Node previous = node.previous;
            Node next = node.next;
            previous.next = next;
            next.previous = previous;
        }
        size--;
    }

和add一样，用链表直接删除对应的节点就行，效率高（但我感觉好像差不多）。

clear方法

ArrayList的：

public void clear() {
        modCount++;
        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

我的：

public void clear() { // 清除让所有节点置空即
	this.head = null;
	this.tail = null;
    size = 0;
    }

如果用数组，需要将数组中每一个元素置空，而如果用链表直接将head头节点和tail尾节点置空即可。

---

从上面几个方法我们不难看出链表的优势：增加、删除速度快，代价小，效率高。
当然用链表时我也遇到了一些问题，譬如get()方法。用链表写最后的返回值是所查元素的地址而不是你需要的元素。这里也体现出来了链表节点的组成特点：存储下一个结点的地址。以及相较于数组链表失去了数组随机读取的优点。