自己动手写写：LinkedList源码浅析

上篇文章浅析了ArrayList的源码相关内容！这篇文章将介绍LinkedList相关的内容！

 

二. LinkedList

 

先来看看LinkedList的类结构！

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

 

 

1. 几个重要的成员变量

private transient Entry<E> header = new Entry<E>(null, null, null);
    
private transient int size = 0;//LinkedList的长度 ，初始化为0

这里先来说一下header这个变量，这个很重要哦!

 

首先看一下Entry是个什么东西！

private static class Entry<E>
{
        E element;
        
        Entry<E> next;
        
        Entry<E> previous;
        
        Entry(E element, Entry<E> next, Entry<E> previous)
        {
            this.element = element;
            this.next = next;
            this.previous = previous;
        }
}

对的，Entry就是LinkedList的一个内部静态类！我们知道LinkedList的内部数据结构采用的链式存储方式，链式存储决定了它插入的速度会相对会快，而索引的速度慢！链式存储最主要的有三个元素：当前元素、前一个元素地址、后一个元素地址。

Entry类中element表示当前元素; next表示后一个元素;previous表示前一个元素;这样的话一个链式的存储的模型就有了。

 

2. 两个构造函数

 /**
   * Constructs an empty list.
   */
public LinkedList()
{
      header.next = header.previous = header;
}

无参构造函数初始化的时候header的前一个、后一个均指向本身。

 

 

  /**
   * Constructs a list containing the elements of the specified
   * collection, in the order they are returned by the collection's
   * iterator.
   *
   * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedList(Collection<? extends E> c)
    {
        this();
        addAll(c);
    }

根据已有的Collection初始化LinkedList，我们来看一个addAll(int index, Collection<? extends E> c)这个方法（addAll(Collection<? extends E> c)本身也是调用的此方法，其中index的参数值为size而已）。

 

/**                                                                                 
 * Inserts all of the elements in the specified collection into this                
 * list, starting at the specified position.  Shifts the element                    
 * currently at that position (if any) and any subsequent elements to               
 * the right (increases their indices).  The new elements will appear               
 * in the list in the order that they are returned by the                           
 * specified collection's iterator.                                                 
 *                                                                                  
 * @param index index at which to insert the first element                          
 *              from the specified collection                                       
 * @param c collection containing elements to be added to this list                 
 * @return <tt>true</tt> if this list changed as a result of the call               
 * @throws IndexOutOfBoundsException {@inheritDoc}                                  
 * @throws NullPointerException if the specified collection is null                 
 */                                                                                 
public boolean addAll(int index, Collection<? extends E> c)                         
{                                                                                   
    if (index < 0 || index > size)                                                  
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); 
    Object[] a = c.toArray();                                                       
    int numNew = a.length;                                                          
    if (numNew == 0)                                                                
        return false;                                                               
    modCount++;                                                                     
                                                                                    
    Entry<E> successor = (index == size ? header : entry(index));                   
    Entry<E> predecessor = successor.previous;                                      
    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;                                                                    
}                                                                                   

前面的我就不说了，都是一些预判断。我们来分析下下面这段代码的含义

 Entry<E> successor = (index == size ? header : entry(index));                   
 Entry<E> predecessor = successor.previous;

 

粗略的看一个successor和predecessor 英文含义分别表示为后继者和前辈;对呀，我们想啊，LinkedList本身是一个链式存储结构，你要将一些内容插入进来，首先必须要在链上找到一个入口，然后将此入口掐断，接着将你插入进来的内容放进去，最后再将这个链给接起来，你要将链给接起来要接对啊，不能接错地方啊！successor、predecessor就是为了将链接对所用，分别指向链断裂后，后一段和前一段的链接地址。

我们来看下面这两张图：

图一

图二
上面我描述的过程就类似于从图一到图二的过程。

 

初步感性的分析玩之后我们来详细分析一下！

这里做了一个判断：如果当前插入的index的值等于size则返回header，否则返回entry(index);

1. index == size时，其实就是插入到链尾处，因为链尾处的元素的next比较特殊，它指向了链首header。

2. index != size时，我们先来看一下entry(int index)这个方法的源码：

/**                                                                                
 * Returns the indexed entry.                                                      
 */                                                                                
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))                                                       
    {                                                                              
        for (int i = 0; i <= index; i++)                                           
            e = e.next;                                                            
    }                                                                              
    else                                                                           
    {                                                                              
        for (int i = size; i > index; i--)                                         
            e = e.previous;                                                        
    }                                                                              
    return e;                                                                      
}                                                                                   

其实就是找到找到索引值为index的Entry,判断index值大小是否已经超过了size值的一半，如果没超过就从链表头部开始遍历，否则从链表尾部开始遍历。

ps:看得出来，按索引找个Entry这么麻烦，真慢，不像ArrayList来得那么直接。这就是为什么LinkedList索引慢的原因，存储结构决定的，基因问题，呵呵。

 

3. Entry<E> predecessor = successor.previous; 鉴于上面的分析，这句也就不难理解了。

4.

