Java进阶之----LinkedList源码分析

阅读量：4031 次

发布时间：2019-05-24

本文共 8833 字，大约阅读时间需要 29 分钟。

一、在Eclipse中查看Java类库的源代码

首先要找到JDK安装目录，然后该目录下会有个src.zip文件，我们把它加载到Eclipse中就行了，然后在Eclipse中想查看某个方法或者某个类的源代码，直接选中按F3

下面那个Path就是你所安装JDK目录下的src.zip的路径

【引自：http://www.2cto.com/kf/201612/571310.html】

使用：

可以在源代码编辑器或代码片段编辑窗中选择类型、方法或字段的名称，然后对元素的定义打开编辑器。

在 Java 编辑器中，选择类型、方法或字段的名称。您也可以仅仅在名称中单击一次。

执行下列其中一项操作：

1.从菜单栏中，选择浏览 > 打开声明

2.从编辑器的弹出菜单中，选择打开声明

3.按 F3 键

或者

1.按下 Ctrl 键。

2.在 Java 编辑器中，将鼠标移到类型、方法或字段的名称上，直到名称变为带有下划线为止。

3.单击一次超链接。

如果具有多个同名的定义，则会显示一个对话框，您可以选择想要打开的一个定义。一个编辑器打开，它包含所选择的元素。

原文地址:http://ajava.org/course/tool/14485.html

二、Java进阶之----LinkedList源码分析

【转自：http://blog.csdn.net/zw0283/article/details/51132161】

今天在看LinkedList的源代码的时候，遇到了一个坑。我研究源码时，发现LinkedList是一个直线型的链表结构，但是我在baidu搜索资料的时候，关于这部分的源码解析，全部都说LinkedList是一个环形链表结构。。我纠结了好长时间，还以为我理解错了，最后还是在Google搜到了结果：因为我看的源码是1.7的而baidu出来的几乎全部都是1.6的。而且也没有对应的说明。在1.7之后，将LinkedList做了一些优化，将1.6中的环形结构优化为了直线型了链表结构。这里要提示一下朋友们，看源码的时候，一定要看版本，有的情况是属于小改动，有的地方可能有大改动，这样只会越看越迷糊。

好，言归正传。我们来分析一下中LinkedList的部分源码。（本文针对的是1.7的源码）

LinkedList的基本结构

之前我一直在说链表链表，那什么是链表？顾名思义，链表就和链子一样，每一环都要连接着后边的一环和前边的一环，这样，当我们需要找这根链子的某一环的时候，只要我们能找到链子的任意一环，都可以找到我们需要的那一环。我们看一个图，就能很好的理解了。

在LinkedList中，我们把链子的“环”叫做“节点”，每个节点都是同样的结构。节点与节点之间相连，构成了我们LinkedList的基本数据结构，也是LinkedList的核心。

我们再来看一下LinkedList在jdk1.6和1.7直接结构的区别

首先看1.7中的结构

再来看1.6中的结构

对比一下，知道区别在哪里了吧？在1.7中，去掉了环形结构，自然在代码中的也会有部分的改变。

理解了上边的结构，在分析的时候就会容易许多。

LinkedList的构造方法

LinkedList包含3个全局参数，

size存放当前链表有多少个节点。

first为指向链表的第一个节点的引用。

last为指向链表的最后一个节点的引用。

LinkedList构造方法有两个，一个是无参构造，一个是传入Collection对象的构造。

[java]
 // 什么都没做，是一个空实现  
 public LinkedList() {  
 }  
   
 public LinkedList(Collection<? extends E> c) {  
     this();  
     addAll(c);  
 }  
   
 public boolean addAll(Collection<? extends E> c) {  
     return addAll(size, c);  
 }  
   
 public boolean addAll(int index, Collection<? extends E> c) {  
     // 检查传入的索引值是否在合理范围内  
     checkPositionIndex(index);  
     // 将给定的Collection对象转为Object数组  
     Object[] a = c.toArray();  
     int numNew = a.length;  
     // 数组为空的话，直接返回false  
     if (numNew == 0)  
         return false;  
     // 数组不为空  
     Node<E> pred, succ;  
     if (index == size) {  
         // 构造方法调用的时候，index = size = 0，进入这个条件。  
         succ = null;  
         pred = last;  
     } else {  
         // 链表非空时调用，node方法返回给定索引位置的节点对象  
         succ = node(index);  
         pred = succ.prev;  
     }  
     // 遍历数组，将数组的对象插入到节点中  
     for (Object o : a) {  
         @SuppressWarnings("unchecked") E e = (E) o;  
         Node<E> newNode = new Node<>(pred, e, null);  
         if (pred == null)  
             first = newNode;  
         else  
             pred.next = newNode;  
         pred = newNode;  
     }  
   
     if (succ == null) {  
         last = pred; // 将当前链表最后一个节点赋值给last  
     } else {  
         // 链表非空时，将断开的部分连接上  
         pred.next = succ;  
         succ.prev = pred;  
     }  
     // 记录当前节点个数  
     size += numNew;  
     modCount++;  
     return true;  
 }  

