Java容器（三）：LinkedList源码分析详解编程语言

在LinkedList中，共有三个成员变量，size，first和last

transient int size = 0; //LinkedList的大小 transient Node E  first; //链表中第一个节点 transient Node E  last; //链表中最后一个节点

Node类是ListedList的一个内部类，其结构如下：

 private static class Node 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; 

 } 

 }

item表示当前节点的值，next引用指向下一个节点，prev引用指向前一个节点，这就是双向链表的特征

//构造一个无参 public LinkedList() { 

} 

 

public LinkedList(Collection ? extends E  c) { this(); 

 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.length; //如果Collection为空，返回false，表示添加失败 if (numNew == 0) return false; 

 //pred指向前一个节点，succ指向下一个节点 

 Node E  pred, succ; //如果在链尾添加，下一个节点为空，pred指向当前链表最后一个节点 if (index == size) { 

 succ = null; 

 pred = last; 

 } else { /** 

 如果不在链尾添加，调用node（index），内部通过遍历离链表取得index位置的节点，并把succ指向index位置的节点，pred指向index位置节点的前一个节点 

 **/ 

 succ = node(index); 

 pred = succ.prev; 

 } 

 //执行插入，注意pred for (Object o : a) { @SuppressWarnings( unchecked ) E e = (E) o; 

 Node E  newNode = new Node (pred, e, null); //如果把o插入到链头 if (pred == null) 

 first = newNode; else //让index位置的前一个节点的next指向包含o的新节点 

 pred.next = newNode; //把newNode节点作为pred 

 pred = newNode; 

 } 

 //更新pred和succ if (succ == null) { 

 last = pred; 

 } else { 

 pred.next = succ; 

 succ.prev = pred; 

 } 

 //增加LinkedList的大小 

 size += numNew; //LinkedList用modCount变量来记录链表改变的次数 

 modCount++; return true; 

 }

node(index)方法非常重要，LinkedList很多方法都是通过node(index)才取得index位置的节点，从而进一步操作：
例如set（int index， E e），就是要通过node（index）取得index位置的node，从而设置node.item = e；

 //遍历链表从而取得index位置节点 

 Node E  node(int index) { //如果index 小于 size/2 则从头开始查找 if (index   (size   1)) { 

 Node E  x = first; for (int i = 0; i   index; i++) 

 x = x.next; return x; 

 } else { //如果index 大于 size/2 则从尾部开始查找 

 Node E  x = last; for (int i = size - 1; i   index; i--) 

 x = x.prev; return x; 

 } 

 }

这里是数据结构链表的内容，有数据结构基础的人完全可以看懂

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); else //如果不是在链尾添加，则把element添加到index位置节点前 

 linkBefore(element, node(index)); 

 }

 //succ是index位置的节点 void linkBefore(E e, Node E  succ) { // assert succ != null; //pred指向要添加的位置的前一个节点 final Node E  pred = succ.prev; //创建一个新节点 final Node E  newNode = new Node (pred, e, succ); //把新节点插入到index位置前 

 succ.prev = newNode; 

 //如果是在链表头部添加 if (pred == null) 

 first = newNode; else //把新节点插入到index位置前一个节点的后面，这样就把新节点插入到了index位置 

 pred.next = newNode; //容量加1 

 size++; //修改次数加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 = first; x != null; x = x.next) { if (x.item == null) { 

 unlink(x); return true; 

 } 

 } 

 } else { for (Node E  x = first; x != null; x = x.next) { if (o.equals(x.item)) { 

 unlink(x); return true; 

 } 

 } 

 } return false; 

 }

这段代码很简单，就是遍历链表，把删除掉第一次出现参数值得节点，如果找不到，返回false

remove调用了unlink(x)方法：

 E unlink(Node E  x) { 

 // assert x != null; 

 final E element = x.item; 

 final Node E  next = x.next; 

 final Node E  prev = x.prev; 

 if (prev == null) { 

 first = next; 

 } else { 

 prev.next = next; 

 x.prev = null; 

 } 

 if (next == null) { 

 last = prev; 

 } else { next.prev = prev; 

 x.next = null; 

 } 

 

 x.item = null; 

 size--; 

 modCount++; return element; 

 }

这里的删除逻辑跟数据结构中的链表的操作一样，非常简单

总得来看，LinkedList的实现是很简单的，只要数据结构过关，完全可以自己实现一个

原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/7795.html