Java集合之LinkedList源码分析-学网-中国IT综合门户网站-提供健康,养生,留学,移民,创业,汽车等信息
Java集合之LinkedList源码分析
来源：互联网 更新时间： 2:58:51 责任编辑：鲁晓倩字体：
一、LinkedList简介
　　LinkedList是一种可以在任何位置进行高效地插入和移除操作的有序序列，它是基于双向链表实现的。
　　ps:这里有一个问题，就是关于实现LinkedList的数据结构是否为循环的双向链表，上网搜了有很多文章都说是循环的，并且有的文章中但是我看了源代码觉得应该不是循环的？
　　例如在删除列表尾部节点的代码：
private E unlinkLast(Node&E& l)
final E element = l.
final Node&E& prev = l.
l.item = null;
l.prev = null; // help GC
if (prev == null)
first = null;
prev.next = null;
modCount++;
　　这里删除尾节点l后，将l前面的节点prev的next置为null，而并没有指向head节点。不知道是不是因为代码版本的原因(我的源代码是在下载的jdk1.8.0_45文件中获取的)，如果读者看到知道原因，希望能够帮忙解答！
　　在源码中定义了节点的基本结构：
private static class Node&E& {
//表示该节点包含的值
Node&E& //表达当前节点的下一个节点
Node&E& //表示当前节点的上一个节点
Node(Node&E& prev, E element, Node&E& next) {
this.item =
this.next =
this.prev =
　　LinkedList的类图如下所示：
LinkedList&是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList&实现&List&接口，能对它进行队列操作。LinkedList&实现&Deque&接口，即能将LinkedList当作双端队列使用。LinkedList&实现了Cloneable接口，即覆盖了函数clone()，能克隆。LinkedList&实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。LinkedList&是非同步的。
二、LinkedList源码分析
1 public class LinkedList&E& extends AbstractSequentialList&E& implements List&E&, Deque&E&, Cloneable, java.io.Serializable
//实现Serilizable接口时，将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中。
transient int size = 0;
//指向首节点
transient Node&E&
//指向最后一个节点
transient Node&E&
//构建一个空列表
public LinkedList() {
//构建一个包含集合c的列表
public LinkedList(Collection&? extends E& c) {
addAll(c);
//将节点值为e的节点作为首节点
private void linkFirst(E e) {
final Node&E& f =
//构建一个prev值为null,next为f,节点值为e的节点
final Node&E& newNode = new Node&&(null, e, f);
//将newNode作为首节点
first = newN
//如果newNode后面没有节点就将newNode作为最后一个节点
if (f == null)
last = newN
//否则就将newNode赋给其prev
f.prev = newN
//列表长度加一
modCount++;
//将节点值为e的节点作为最后一个节点
void linkLast(E e) {
final Node&E& l =
//构建一个prev值为l,next为null,节点值为e的节点
final Node&E& newNode = new Node&&(l, e, null);
last = newN
if (l == null)
first = newN
l.next = newN
modCount++;
//在非空节点succ之前插入节点e
void linkBefore(E e, Node&E& succ) {
final Node&E& pred = succ.
//将succ前面的节点和succ作为其prev和next
final Node&E& newNode = new Node&&(pred, e, succ);
//然后将newNode作为succ的prev
succ.prev = newN
//如果原来succ是首节点，则将newNode设置为首节点
if (pred == null)
first = newN
pred.next = newN
modCount++;
//释放非空的首节点f
private E unlinkFirst(Node&E& f) {
final E element = f.
final Node&E& next = f.
f.item = null;
f.next = null; // help GC
//将first节点后面的节点设为首节点
if (next == null)
last = null;
next.prev = null;
modCount++;
//释放非空的尾节点l
private E unlinkLast(Node&E& l) {
final E element = l.
final Node&E& prev = l.
l.item = null;
l.prev = null; // help GC
if (prev == null)
first = null;
prev.next = null;
modCount++;
//删除非空节点x
E unlink(Node&E& x)
final E element = x.
final Node&E& next = x.
//x后面的节点
final Node&E& prev = x.
//x前面的节点
if (prev == null) {
prev.next =
x.prev = null;
if (next == null) {
next.prev =
x.next = null;
x.item = null;
modCount++;
//返回列表首节点元素值
public E getFirst() {
final Node&E& f =
if (f == null)
throw new NoSuchElementException();
//返列表尾节点元素值
public E getLast() {
final Node&E& l =
if (l == null)
throw new NoSuchElementException();
//移除首节点
public E removeFirst() {
final Node&E& f =
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
//删除尾节点
public E removeLast() {
final Node&E& l =
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
//在列表首部插入节点e
public void addFirst(E e) {
linkFirst(e);
//在列表尾部插入节点e
public void addLast(E e) {
linkLast(e);
//判断列表中是否包含有元素o
public boolean contains(Object o) {
return indexOf(o) != -1;
//返回列表长度大小
public int size() {
//在列表尾部插入元素
public boolean add(E e) {
linkLast(e);
return true;
//删除元素为o的节点
public boolean remove(Object o)
if (o == null) {
for (Node&E& x = x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
for (Node&E& x = x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
return false;
//将集合c中所有元素添加到列表的尾部
public boolean addAll(Collection&? extends E& c) {
return addAll(size, c);
//从指定的位置index开始，将集合c中的元素插入到列表中
public boolean addAll(int index, Collection&? extends E& c) {
//首先判断插入位置的合法性
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.
if (numNew == 0)
return false;
Node&E& pred,
if (index == size) {//说明在列表尾部插入集合元素
succ = null;
//否则，找到index所在的节点
succ = node(index);
pred = succ.
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E)
Node&E& newNode = new Node&&(pred, e, null);
if (pred == null)
first = newN
pred.next = newN
pred = newN
if (succ == null) {
pred.next =
succ.prev =
size += numN
modCount++;
return true;
//删除列表中所有节点
public void clear() {
for (Node&E& x = x != null; )
Node&E& next = x.
x.item = null;
x.next = null;
x.prev = null;
first = last = null;
modCount++;
//获取指定索引位置节点的元素值
public E get(int index) {
checkElementIndex(index);
return node(index).
//替换指定索引位置节点的元素值
public E set(int index, E element) {
checkElementIndex(index);
Node&E& x = node(index);
E oldVal = x.
return oldV
//在指定索引位置之前插入元素e
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
linkBefore(element, node(index));
//删除指定位置的元素
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
//判断指定索引位置的元素是否存在
private boolean isElementIndex(int index) {
return index &= 0 && index &
private boolean isPositionIndex(int index) {
return index &= 0 && index &=
//构建 IndexOutOfBoundsException详细信息
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//返回指定索引位置的节点
Node&E& node(int index) {
//此处是一个小技巧，当index&size/2时，从列表前半部分开始，否则从后半部分开始
if (index & (size && 1)) {
Node&E& x =
for (int i = 0; i & i++)
Node&E& x =
for (int i = size - 1; i & i--)
}//返回列表中第一次出现o的位置，若不存在则返回-1
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node&E& x = x != null; x = x.next) {
if (x.item == null)
for (Node&E& x = x != null; x = x.next) {
if (o.equals(x.item))
return -1;
//逆向搜索，返回第一出现o的位置，不存在则返回-1
public int lastIndexOf(Object o) {
int index =
if (o == null) {
for (Node&E& x = x != null; x = x.prev) {
if (x.item == null)
for (Node&E& x = x != null; x = x.prev) {
if (o.equals(x.item))
return -1;
//获取列表首节点元素值
public E peek() {
final Node&E& f =
return (f == null) ? null : f.
//获取列表首节点元素值，若为空则抛异常
public E element() {
return getFirst();
//检索首节点，若空则返回null,不为空则返回其元素值并删除首节点
public E poll() {
final Node&E& f =
return (f == null) ? null : unlinkFirst(f);
//检索首节点，若空则抛异常,不为空则返回其元素值并删除首节点
public E remove() {
return removeFirst();
//在列表尾部增加节点e
public boolean offer(E e) {
return add(e);
//在列表首部插入节点e
public boolean offerFirst(E e) {
addFirst(e);
return true;
//在列表尾部插入节点e
public boolean offerLast(E e) {
addLast(e);
return true;
public E peekFirst() {
final Node&E& f =
return (f == null) ? null : f.
//获取列表尾节点元素值
public E peekLast() {
final Node&E& l =
return (l == null) ? null : l.
public E pollFirst() {
final Node&E& f =
return (f == null) ? null : unlinkFirst(f);
public E pollLast() {
final Node&E& l =
return (l == null) ? null : unlinkLast(l);
public void push(E e)
addFirst(e);
public E pop() {
return removeFirst();
//删除列表中第一出现o的节点
public boolean removeFirstOccurrence(Object o) {
return remove(o);
//逆向搜索，删除第一次出现o的节点
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node&E& x = x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
for (Node&E& x = x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
return false;
相关文章：
上一篇文章：下一篇文章：
最新添加资讯
24小时热门资讯
Copyright © 2004- All Rights Reserved. 学网 版权所有
京ICP备号-1 京公网安备02号Java容器（三）：LinkedList源码分析_ASP.NET技巧_动态网站制作指南
Java容器（三）：LinkedList源码分析
来源：人气：17
在LinkedList中，共有三个成员变量，size，first和last
transient int size = 0; //LinkedList的大小
transient Node&E& //链表中第一个节点
transient Node&E& //链表中最后一个节点
Node类是ListedList的一个内部类，其结构如下：
ivate static class Node&E& {
Node(Node&E& prev, E element, Node&E& next) {
this.item =
this.next =
this.prev =
item表示当前节点的值，next引用指向下一个节点，prev引用指向前一个节点，这就是双向链表的特征
二、构造方法
//构造一个无参
public LinkedList() {
public LinkedList(Collection&? extends E& c) {
addAll(c);
容器第一篇总结篇说过，所有实现Collection接口的容器类，都一定有两个构造方法，一个无参，一个有参（参数为所有实现Collection的对象）
LinkedList(Collection& ? extends E& c) ：构造一个包含指定 collection 中的元素的列表，这些元素按其 collection 的迭代器返回的顺序排列
首先调用this()生成一个空的LinkedList对象，然后调用addAll，把参数的Collection添加到LinkedList中，addAll（Collection& ? extends E& c）代码如下：
public boolean addAll(Collection&? extends E& c) {
return addAll(size, c);
addAll方法有两个（一参和二参）：
addAll(Collection& ? extends E& c) ： 把Collection添加到LinkedList的尾端
addAll(int index, Collection& ? extends E& c)：把Collection添加到LinkedList的index位置
在构造方法中调用一参的addAll，从而调用二参的addAll，此时index为成员变量size，即把Collection添加到LinkedList的尾端
public boolean addAll(int index, Collection&? extends E& c) {
//检查index位置是否超出边界
checkPositionIndex(index);
//把Collection转为数组
Object[] a = c.toArray();
int numNew = a.
//如果Collection为空，返回false，表示添加失败
if (numNew == 0)
//pred指向前一个节点，succ指向下一个节点
Node&E& pred,
//如果在链尾添加，下一个节点为空，pred指向当前链表最后一个节点
if (index == size) {
如果不在链尾添加，调用node（index），内部通过遍历离链表取得index位置的节点，并把succ指向index位置的节点，pred指向index位置节点的前一个节点
succ = node(index);
pred = succ.
//执行插入，注意pred
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E)
Node&E& newNode = new Node&&(pred, e, null);
//如果把o插入到链头
if (pred == null)
first = newN
//让index位置的前一个节点的next指向包含o的新节点
pred.next = newN
//把newNode节点作为pred
pred = newN
//更新pred和succ
if (succ == null) {
pred.next =
succ.prev =
//增加LinkedList的大小
size += numN
//LinkedList用modCount变量来记录链表改变的次数
modCount++;
node(index)方法非常重要，LinkedList很多方法都是通过node(index)才取得index位置的节点，从而进一步操作：
例如set（int index， E e），就是要通过node（index）取得index位置的node，从而设置node.item = e；
//遍历链表从而取得index位置节点
Node&E& node(int index) {
if (index & (size && 1)) {
Node&E& x =
for (int i = 0; i & i++)
Node&E& x =
for (int i = size - 1; i & i--)
这里是数据结构链表的内容，有数据结构基础的人完全可以看懂
三、增加方法的核心
add(E e) ：将指定元素添加到此列表的结尾
add(int index, E element)：在此列表中指定的位置插入指定的元素
当index == size时，两个方法等效，都是添加到链表的尾部
接下来看看add(int index, E element)的：
public void add(int index, E element) {
checkPositionIndex(index);
//当在链尾添加时，调用linkLast(element)，add(E e) 方法内部也是调用linkLast(element)
if (index == size)
linkLast(element);
//如果不是在链尾添加，则把element添加到index位置节点前
linkBefore(element, node(index));
//succ是index位置的节点
void linkBefore(E e, Node&E& succ) {
// assert succ !=
//pred指向要添加的位置的前一个节点
final Node&E& pred = succ.
//创建一个新节点
final Node&E& newNode = new Node&&(pred, e, succ);
//把新节点插入到index位置前
succ.prev = newN
//如果是在链表头部添加
if (pred == null)
first = newN
//把新节点插入到index位置前一个节点的后面，这样就把新节点插入到了index位置
pred.next = newN
//修改次数加1
modCount++;
除了linkBefore，linkFirst和linkLast也是其它增加方法的核心
例如addFirst内部是调用linkFirst，push()也是调用linkFirst，addLast()内部调用的是linkLast
这三个方法都比较简单，就不再叙述
四、删除方法的核心
remove(Object o)：从此列表中移除首次出现的指定元素（如果存在）
public boolean remove(Object o) {
if (o == null) {
for (Node&E& x = x != x = x.next) {
if (x.item == null) {
unlink(x);
for (Node&E& x = x != x = x.next) {
if (o.equals(x.item)) {
unlink(x);
这段代码很简单，就是遍历链表，把删除掉第一次出现参数值得节点，如果找不到，返回false
remove调用了unlink(x)方法：
E unlink(Node&E& x) {
// assert x !=
final E element = x.
final Node&E& next = x.
final Node&E& prev = x.
if (prev == null) {
prev.next =
if (next == null) {
next.prev =
modCount++;
这里的删除逻辑跟数据结构中的链表的操作一样，非常简单
总得来看，LinkedList的实现是很简单的，只要数据结构过关，完全可以自己实现一个
优质网站模板java集合类——LinkedList类 -
- ITeye技术网站
博客分类：
LinkedList是实现List接口。LinkedList类有很多方法，对头尾的操作都提供了方法。如addFirst(),addLast()等等。LinkedList与Stack的顺序刚好相反，是先进先出的。
import java.util.LinkedL
public class LinkedListTest {
* @param args
public static void main(String[] args) {
LinkedList&String& linkedList = new LinkedList&String&();
linkedList.add("1");
linkedList.add("2");
linkedList.add("3");
linkedList.add("4");
linkedList.addFirst("add first");
linkedList.addLast("add last");
System.out.println(linkedList);
linkedList.offerFirst("offer first");
linkedList.offerLast("offer last");
System.out.println(linkedList);
linkedList.offer("offer");
System.out.println(linkedList);
System.out.println(linkedList.pop());
System.out.println(linkedList);
System.out.println(linkedList.getLast());
}
输出：
[add first, 1, 2, 3, 4, add last]
[offer first, add first, 1, 2, 3, 4, add last, offer last]
[offer first, add first, 1, 2, 3, 4, add last, offer last, offer]
offer first
[add first, 1, 2, 3, 4, add last, offer last, offer]
offer
从结果看，个人认为，没有指定位置的add()和addFirst(),offer(),offerFirst()是基本没什么区别，都是在最前面出入对象，addLast()和offerLast()也基本没什么区别。
还有element()和peek()方法的作用完全一样。
为什么要提供那么多相同作用的方法呢？
因为LinkedList实现了一系列的接口才导致这种情况出现的。
以上均为自己的理解，如有不对，忘君指教，不胜感激。。。
Javaloverlover
浏览: 226799 次
来自: 杭州
正在想这个问题，看到了你的回答，谢谢！
我不知道网上这类maven+jetty热部署是怎么来的，好多人 ...
个人还是比较喜欢 sass语法
更接近ruby
可不可以自己独立配置插件的方法，不要放在plugins文件夹里 ...