这里要说明一下，Node是LinkedList的内部私有类，它的组成很简单，只有一个构造方法。

[java]
 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;  
     }  
 }  

构造方法的参数顺序是：前继节点的引用，数据，后继节点的引用。

有了上边的说明，我们来看LinkedList的构造方法。

这段代码还是很好理解的。我们可以配合图片来深入理解。

这段代码分为了2种情况，一个是原来的链表是空的，一个是原来的链表有值。我们分别来看

原来有值的情况

配合代码来看，是不是思路清晰了许多？

原来链表是空的话就更好办了，直接把传入的Collection对象转化为数组，数组的第一个值就作为头结点，即head，之后的顺序往里加入即可。并且节省了改变原节点指向的的操作。

对与两种构造方法，总结起来，可以概括为：无参构造为空实现。有参构造传入Collection对象，将对象转为数组，并按遍历顺序将数组首尾相连，全局变量first和last分别指向这个链表的第一个和最后一个。

LinkedList部分方法分析

addFirst/addLast分析

我们来看代码

[java]
 public void addFirst(E e) {  
     linkFirst(e);  
 }  
   
 private void linkFirst(E e) {  
     final Node<E> f = first;  
     final Node<E> newNode = new Node<>(null, e, f); // 创建新的节点，新节点的后继指向原来的头节点，即将原头节点向后移一位，新节点代替头结点的位置。  
     first = newNode;  
     if (f == null)  
         last = newNode;  
     else  
         f.prev = newNode;  
     size++;  
     modCount++;  
 }  

其实只要理解了上边的数据结构，这段代码是很好理解的。

加入一个新的节点，看方法名就能知道，是在现在的链表的头部加一个节点，既然是头结点，那么头结点的前继必然为null，所以这也是Node<E> newNode = new Node<>(null, e, f);这样写的原因。

之后将first指向了当前链表的头结点，之后对之前的头节点进行了判断，若在插入元素之前头结点为null，则当前加入的元素就是第一个几点，也就是头结点，所以当前的状况就是：头结点=刚刚加入的节点=尾节点。若在插入元素之前头结点不为null，则证明之前的链表是有值的，那么我们只需要把新加入的节点的后继指向原来的头结点，而尾节点则没有发生变化。这样一来，原来的头结点就变成了第二个节点了。达到了我们的目的。

addLast方法在实现上是个addFirst是一致的，这里就不在赘述了。有兴趣的朋友可以看看源代码。

其实，LinkedList中add系列的方法都是大同小异的，都是创建新的节点，改变之前的节点的指向关系。仅此而已。

getFirst/getLast方法分析

[java]
 public E getFirst() {  
     final Node<E> f = first;  
     if (f == null)  
         throw new NoSuchElementException();  
     return f.item;  
 }  
   
 public E getLast() {  
     final Node<E> l = last;  
     if (l == null)  
         throw new NoSuchElementException();  
     return l.item;  
 }  

这段代码即不需要解析了吧。。很简单的。

get方法分析

这里主要看一下它调用的node方法

[java]
 public E get(int index) {  
     // 校验给定的索引值是否在合理范围内  
     checkElementIndex(index);  
     return node(index).item;  
 }  
   
 Node<E> node(int index) {  
     if (index < (size >> 1)) {  
         Node<E> x = first;  
         for (int i = 0; i < index; i++)  
             x = x.next;  
         return x;  
     } else {  
         Node<E> x = last;  
         for (int i = size - 1; i > index; i--)  
             x = x.prev;  
         return x;  
     }  
 }  

