LinkedList源码总结

双向链表：http://student.zjzk.cn/course_ware/data_structure/web/xianxingbiao/xianxingbiao2.3.3.htm

源码解析1：http://www.iteye.com/topic/1115828

2： http://blog.csdn.net/moreevan/article/details/6783801

 

 

LinkedList属于一个双向循环的链表，其内部是用一个Entry来维护的

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

默认构造函数：

public LinkedList() {
        header.next = header.previous = header;
    }

 

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

 

  element:当前节点的值

  previous：指向当前节点的前一个节点

  next：指向当前节点的后一个节点

 

public E get(int index) {
        return entry(index).element;
    }

 

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

 

 /**  
 *将元素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;  
     }  
   
   
 /** 
 *删除给定的结点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;  
     }  
   
   
   
 /**  
 *从表头开始遍历，返回此元素在表中的第一个位置 
      */  
     public int indexOf(Object o) {  
         int index = 0;  
         if (o==null) { //如果传入的元素是null，则不能调用 eqauls方法进行比较  
             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;  
     }  

public int lastIndexOf(Object o) {
        int index = size;
        if (o==null) {
            for (Entry e = header.previous; e != header; e = e.previous) {
                index--;
                if (e.element==null)
                    return index;
            }
        } else {
            for (Entry e = header.previous; e != header; e = e.previous) {
                index--;
                if (o.equals(e.element))
                    return index;
            }
        }
        return -1;
    }
   
 /** 
 *默认的添加动作，可以看到这个方法是把新元素添加 到表尾 
 */  
 public boolean add(E e) {  
        addBefore(e, header); //加到头结点之前 ，即表尾  
         return true;  
     }  
   
 /** 
 *默认的删除动作是删除链表的第一个元素，所以说在默认情况下，LinkedList其实扮*演的是一个队列的角色 
 */  
 public E remove() {  
         return removeFirst();  
     }  

//LinkedList是如何序列化和反序列化的

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
	// Write out any hidden serialization magic
	s.defaultWriteObject();

        // Write out size
        s.writeInt(size);

	// Write out all elements in the proper order.
        for (Entry e = header.next; e != header; e = e.next)
            s.writeObject(e.element);
    }

    /**
     * Reconstitute this <tt>LinkedList</tt> instance from a stream (that is
     * deserialize it).
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
	// Read in any hidden serialization magic
	s.defaultReadObject();

        // Read in size
        int size = s.readInt();

        // Initialize header
        header = new Entry<E>(null, null, null);
        header.next = header.previous = header;

	// Read in all elements in the proper order.
	for (int i=0; i<size; i++)
            addBefore((E)s.readObject(), header);
    }

 

注意：

注意entry的循环：

 for (Entry e = header.previous; e != header; e = e.previous) {}

 新节点的创建：

Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);

此时新加节点已知道其前后节点，但其前节点并不知道后节点发生变化，后节点也不知道前节点发生变化，所以分别将新节点赋给他们。

 

 

注意头结点的初始化：  

public LinkedList() {   
       header.next = header.previous = header;   
    }  

 

 

 由index获取节点的entry(int index) 方法...

 

 

ArrayList中主要用到以下方法：

public static  T[] copyOf(T[] original, int newLength) {
    Object[] Arrays.copyOf(elementData, size);
    从数组elementData中复制size个元素到返回的新数组,不足时补null,否则截取
//Copies the specified array, truncating or padding with nulls 

 
System提供了一个静态方法arraycopy(),我们可以使用它来实现数组之间的复制 。其函数原型是：

public static void arraycopy(Object src,int srcPos, Object dest,int destPos, int length)
        //list中的remove(int index)方法就是调用该方法

//src:源数组；    srcPos:源数组要复制的起始位置；
//dest:目的数组；    destPos:目的数组放置的起始位置；
//length:复制的长度。

 

注意：src and dest都必须是同类型或者可以进行转换类型的数组．

有趣的是这个函数可以实现自己到自己复制，比如：
int[] fun ={0,1,2,3,4,5,6};
System.arraycopy(fun,0,fun,3,3);
则结果为：{0,1,2,0,1,2,6};
实现过程是这样的，先生成一个长度为length的临时数组,将fun数组中srcPos到srcPos+length-1之间的数据拷贝到临时数组中，再执行System.arraycopy(临时数组,0,fun,3,3).