Java源码分析之LinkedList

 

LinkedList源码分析

1. 数据结构

1.1. 单链表

1.2. 双向链表

LinkedList采用的是双向链表模式，而每一个节点就是一个LinkedList类的一个私有静态的内部类Entry，Entry含有三个成员：E element (E就是申明变量时需要的泛型参数)、Entry next、Entry previous。

2. 类的申明

 

public class LinkedList<E>
    extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable

 

继承至AbstractSequentialList(此类提供了List接口的骨干实现，从而最大限度减少了实现受“连续访问”数据存储支持的此接口的所需工作)

在实现的接口中Cloneable表示LinkedList能够被复制，实现java.io.Serializable表示此类能被序列化

3. 成员变量分析

 

private transient Entry<E> header = new Entry<E>(null, null, null);
private transient int size = 0;

 

关键字transient的作用是表示一个域不是该对象串行化(序列化)的一部分，当这个对象串行化的时候transient申明的变量不包括在串行化的表示中，而非transient的变量会被包括进去。

4. 构造函数分析

 

 /**
     * Constructs an empty list.	//构造一个空链表
     */
    public LinkedList() {
        header.next = header.previous = header;
    }
    public LinkedList(Collection<? extends E> c) {
	this();		//首先构造一个空链表
	addAll(c);	//将初始化的Collection加入到此链表中
  }

     

5. 成员方法分析

5.1. 增加元素

LinkedList提供像链表中增加元素的方法有很多,例如：add(e)、add(int,e)、addAll(int,Collection)、addAll(Collection)，只需分析add(int,e)以及addAll(int,Collection)即可,其余的都是基于这两个函数实现的。

5.1.1. Add(int,e)

 

public void add(int index, E element) {
        addBefore(element, (index==size ? header : entry(index)));
}

entry(index)将在链表中返回位置是index的链表元素，因为链表不像数组可以随机读取，对于链表来说得到某一位置的元素只能一个一个遍历得到位置，然后将前后位置元素的索引改变，而LinkedList是一个双向链表，在寻找插入位置的时候，会判断是位于前半部分还是后半部分，如果是前半部分则从第一个往后遍历，如果是后半部分则有最后一个往前遍历，然后将位置属于index的元素返回。

addBefore(E e,Entry entry)

 

private Entry<E> addBefore(E e, Entry<E> entry) {
    //将newEntry的next指向entry,previous指向尾部entry的尾部
    Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
//将entry前面元素的后驱指向newEntry
    newEntry.previous.next = newEntry;
    //将entry元素的前驱指向newEntry
    newEntry.next.previous = newEntry;
size++;
    modCount++;
    return newEntry;
}

 

对于add(E e)则是调用方法addBefore(e,header)

5.1.2. addAll(int,Collection)

 

public boolean addAll(int index, Collection<? extends E> c) {
    //验证链表的长度与要插入的位置的大小
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        //将要插入的Collection转换成数组
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew==0)
            return false;
        modCount++;//是AbstractList中得一个字段，用来记录list结构变化的次数
        //得到index位置的entry
        Entry<E> successor = (index==size ? header : entry(index));
        Entry<E> predecessor = successor.previous;
        //依次将c插入原链表中
        for (int i=0; i<numNew; i++) {
            Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
            predecessor.next = e;
            predecessor = e;
        }
        successor.previous = predecessor;
        size += numNew;
        return true;
    }

 

5.2. 删除元素

仅分析remove(Entry<E> e),因为其余有关删除的操作都是基于这个函数实现的

 

private E remove(Entry<E> e) {
	if (e == header)
		throw new NoSuchElementException();

	E result = e.element;
	//将要删除的元素的前面元素的后驱指向删除元素的后驱
	e.previous.next = e.next;		
       //将要删除的元素的后面元素的前驱指向删除元素的前驱
	e.next.previous = e.previous;
	e.next = e.previous = null;
	e.element = null;
	size--;
	modCount++;
	return result;
}

   

6. 迭代器

