LinkedList源码剖析

小咪咪 2022-06-04 06:42 243阅读 0赞

简介

LinkedList是基于双向循环链表（从源码中可以很容易看出）实现的，除了可以当做链表来操作外，它还可以当做栈、队列和双端队列来使用。  
由于是链表结构,LinkedList具有查找快,增删快的特点;  
所有操作都是按照双重链接列表的需要执行的。在列表中，索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。同时，与ArrayList一样此实现不是同步的。  
成员变量

在LinkedList中提供了两个基本属性size、header。 其中size表示的LinkedList的大小，header表示链表的表头，Entry为节点对象。从Entry对象的定义就可以看出 LinkedList是双向循环链表结构。并且可知链表的头结点是不存放数据的。

private transient Entry header = new Entry(null, null, null);  
private transient int size = 0;  
private static class Entry \{  
E element; //元素节点  
Entry next; //下一个元素  
Entry previous; //上一个元素

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

\}  
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
构造方法

LinkedList()：构造一个空列表。  
LinkedList(Collection  
添加元素

add(E e): 将指定元素添加到此列表的结尾。  
public boolean add(E e) \{  
addBefore(e, header);  
return true;  
\}  
//该方法调用addBefore方法，然后直接返回true  
private Entry addBefore(E e, Entry entry) \{  
//利用Entry构造函数构建一个新节点 newEntry，  
Entry newEntry = new Entry(e, entry, entry.previous);  
//修改newEntry的前后节点的引用，确保其链表的引用关系是正确的  
newEntry.previous.next = newEntry;  
newEntry.next.previous = newEntry;  
//容量+1  
size++;  
//修改次数+1  
modCount++;  
return newEntry;  
\}  
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
add(int index, E element)：在此列表中指定的位置插入指定的元素。  
addAll(Collection  
/\*\*  
\* 添加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序。  
\*/  
public boolean addAll(Collection