了解LinkedList原理

1.LinkedList介绍

线性链表集合，循环链表http://blog.csdn.net/tiwerbao/article/details/8227689

非线程安全

底层实现：底层使用 Entry<E>实现  entry 有有三个元素 ：

E element 当前元素

Entry<E> next  下个一元素

Entry<E> previous 上一个元素

不需要考虑集合大小与扩展

 

2.与其他集合对比

 参见：http://nassir.iteye.com/blog/1990523 

 

3.源码分析 

 

 public LinkedList() {
        header.next = header.previous = header; // 先初始化一个空的Entry，用来做header，然后首尾相连，形成一个循环链表
    }

 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 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 >> 1 相当于 size/2 通过index确定是向前还是向后查找
            for (int i = 0; i <= index; i++)
                e = e.next;
        } else {
            for (int i = size; i > index; i--)
                e = e.previous;
        }
        return e;
    }

final void checkForComodification() { //检测是否在并发
	    if (modCount != expectedModCount)
		throw new ConcurrentModificationException();
	}


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

 

 

4.优化

 LinkedList 应用在新增和删除操作比较频繁场景