LinkedList作为一种常用的List，是除了ArrayList之外最有用的List。其同样实现了List接口，但是除此之外它同样实现了Deque接口，而Deque是一个双端队列接口，其继承自Queue，所以LinkedList同样可以用来模拟队列，栈以及双端队列。
一.基本用法 因为LinkedList是基于链表实现的，所以注定其插入和删除操作速度要快于ArrayList，但是由于其是链表结构，所以其随机访问查找检索速度慢于基于数组的ArrayList。
这里先主要说一下LinkedList的基本用法，以及模拟队列，模拟栈，模拟双端队列的常用方法。
1.LinkedList,List用法List<String> myList=newLinkedList<String>();
（1）//增加元素String s="myString"myList.add(s);//这里等同于在链表尾端增加元素addLast(e)myList.add(1,s);//在指定位置插入元素（2）//获取指定位置的元素String getString=myList.get(10)//获取链表第11处元素，从头计算（3）//删除元素myList.remove(2)//删除链表第3个元素（4）//clear清空链表myList.clear()
(5)isEmpty(),//判断list是否为空
2.LinkedList模拟队列Queue<String> myQueue=newLinkedList<String>();
(1)//添加元素到到队尾myQueue.offer(myString);
myQueue.add(myString);
(2)检索但不删除队首元素
String head=myQueue.peek();//若为空，返回nullString head=myQueue.element();//若队列为空，抛出NoSuchElementException(3)取出并且删除队首元素
String head=myQueue.poll();//若为空，返回nullString head=myQueue.remove();//若队列为空，抛出NoSuchElementException//综上，LinkedList通过在链表尾插入元素，链表首取出元素,模拟了先进先出FIFO的队列，但是//这里的队列是单向的
3.LinkedList模拟栈Stack操作Deque<String> stack=newLinkedList<String>();//（1）进栈操作stack.push(myString);//(2)出栈操作，删除并且取出stack.pop();//(3)若是检索不删除则还用peekstack.peek();//LinkedList通过在队首插入元素，队首取出元素，模拟stack的先进后出操作
4.LinkedList模拟双端队列Deque操作Deque<String> deque=newLinkedList<String>();//(1)队首添加元素deque.offerFirst(myString);
deque.addFirst(myString);//(2)队尾添加元素deque.offerLast(myString);
deque.addLast(myString);//(3)检索但不删除队首元素String first=deque.peekFirst();
first=deque.getFirst();//(4)检索但不删除队尾元素String last=deque.peekLast();
last=deque.getLast();//(5)取出并删除队首元素deque.pollFirst();
deque.removeFirst();//(6)取出并删除队尾元素deque.pollLast();
deque.removeLast();//这样LinkedList通过操作链表队首队尾就实现了双端队列
5.LinkedList迭代遍历//(1)for each 循环List<String> list=newArrayList<String>();for(String s:list){////}//(2)iterator迭代器Iterator<String> it=list.iterator();while(it.hasNext()){
it.next();
}//(3)同时List还提供了ListIterator接口，拥有反向正向迭代ListIterator<String> lit=list.listIterator();while(lit.hasNext()){
it.next();
}//正向迭代while(it.hasprevious()){
it.PRevious();
}//反向迭代//值得注意的是，以前可能忽视了，listIterator迭代器同时提供了增删改的功能//add(),在指定位置插入一个元素,当前迭代的前面插入//set(E，e),修改当前迭代为指定元素//remove();删除上一次迭代
二.JDK源码分析 这里的JDK是基于JDK1.8的源码。
1.定义，LinkedList类定义publicclassLinkedList<E>extendsAbstractSequentialList<E>implementsList<E>, Deque<E>, Cloneable,java.io.Serializable//继承了AbstractSequentialList抽象类，提供了实现List接口的基本实现//Deque接口， A linear collection that supports element insertion and removal at both ends.//The name <i>deque</i> is short for "double ended queue" and is usually pronounced "deck"publicinterfaceDeque<E>extendsQueue<E>//所以这里就可以知道为什么LinkedList可以模拟队列，双端队列，以及Stack栈了
2.重要属性transientintsize = 0;//记录List大小//接下来分别是两个Node引用，分别指向链表头和链表尾transientNode<E>first;transientNode<E>last;//接下就是链表中节点的定义，可以看到JDK1.8把节点都统一为Node了privatestaticclassNode<E>{
E item;
Node<E>next;
Node<E>prev;
Node(Node<E> prev, E element, Node<E>next) {this.item =element;this.next =next;this.prev =prev;
}
}//及其简单的定义，双向链表，向前链接，向后向后链接，元素
3.构造器//（1）无参构造器publicLinkedList() {
}//（2）带有集合的构造器publicLinkedList(Collection<?extendsE>c) {this();
addAll(c);
}//调用addAll将现有集合内所有元素放到LinkedList中publicbooleanaddAll(Collection<?extendsE>c) {returnaddAll(size, c);
}//将整个集合c中的元素加入链表中publicbooleanaddAll(intindex, Collection<?extendsE>c) {
checkPositionIndex(index);
Object[] a=c.toArray();intnumNew =a.length;if(numNew == 0)returnfalse;
Node<E>pred, succ;//插入到结尾if(index ==size) {
succ=null;
pred=last;
}else{//插入到中间//这里succ则为原来在index位置的节点succ =node(index);
pred=succ.prev;
}for(Object o : a) {
@SuppressWarnings("unchecked") E e =(E) o;//创建新的Node节点，其中newNode的前向节点为pred，后向节点没有定义Node<E> newNode =newNode<>(pred, e,null);//pred==null，则此节点为首节点if(pred ==null)
first=newNode;else//当节点不是首节点时，定义前向节点的后向节点为当前节点pred.next =newNode;
pred=newNode;
}if(succ ==null) {
last=pred;
}else{//将原来的链表加入pred.next =succ;
succ.prev=pred;
}
size+=numNew;
modCount++;returntrue;
}
4.常用方法源码分析(1). add(E e)//默认add方法，将节点放入链表尾部，同offer方法publicbooleanadd(E e) {
linkLast(e);returntrue;
}//将节点放入链表尾部voidlinkLast(E e) {finalNode<E> l =last;finalNode<E> newNode =newNode<>(l, e,null);
last=newNode;//同样要判断当前节点是不是头节点if(l ==null)
first=newNode;elsel.next=newNode;
size++;
modCount++;
}
//将元素链接放到指定位置publicvoidadd(intindex, E element) {//该方法主要是查看index是否合法，在范围内，否则抛出异常checkPositionIndex(index);//当index是末尾时，直接链接到结尾if(index ==size)
linkLast(element);else//否则找到index位置的原来节点，插入到其前面linkBefore(element, node(index));
}//取出index位置的node节点Node<E> node(intindex) {//assert isElementIndex(index);//这里有一处非常值得注意//size>>1表示的是向右移位1，该方法其实相当于除以2，去得一半的值//当index<size/2时，表明index在前半部分，则正序找//否则在后半部分，则倒序查找,节省了时间if(index < (size >> 1)) {
Node<E> x =first;for(inti = 0; i < index; i++)
x=x.next;returnx;
}else{
Node<E> x =last;for(inti = size - 1; i > index; i--)
x=x.prev;returnx;
}
}//linkBefore 方法//这个方法是将节点插入到succ节点的前面，//由于是在指定位置插入节点，所以要将原来的节点链接到新节点后面voidlinkBefore(E e, Node<E>succ) {//assert succ != null;finalNode<E> pred =succ.prev;finalNode<E> newNode =newNode<>(pred, e, succ);
succ.prev=newNode;if(pred ==null)
first=newNode;else//这里一定要注意，双向链表，一定要将pred节点的next节点定义为当前节点pred.next =newNode;
size++;
modCount++;
}
(2).addLast()，addFirst()方法addLast()等同于add()方法，addFirst是在链表头插入节点
//将新节点放入到链表尾部publicvoidaddLast(E e) {
linkLast(e);
}//在链表头插入节点publicvoidaddFirst(E e) {
linkFirst(e);
}//将新节点设置为首节点privatevoidlinkFirst(E e) {finalNode<E> f =first;finalNode<E> newNode =newNode<>(null, e, f);
first=newNode;if(f ==null)
last=newNode;elsef.prev=newNode;
size++;
modCount++;
}
(3). getFirst(),getLast()获取头节点和尾节点/*** Returns the first element in this list.
*
*@returnthe first element in this list
*@throwsNoSuchElementException if this list is empty为空会抛出异常*/publicE getFirst() {finalNode<E> f =first;if(f ==null)thrownewNoSuchElementException();returnf.item;
}/*** Returns the last element in this list.
*
*@returnthe last element in this list
*@throwsNoSuchElementException if this list is empty*/publicE getLast() {finalNode<E> l =last;if(l ==null)thrownewNoSuchElementException();returnl.item;
}
(4). removeFirst()，removeLast()方法/*** Removes and returns the first element from this list.
*
*@returnthe first element from this list
*@throwsNoSuchElementException if this list is empty*/
publicE removeFirst() {finalNode<E> f =first;if(f ==null)thrownewNoSuchElementException();returnunlinkFirst(f);
}//unlinkFirst（）即解开并返回头节点privateE unlinkFirst(Node<E>f) {//assert f == first && f != null;finalE element =f.item;finalNode<E> next =f.next;
f.item=null;//及时清除f.next =null;//help GCfirst =next;if(next ==null)
last=null;//此时链表为空elsenext.prev=null;
size--;
modCount++;returnelement;
}
/*** Removes and returns the last element from this list.
*
*@returnthe last element from this list
*@throwsNoSuchElementException if this list is empty*/publicE removeLast() {finalNode<E> l =last;if(l ==null)thrownewNoSuchElementException();returnunlinkLast(l);
}/*** Unlinks non-null last node l.*/privateE unlinkLast(Node<E>l) {//assert l == last && l != null;finalE element =l.item;finalNode<E> prev =l.prev;
l.item=null;
l.prev=null;//help GClast =prev;if(prev ==null)
first=null;elseprev.next=null;
size--;
modCount++;returnelement;
}
(5). contains(Object o)
查看链表中是否存有某个元素publicbooleancontains(Object o) {returnindexOf(o) != -1;
}//indexOf（）这个方法返回对象O在链表中的位置publicintindexOf(Object o) {intindex = 0;if(o ==null) {for(Node<E> x = first; x !=null; x =x.next) {if(x.item ==null)returnindex;
index++;
}
}else{//同样调用的也是equals方法判断两个值是否相等for(Node<E> x = first; x !=null; x =x.next) {if(o.equals(x.item))returnindex;
index++;
}
}return-1;//没有找到时返回-1}
(6). get（int index）获取指定index位置的元素
/*** Returns the element at the specified position in this list.
*
*@paramindex index of the element to return
*@returnthe element at the specified position in this list
*@throwsIndexOutOfBoundsException {@inheritDoc}*/publicE get(intindex) {
checkElementIndex(index);returnnode(index).item;
}
(7).set（int index,E element）set修改指定位置的元素
//主要还是定位获取节点之后再修改publicE set(intindex, E element) {
checkElementIndex(index);
Node<E> x =node(index);
E oldVal=x.item;
x.item=element;returnoldVal;
}
(8).搜索元素所在位置indexOf(Object o),lastIndexOf(Object o)分为正向indexOf(),即第1次插入时匹配的元素位置和反向lastIndexOf()，即最后一次插入匹配的位置
//indexOf（）这个方法返回对象O在链表中的位置publicintindexOf(Object o) {intindex = 0;if(o ==null) {for(Node<E> x = first; x !=null; x =x.next) {if(x.item ==null)returnindex;
index++;
}
}else{//同样调用的也是equals方法判断两个值是否相等for(Node<E> x = first; x !=null; x =x.next) {if(o.equals(x.item))returnindex;
index++;
}
}return-1;
}//反向查找//有index的时候，必然会有lastIndexOfpublicintlastIndexOf(Object o) {intindex =size;if(o ==null) {for(Node<E> x = last; x !=null; x =x.prev) {
index--;if(x.item ==null)returnindex;
}
}else{for(Node<E> x = last; x !=null; x =x.prev) {//这里值得注意的是，index先--，因为你是从size位置开始的，所以要先--index--;if(o.equals(x.item))returnindex;
}
}return-1;
}
5.模拟Queue操作源码分析再次强调一次这里queue先进先出，在队尾入队，队首出队
(1).首先是检索队首，但不出队的操作，peek(),element()/*** Retrieves, but does not remove, the head (first element) of this list.
*
*@returnthe head of this list, or {@codenull} if this list is empty
*@since1.5*/最常用操作，peek()，若为空会，返回nullpublicE peek() {finalNode<E> f =first;return(f ==null) ?null: f.item;
}/*** Retrieves, but does not remove, the head (first element) of this list.
*
*@returnthe head of this list
*@throwsNoSuchElementException if this list is empty
*@since1.5*///若为空会抛出异常publicE element() {returngetFirst();
}//再回头看一眼getFirst(),publicE getFirst() {finalNode<E> f =first;if(f ==null)thrownewNoSuchElementException();//抛出异常returnf.item;
}
(2).出队操作，取出队首元素,poll(),remove()/*** Retrieves and removes the head (first element) of this list.
*
*@returnthe head of this list, or {@codenull} if this list is empty
*@since1.5*/publicE poll() {finalNode<E> f =first;return(f ==null) ?null: unlinkFirst(f);
}/*** Retrieves and removes the head (first element) of this list.
*
*@returnthe head of this list
*@throwsNoSuchElementException if this list is empty
*@since1.5*/publicE remove() {returnremoveFirst();
}publicE removeFirst() {finalNode<E> f =first;if(f ==null)thrownewNoSuchElementException();returnunlinkFirst(f);
}
(3).队尾插入元素offer()/*** Adds the specified element as the tail (last element) of this list.
*
*@parame the element to add
*@return{@codetrue} (as specified by {@linkQueue#offer})
*@since1.5*/publicbooleanoffer(E e) {returnadd(e);
}
6. 模拟双端队列Deque操作源码分析双端队列，其实就是整条链表头尾都操作，有了前面的基础，这里应该非常简单了
(1).在队首，队尾插入元素，offerFirst(),offerLast()其实就是分别调用addFirst(E e)和addLast(E e)方法
/*** Inserts the specified element at the front of this list.
*
*@parame the element to insert
*@return{@codetrue} (as specified by {@linkDeque#offerFirst})
*@since1.6*/publicbooleanofferFirst(E e) {
addFirst(e);returntrue;
}/*** Inserts the specified element at the end of this list.
*
*@parame the element to insert
*@return{@codetrue} (as specified by {@linkDeque#offerLast})
*@since1.6*/publicbooleanofferLast(E e) {
addLast(e);returntrue;
}
(2).检索队首,队尾元素，但不出队peekFirst(),peekLast()/*** Retrieves, but does not remove, the first element of this list,
* or returns {@codenull} if this list is empty.
*
*@returnthe first element of this list, or {@codenull}
* if this list is empty
*@since1.6*/publicE peekFirst() {finalNode<E> f =first;return(f ==null) ?null: f.item;
}/*** Retrieves, but does not remove, the last element of this list,
* or returns {@codenull} if this list is empty.
*
*@returnthe last element of this list, or {@codenull}
* if this list is empty
*@since1.6*/publicE peekLast() {finalNode<E> l =last;return(l ==null) ?null: l.item;
}
(3). 出队操作，取出队首，队尾元素，pollFirst(),pollLast()/*** Retrieves and removes the first element of this list,
* or returns {@codenull} if this list is empty.
*
*@returnthe first element of this list, or {@codenull} if
* this list is empty
*@since1.6*/publicE pollFirst() {finalNode<E> f =first;return(f ==null) ?null: unlinkFirst(f);
}/*** Retrieves and removes the last element of this list,
* or returns {@codenull} if this list is empty.
*
*@returnthe last element of this list, or {@codenull} if
* this list is empty
*@since1.6*/publicE pollLast() {finalNode<E> l =last;return(l ==null) ?null: unlinkLast(l);
}
7. 模拟栈Stack操作源码分析值得注意的是Stack操作一直是对链表头进行操作，不管是进栈push还是出栈pop方法
/*** Pushes an element onto the stack represented by this list. In other
*Words, inserts the element at the front of this list.
*
* <p>This method is equivalent to {@link#addFirst}.
*
*@parame the element to push
*@since1.6*/publicvoidpush(E e) {
addFirst(e);
}/**出栈操作，若栈为空会抛出异常* Pops an element from the stack represented by this list. In other
* words, removes and returns the first element of this list.
*
* <p>This method is equivalent to {@link#removeFirst()}.
*
*@returnthe element at the front of this list (which is the top
* of the stack represented by this list)
*@throwsNoSuchElementException if this list is empty
*@since1.6*/publicE pop() {returnremoveFirst();
}
8. 最后再看一下LinkedList的迭代器ListIteratorlistIterator()方法，返回ListIterator迭代器 ，这个不带参数listIterator方法是 AbstractlList中的方法
publicListIterator<E>listIterator() {returnlistIterator(0);
}//从第几个链表节点开始迭代publicListIterator<E> listIterator(intindex) {
checkPositionIndex(index);returnnewListItr(index);
}
//ListItr是其中的一个内部类，该类是一个List迭代器privateclassListItrimplementsListIterator<E>{privateNode<E> lastReturned;//永远记录上一次迭代的节点privateNode<E>next;privateintnextIndex;//这个变量非常重要，能够查看迭代过程中是否修改了List，使得迭代过程中的数据与原List中的数据一致//Fail_fast原理，不一致时立马失败抛出异常privateintexpectedModCount =modCount;//这里给出index，则可以看成是从哪个节点开始迭代ListItr(intindex) {//assert isPositionIndex(index);next = (index == size) ?null: node(index);
nextIndex=index;
}//正向迭代，向后迭代publicbooleanhasNext() {returnnextIndex <size;
}publicE next() {//每次迭代前都检查一下，是否修改了原List，若原List自行修改，而没有经过ListItr迭代器修改则将抛出异常//Fail-FastcheckForComodification();if(!hasNext())thrownewNoSuchElementException();
lastReturned=next;
next=next.next;
nextIndex++;returnlastReturned.item;
}//反向迭代，即向前迭代publicbooleanhasPrevious() {returnnextIndex > 0;
}publicE previous() {
checkForComodification();if(!hasPrevious())thrownewNoSuchElementException();
lastReturned= next = (next ==null) ?last : next.prev;
nextIndex--;returnlastReturned.item;
}//返回下标publicintnextIndex() {returnnextIndex;
}publicintpreviousIndex() {returnnextIndex - 1;
}//迭代操作时，唯一的增删改方式，值得注意的是这里的修改操作都是针对上一次的迭代//也就是调用next()得到元素，若要对这个变量进行修改，则可以进行修改//这种设计也十分合理，我只有得到元素我才知道我要对元素做什么publicvoidremove() {//当迭代过程中要想删除元素，一定要用迭代器的remove方法checkForComodification();if(lastReturned ==null)thrownewIllegalStateException();
Node<E> lastNext =lastReturned.next;
unlink(lastReturned);if(next ==lastReturned)
next=lastNext;elsenextIndex--;
lastReturned=null;//由于上面调用unlink时，modCount++；//所以为了下一次迭代不抛出异常，这里也要进行 expectedModCount++expectedModCount++;
}publicvoidset(E e) {if(lastReturned ==null)thrownewIllegalStateException();
checkForComodification();
lastReturned.item=e;
}//增也是增在next()后的元素之后publicvoidadd(E e) {
checkForComodification();
lastReturned=null;if(next ==null)
linkLast(e);elselinkBefore(e, next);
nextIndex++;
expectedModCount++;
}publicvoidforEachRemaining(Consumer<?superE>action) {
Objects.requireNonNull(action);while(modCount == expectedModCount && nextIndex <size) {
action.accept(next.item);
lastReturned=next;
next=next.next;
nextIndex++;
}
checkForComodification();
}////判断expectedModCount和modCount是否一致，以确保通过ListItr的修改操作正确的反映在LinkedList中finalvoidcheckForComodification() {if(modCount !=expectedModCount)thrownewConcurrentModificationException();
}
}
三.简单总结 LinkedList是十分常用的类，而且其方法实在太多了，而且其功能还狠多，之前老是记不住，这次掰开揉碎过一遍JDK源码，发现实现其实非常简单，但是里面有很多小技巧是值得学习的。所以阅读源码应该成为我今后学习的一个好习惯，任何框架任何技术，知其所以然才能融汇贯通。