java 集合 2 - LinkedList-白红宇

java 集合 2 - LinkedList

参考文章：

LinkedList是基于实现的。

特性
是否存取null值	可以
元素是否可以重复	可以
是否有序	有序
是否线程安全	不安全

接下来直接通过源码（jdk1.8）分析。

结点定义

private static class Node
    
      {        E item;        Node
     
       next;        Node
      
        prev;        Node(Node
       
         prev, E element, Node
        
          next) {            this.item = element;            this.next = next;            this.prev = prev;        }    }复制代码

可见，对于每一个结点，可以通过prev找到它的直接前驱，通过next找到其后继。

头，尾结点

/**     * Pointer to first node.     * Invariant: (first == null && last == null) ||     *            (first.prev == null && first.item != null)     */    transient Node
    
      first;    /**     * Pointer to last node.     * Invariant: (first == null && last == null) ||     *            (last.next == null && last.item != null)     */    transient Node
     
       last;复制代码

作为双向链表，链表头的前驱为链表尾，链表尾的后继为链表头，first和last满足如下关系： first不为空，且链表尾为空，那么链表只有一个元素，保存于链表头；last不为空，且链表头为空，那么链表只有一个元素，保存于链表尾。

add方法

public boolean add(E e) {        linkLast(e);        return true;    }        public void add(int index, E element) {        checkPositionIndex(index);        if (index == size)            linkLast(element);        else            linkBefore(element, node(index));    }复制代码

一个参数的add方法实际调用了linkLast方法，linkLast方法。

两个参数的add方法先检查下标是否越界，之后如果下标（从0开始）为当前链表的长度（size从1开始），那么就是新增元素于链表尾，否则调用linkbefore插入元素。

linkLast方法

/**     * Links e as last element.     */    void linkLast(E e) {        final Node
    
      l = last;        final Node
     
       newNode = new Node<>(l, e, null);        last = newNode;        if (l == null)            first = newNode;        else            l.next = newNode;        size++;        modCount++;    }复制代码

可见linkLast方法会将新的结点进行构造，然后替换原来的尾结点，如果原来的尾结点为空，那意味着链表还没有元素（有一个元素时头尾就都不为null），此时构造的就是第一个元素，使头尾都指向同一元素（该元素的前驱和后继都为null），如果原来的尾结点已经存在，那么将原来的尾结点的后继指向新的尾结点即可。

linkBefore方法

/**     * Inserts element e before non-null Node succ.     */    void linkBefore(E e, Node
    
      succ) {        // assert succ != null;        final Node
     
       pred = succ.prev;        final Node
      
        newNode = new Node<>(pred, e, succ);        succ.prev = newNode;        if (pred == null)            first = newNode;        else            pred.next = newNode;        size++;        modCount++;    }复制代码

这里对应succ参数的定位发生在node方法中：

node方法

/**     * Returns the (non-null) Node at the specified element index.     */    Node
    
      node(int index) {        // assert isElementIndex(index);        if (index < (size >> 1)) {            Node
     
       x = first;            for (int i = 0; i < index; i++)                x = x.next;            return x;        } else {            Node
      
        x = last;            for (int i = size - 1; i > index; i--)                x = x.prev;            return x;        }    }复制代码

结合上面双参数的add方法，可见该方法首先会判断新插入的点在链表中的大体位置（前一半还是后一半），然后从前往后或从后往前定位到指定下标的点并返回。

再回头看linkBefore方法，构建新节点，修改被插入结点的前驱，被插入结点的原前驱的后继。

get方法

public E get(int index) {        checkElementIndex(index);        return node(index).item;    }复制代码

get方法首先会检查下标，然后通过node方法定位目标结点，取出值返回。

indexOf方法

public int indexOf(Object o) {        int index = 0;        if (o == null) {            for (Node
    
      x = first; x != null; x = x.next) {                if (x.item == null)                    return index;                index++;            }        } else {            for (Node
     
       x = first; x != null; x = x.next) {                if (o.equals(x.item))                    return index;                index++;            }        }        return -1;    }复制代码

该方法用于查找指定元素的下标，可见该方法会对目标元素是否为null采用不同的搜索方式，没找到则返回-1。

---END---