一开始我很费解，这是要干嘛？后来我才明白，代码要做的是:判断给定的索引值，若索引值大于整个链表长度的一半，则从后往前找，若索引值小于整个链表的长度的一般，则从前往后找。这样就可以保证，不管链表长度有多大，搜索的时候最多只搜索链表长度的一半就可以找到，大大提升了效率。

removeFirst/removeLast方法分析

[java]
 public E removeFirst() {  
     final Node<E> f = first;  
     if (f == null)  
         throw new NoSuchElementException();  
     return unlinkFirst(f);  
 }  
   
 private E unlinkFirst(Node<E> f) {  
     // assert f == first && f != null;  
     final E element = f.item;  
     final Node<E> next = f.next;  
     f.item = null;  
     f.next = null; // help GC  
     first = next;  
     if (next == null)  
         last = null;  
     else  
         next.prev = null;  
     size--;  
     modCount++;  
     return element;  
 }  

摘掉头结点，将原来的第二个节点变为头结点，改变frist的指向，若之前仅剩一个节点，移除之后全部置为了null。

对于LinkedList的其他方法，大致上都是包装了以上这几个方法，没有什么其他的大的变动。

三、完整实例

【转自：https://github.com/onlyliuxin/coding2017/blob/master/group20/1107837739/1107837739Learning/src/org/korben/list/KLinkedList.java】

（1）KList.java

package org.korben.list;/** * Korben's List * * Created by Korben on 18/02/2017. */public interface KList
   
     {    int size();    boolean isEmpty();    boolean contains(Object o);    Object[] toArray();    boolean add(T o);    boolean remove(T o);    void clear();    T get(int index);    T set(int index, T element);    void add(int index, T element);    T remove(int index);    int indexOf(T o);    KIterator
    
      iterator();}

（2）KLinkedList.java——存在点bug；不过大体思路给出来了

package org.korben.list;import java.util.Objects;/** * Korben's LinkedList * * Created by Korben on 18/02/2017. */public class KLinkedList
   
     implements KList
    
      {    private int size;    private Node
     
       head;    private Node
      
        last;    public KLinkedList() {        this.head = new Node<>(null);    }    @Override    public int size() {        return this.size;    }    @Override    public boolean isEmpty() {        return this.size == 0;    }    @Override    public boolean contains(Object o) {        Node node = this.head;        while (node.next != null) {            node = node.next;            if (Objects.equals(node.data, o)) {                return true;            }        }        return false;    }    @Override    public Object[] toArray() {        return new Object[0];    }    @Override    public boolean add(T o) {        if (this.last == null) {            this.last = new Node<>(o);            this.last.pre = this.head;            this.head.next = this.last;        } else {            Node
       
         oldLast = this.last;            this.last = new Node<>(o);            this.last.pre = oldLast;            oldLast.next = this.last;        }        this.size++;        return true;    }    @Override    public boolean remove(T o) {        Node node = this.head;        while (node.next != null) {            node = node.next;            if (Objects.equals(node.data, o)) {                node.pre.next = node.next;                if (node.next != null) {                    node.next.pre = node.pre;                }                this.size--;                return true;            }        }        return false;    }    @Override    public void clear() {        this.head.next = null;        this.last = null;        this.size = 0;    }    @Override    public T get(int index) {        return getNode(index).data;    }    @Override    public T set(int index, T element) {        Node
        
          node = getNode(index); node.data = element; return element; } @Override public void add(int index, T element) { Node
         
           node = this.head; for (int i = 0; i <= index; i++) { node = node.next; } Node
          
            pre = node.pre; Node
           
             newNode = new Node<>(element); pre.next = newNode; newNode.pre = pre; newNode.next = node; node.pre = newNode; this.size++; } @Override public T remove(int index) { Node
            
              node = getNode(index); Node
             
               pre = node.pre; Node
              
                next = node.next; pre.next = next; if (next != null) { next.pre = pre; } this.size--; return node.data; } @Override public int indexOf(T o) { Node node = this.head; int index = 0; while (node.next != null) { node = node.next; if (Objects.equals(node.data, o)) { return index; } index++; } return -1; } @Override public KIterator
               
                 iterator() { throw new IllegalStateException("方法未实现"); } private Node
                
                  getNode(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException(); } Node
                 
                   node = this.head; for (int i = 0; i <= index; i++) { node = node.next; } return node; } private static class Node
                  
                    { T data; Node
                   
                     pre; Node
                    
                      next; Node(T data) { this.data = data; } }}