与ArrayList不同的是LinkedList实现了自己的迭代器，实现了ListIterator接口，ListIterator接口继承至Iterator接口，LinkedList，没有直接使用AbstractList虚类中的实现，LinkedList内部自定义了一个内部类ListItr，该类实现了ListIterator接口，专门对LinkedList进行迭代，但是要注意的是因为ArrayList与LinkedList的迭代器的功能和特点都是一样的，所以符合ArrayList迭代器的特点都符合LinkedList的特点。AbstractList实现了两个迭代器分别是Itr以及ListItr，其中ListItr更适用于LinkedList，因为LinkedList是一个双向链表。以下是LinkedList中的：ListIterator的实现：

 

private class LinkedList implements ListIterator<E> {
//最近一次next或previous操作所返回的元素，初始为头结点，表示链表的开始与结尾
    private Entry<E> lastReturned = header;
    //next操作所返回的节点
    private Entry<E> next;
    //记录当前next指向的entry的位置，与next保持一致
    private int nextIndex;
    //检测外界是否改变结合的结构
    private int expectedModCount = modCount;
    //得到第index位置的元素(entry)
    ListItr(int index) {
       //此方法运行完毕next指向的就是index位置的元素
        if (index < 0 || index > size)
       throw new IndexOutOfBoundsException("Index: "+index+
                         ", Size: "+size);
        if (index < (size >> 1)) {   //当index小于size的一半是在前半部找
           next = header.next;  //从第一个元素开始
           for (nextIndex=0; nextIndex<index; nextIndex++)
               next = next.next;
        } else {
           next = header;
            for (nextIndex=size; nextIndex>index; nextIndex--)
               next = next.previous;
        }
    }
 
    public boolean hasNext() {
        return nextIndex != size;
    }
 
    public E next() {
        checkForComodification();
        if (nextIndex == size)
       throw new NoSuchElementException();
 
        lastReturned = next;
        next = next.next;
//执行next的结果是next与lastReturned不相等
        nextIndex++;
        return lastReturned.element;
    }
 
    public boolean hasPrevious() {
        return nextIndex != 0;
    }
 
    public E previous() {
        if (nextIndex == 0)
       throw new NoSuchElementException();
//执行previous的结果是next与lastReturned不相等
        lastReturned = next = next.previous;
        nextIndex--;
        checkForComodification();
        return lastReturned.element;
    }
 
    public int nextIndex() {
        return nextIndex;
    }
 
    public int previousIndex() {
        return nextIndex-1;
    }
 
    public void remove() {
            checkForComodification();
            Entry<E> lastNext = lastReturned.next;
            try {
                LinkedList.this.remove(lastReturned);
            } catch (NoSuchElementException e) {
                throw new IllegalStateException();
            }
        if (next==lastReturned)
             next = lastNext;
        else
           nextIndex--;
       //每次remove操作之后就会将lastReturned指向header
        lastReturned = header;  
        expectedModCount++;
    }
 
    public void set(E e) {
        if (lastReturned == header)
            throw new IllegalStateException();
        checkForComodification();
        lastReturned.element = e;
    }
 
    public void add(E e) {
        checkForComodification();
//每次add操作之后就会将lastReturned指向header
        lastReturned = header;
        addBefore(e, next);
        nextIndex++;
        expectedModCount++;
    }
 
    final void checkForComodification() {
        if (modCount != expectedModCount)
       throw new ConcurrentModificationException();
    }
}

 

从源码中可以看出：

1.  刚实例化的迭代器lastReturned是指向header节点的，是不能马上进行删除跟修改操作的，需要首先进行后移或者前移操作；

2.  只要lastReturned指向header是不能进行删除以及修改操作的，所以以下成立：

 可以对迭代器进行连续的添加或者修改，但是不能进行连续的删除，因为删除后lastReturned指向header是不能再删除的；

 进行添加操作后不能立刻进行删除或者修改操作；

 进行删除操作操作后可以进行添加操作，但是不能进行修改操作；

 进行修改后是可以进行删除和增加操作的；