JDK学习之LinkedList

1.先看下LinkedList 的继承关系：

 

 

2. 我们看到其主要实现了List,Queue接口，通过继承一个模板类AbstractSequentialList来实现链表，首先看下成员变量：

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

 

可以看到，有两个成员变量，一个是Entry-静态内部类,还有一个size，代表链表的实际大小，看下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;
	}
    }

 

是一个静态内部类，包含三个成员变量，element-数据项，next-指向下一条数据项，previous-指向前一条数据项，可以看出这是一个双向链接，每个节点

都会指向前一个节点和后一个节点。

这里简要说明一下为什么要使用静态内部类：

摘自网络：

静态内部类的实例不会自动持有外部类的特定实例的引用, 因此在创建内部类的实例时, 不必创建外部类的实例.

 静态内部类可以直接访问外部类的静态成员, 如果要访问外部类的实例成员, 就必须通过外部类的实例去访问

静态内部类中可以定义静态成员和实例成员

 客户类可以通过完整的类名直接访问静态内部类的静态成员. 

 

那这里，我认为是方便外部类访问，同时因为不包含任何方法，可以不用拿出来单独形成一个类，其他的好处，暂时还没看出来:(

 

下边重点看下几个方法的实现：

增加一条记录，add(E o)，实现代码：

 

    public boolean add(E o) {
	addBefore(o, header);
        return true;
    }

 

 

 内部调用了addBefore，再看addBefore的实现方式：

    private Entry<E> addBefore(E o, Entry<E> e) {

	//创建一个新的Entry实例
	Entry<E> newEntry = new Entry<E>(o, e, e.previous);

	//将header前一条数据的next指向newEntry，同时把header的previous指向newEntry,
	newEntry.previous.next = newEntry;
	newEntry.next.previous = newEntry;

	//长度和修改计数递增
	size++;
	modCount++;
	return newEntry;
    }

 在指定位置添加：

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

  

 

 

传递参数为：待添加的数据项O和header引用，详细分析参见注释，这里我们可以清晰的看到如何在一个链表结构中添加一条记录。

删除一条记录，remove(Object c)：

 public boolean remove(Object o) {
     //判断插入数据项是否为null
        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;
    }

 

 再看 remove(e)方法：

 private E remove(Entry<E> e) {
   if (e == header)
       throw new NoSuchElementException();
       //提取待删除数据作为返回值
          E result = e.element;
          /*将待删除数据的next付给前一条数据项的next
           * 将待删除数据的previous指向后一条数据previous
           * 同时释放待删除数据项的next和previous链接，是否element
           */
          
   e.previous.next = e.next;
   e.next.previous = e.previous;
          e.next = e.previous = null;
          e.element = null;
          //总条数size和修改计数递减
   size--;
   modCount++;
          return result;
}

 

 这里需要注意的是我们需要释放待删除节点的next和previous链接 ，以便于JVM在适当的时候进行垃圾回收。

获取数据,get(int index)：

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

 

 

 我们看下entry方法：

	  private Entry<E> entry(int index) {
		  //判断边界--前置条件判断
	        if (index < 0 || index >= size)
	            throw new IndexOutOfBoundsException("Index: "+index+
	                                       ", Size: "+size);
	        //如果index小于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;
	    }

 

这里我们看到在链表中取值时，需要遍历整个链表，相对于ArrayList的随机访问，会有所缓慢

 

最后看下contails(Object o)

    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

 看下indexOf(Object c)

 

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

 

 

 这里分两种情况进行遍历，跟删除是相同的。

 

3.典型应用：

暂无

4，优点与缺点

优点：

LinkedList的中间插入或删除一个元素的开销是固定的

缺点：

 LinkedList不支持高效的随机元素访问

 

最后，我感觉平时做项目ArrayList还是相对比较常用，LinkedList很少用，不知道有没有人在实际项目中使用过LinkedList ，切实的体会

到两者之间的差异，而不是向我最后分析的优缺点那样 都是些理论写的说辞，希望大家补充，谢谢。