for (int i = 0; i < numNew; i++)                                                
{                                                                               
        Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);                 
        predecessor.next = e;                                                       
        predecessor = e;                                                            
}

 

 这段代码就是将初始化的Collection数据一个一个链接上去。

 

successor.previous = predecessor; 
size += numNew;

 最后将这个链给接回去，形成了一个闭环链！ LinkedList的大小也要增加一下嘛！

 

   

3. 几个常用方法浅析

/**                                                                     
 * Inserts the specified element at the specified position in this list.
 * Shifts the element currently at that position (if any) and any       
 * subsequent elements to the right (adds one to their indices).        
 *                                                                      
 * @param index index at which the specified element is to be inserted  
 * @param element element to be inserted                                
 * @throws IndexOutOfBoundsException {@inheritDoc}                      
 */                                                                     
public void add(int index, E element)                                   
{                                                                       
    addBefore(element, (index == size ? header : entry(index)));        
}                                                                       

 

 有些代码是不是很熟悉啊？呵呵，还是看内部的addBefore(E e, Entry<E> entry)方法吧。

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

 这个还用我说吗？ 是不是比在构造方法里面的要简单得多啊。

 

 

/**                                                           
 * Returns the element at the specified position in this list.
 *                                                            
 * @param index index of the element to return                
 * @return the element at the specified position in this list 
 * @throws IndexOutOfBoundsException {@inheritDoc}            
 */                                                           
public E get(int index)                                       
{                                                             
    return entry(index).element;                              
}                                                             

   获取指定索引值index的元素，呵呵，不解释了！

 

 

/**                                                    
 * Returns the first element in this list.             
 *                                                     
 * @return the first element in this list              
 * @throws NoSuchElementException if this list is empty
 */                                                    
public E getFirst()                                    
{                                                      
    if (size == 0)                                     
        throw new NoSuchElementException();            
                                                       
    return header.next.element;                        
}                                                      

/**                                                    
 * Returns the last element in this list.              
 *                                                     
 * @return the last element in this list               
 * @throws NoSuchElementException if this list is empty
 */                                                    
public E getLast()                                     
{                                                      
    if (size == 0)                                     
        throw new NoSuchElementException();            
                                                       
    return header.previous.element;                    
}                                                      

 分别为获取第一个和最后一个元素的值，也很简单啊，第一个元素就是header的next的element的值，最后一个元素就是header的previous的element的值。

ps：真实的内部情况是这样的，整个链表的内容是包含header的Entry和LinkedList存储的所有Entry两个部分共同组成的。

 

 

/**                                                                           
 * Returns the index of the first occurrence of the specified element         
 * in this list, or -1 if this list does not contain the element.             
 * More formally, returns the lowest index <tt>i</tt> such that               
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,  
 * or -1 if there is no such index.                                           
 *                                                                            
 * @param o element to search for                                             
 * @return the index of the first occurrence of the specified element in      
 *         this list, or -1 if this list does not contain the element         
 */                                                                           
public int indexOf(Object o)                                                  
{                                                                             
    int index = 0;                                                            
    if (o == null)                                                            
    {                                                                         
        for (Entry e = header.next; e != header; e = e.next)                  
        {                                                                     
            if (e.element == null)                                            
                return index;                                                 
            index++;                                                          
        }                                                                     
    }                                                                         
    else                                                                      
    {                                                                         
        for (Entry e = header.next; e != header; e = e.next)                  
        {                                                                     
            if (o.equals(e.element))                                          
                return index;                                                 
            index++;                                                          
        }                                                                     
    }                                                                         
    return -1;                                                                
}                                                                             

返回第一个包含对象o的索引值。也很简单吧，对吧！

 

 

 

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

这是一个private方法，就是删除链表中的一个Entry，思路如下：将要移除的对象e的previous的next指向e的next,对象e的next的previous指向e的previous，就是将链表的一个节点删掉，在将这个链表接起来。

 

 

 

/**                                                                    
 * Replaces the element at the specified position in this list with the
 * specified element.                                                  
 *                                                                     
 * @param index index of the element to replace                        
 * @param element element to be stored at the specified position       
 * @return the element previously at the specified position            
 * @throws IndexOutOfBoundsException {@inheritDoc}                     
 */                                                                    
public E set(int index, E element)                                     
{                                                                      
    Entry<E> e = entry(index);                                         
    E oldVal = e.element;                                              
    e.element = element;                                               
    return oldVal;                                                     
}                                                                      

 这个更简单，就是替换索引index的Entry的element的值。

 

好吧，基本常用的方法也都分析完了，重点已经照顾到了，其他的就不再累述了。

 

这里就简单描述一下Vector吧！

 

public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

 Vector用得并不多，它和ArrayList很相似，但是它本身是线程安全的，看源码就能够看得出来，很多方法都是synchronized，但是在jdk1.6上就已经有java.util.concurrent了，对于多线程编程的话，Vector的用武之地也很少了，这里就不再讲了！

 

 

ps:附件中我上传了一个比较不错的Data Structure Visualzation工具，是一个jar包运行java -jar 执行。对于分析与理解数据结构方面的问题相当有帮助。