LinkedList集合源码分析

LinkedList这个集合想必大家都有使用过，它是java单列集合Collection的一个实现。
LinkedList有以下几个特点：

• 底层数据结构是双向链表
• 内部不保存下标
• 线程不安全

LinkedList的使用十分简单，这里不再给出，重点讲下LinkedList的源码和底层实现。
首先看一下LinkedList底层保存数据的Node类

 private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

Node是LinkedList的静态内部类，主要有item，next，prev3个属性。

• item 用于存储值，就是我们往集合中放的数据
• next 下一个节点的引用
• prev 前一个节点的引用

从属性上也可以看出LinkedList底层是一个双向链表。
再看一下LinkedList的其他属性：

	transient int size = 0;

   
    transient Node<E> first;

   
    transient Node<E> last;

• size 保存集合的长度
• first 集合中的第一个节点
• last 集合中的最后一个节点

然后就是LinkedList的主要方法

• void linkFirst(E e) 从集合前面添加元素
• void linkLast(E e) 从集合后面添加元素
• Node node(int index) 获取指定位置节点
• E unlink(Node x) 删除一个节点
• E set(int index, E element) 修改指定下标的元素

下面会一一讲解
void linkFirst(E e) 从集合前面添加元素

 private void linkFirst(E e) {
		 //取出首节点
        final Node<E> f = first;
		//创建一个节点, 元素为e, prev为null, next为首节点
        final Node<E> newNode = new Node<>(null, e, f);
		//首节点变为新创建节点
        first = newNode;
		//如果原有首节点不存在, 证明集合中没有节点,新添加的为第一个节点,所以既是首节点又是尾节点
		//如果原有首节点存在, 那就把原有首节点的prev变为新创建的节点
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
		//集合长度加1
        size++;
        modCount++;
    }

void linkLast(E e) 从集合后面添加元素

 void linkLast(E e) {
		 //取出尾节点
        final Node<E> l = last;
		//创建一个新节点,元素为e, prev为尾节点
        final Node<E> newNode = new Node<>(l, e, null);
		//尾节点变为新建节点
        last = newNode;
		//原尾节点为空, 证明集合中没有节点,新添加的为第一个节点,所以既是首节点又是尾节点
		//原尾节点不为空, 原尾节点的next变为新建节点
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

Node node(int index) 获取指定位置节点

 Node<E> node(int index) {
		//如果index小于链表长度的一半,从首节点开始查找
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
			//index大于等于链表长度的一半,从尾节点开始查找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
        //从这里也可以看出LinkedList查询效率较低，只能遍历链表
    }

E unlink(Node x) 删除一个节点

E unlink(Node<E> x) {
        //取出节点元素,用于返回
        final E element = x.item;
		//取出该节点的next,prev
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
		//prev为空,证明该节点为首节点,移除该节点后next变为首节点
        if (prev == null) {
            first = next;
        } else {
			//prev不为空,prev和next相连接
            prev.next = next;
            x.prev = null;
        }
		next为空,证明该节点为尾节点,移除该节点后prev变为尾节点
        if (next == null) {
            last = prev;
        } else {
			//next不为空,next和prev相连接
            next.prev = prev;
            x.next = null;
        }
		//元素置为null
        x.item = null;
		//长度-1
        size--;
        modCount++;
        return element;
    }

E set(int index, E element) 修改指定下标的元素
此方法非常简单，有兴趣的可阅读下源码

 public E set(int index, E element) {
 		// 检查下标是否合法（index >= 0 && index < size ）
        checkElementIndex(index);
        // 取出该下标的节点
        Node<E> x = node(index);
        // 取出旧值
        E oldVal = x.item;
        // 设置新值
        x.item = element;
        // 返回旧值
        return oldVal;
    }

以上方法在什么时候被调用？
linkFirst： 在我们调用add，addFirst时
linkLast： 在我们调用addLast时
node： 在我们调用get时
unlink： 在我们调用remove方法时
set： 本身就是public方法，由我们调用