LinkedList源码探究

柔光的暖阳◎ 2022-01-21 10:35 321阅读 0赞

# ArrayList源码探究 #

本文全部以jdk1.8源码为根据，探究LinkedList的实现。转载请注明出处。

LinkedList同时实现了List接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（Stack）。这样看来，LinkedList简直就是个全能冠军。当你需要使用栈或者队列时，可以考虑使用LinkedList，一方面是因为Java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类（它是个接口名字）。关于栈或队列，现在的首选是ArrayDeque，它有着比LinkedList（当作栈或队列使用时）有着更好的性能。

![在这里插入图片描述][20190609204700904.png]

## 构造方法 ##

无参构造方法什么也没有做。  
构建一个空的list。  
![在这里插入图片描述][20190609204747841.png]  
内部类有一个Node,可以看出 Node为一个双向链表  
![在这里插入图片描述][20190609204759997.png]

## 添加方法们 ##

*  **public boolean add(E e)**

添加一个指定的节点到list集合中的尾部  
![在这里插入图片描述][20190609204908983.png]  
如果last为null，代表原来的链表为null，这是插入的第一个元素，直接把first赋值为newNode即可  
![在这里插入图片描述][20190609205009827.png]

*  **public void add(int index, E element)**  
    将指定元素插入此列表中的指定位置。 将当前位置的元素（如果有）和任何后续元素向右移动（将其添加到其索引中）。  
    ![在这里插入图片描述][20190609205156714.png]  
    如果index == size，即添加到队末尾，直接调用linkLast即可  
    否则，调用linkeBefore方法  
    在非null节点succ之前插入元素e。  
    ![在这里插入图片描述][20190609205229232.png]  
    上面的方法中，pred代表被插入到之前的节点，构造好newNode后，指针更改指向就完成了成功插入。
 *  **public boolean addAll(Collection<? extends E> c)**

将指定集合中的所有元素按指定集合的迭代器返回的顺序附加到此列表的末尾。 如果在操作正在进行时修改指定的集合，则此操作的行为是不确定的。 （请注意，如果指定的集合是此列表，则会发生这种情况，并且它是非空的。）  
![在这里插入图片描述][20190609205315224.png]  
点开addAll  
从指定位置开始，将指定集合中的所有元素插入此列表。 将当前位置的元素（如果有）和任何后续元素向右移动（增加其索引）。 新元素将按照指定集合的迭代器返回的顺序出现在列表中。  
![在这里插入图片描述][20190609205333657.png]

public boolean addAll(int index, Collection<? extends E> c) { 
            //1:检查index范围是否在size之内
            checkPositionIndex(index);
     
            //2:toArray()方法把集合的数据存到对象数组中
            Object[] a = c.toArray();
            int numNew = a.length;
            if (numNew == 0)
                return false;
     
            //3：得到插入位置的前驱节点和后继节点
            Node<E> pred, succ;
            //如果插入位置为尾部，前驱节点为last，后继节点为null
            if (index == size) { 
                succ = null;
                pred = last;
            }
            //否则，调用node()方法得到后继节点，再得到前驱节点
            else { 
                succ = node(index);
                pred = succ.prev;
            }
     
            // 4：遍历数据将数据插入
            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;
            }
     
            //如果插入位置在尾部，重置last节点
            if (succ == null) { 
                last = pred;
            }
            //否则，将插入的链表与先前链表连接起来
            else { 
                pred.next = succ;
                succ.prev = pred;
            }
     
            size += numNew;
            modCount++;
            return true;
        }

上面可以看出addAll方法通常包括下面四个步骤：

1.  检查index范围是否在size之内
2.  toArray()方法把集合的数据存到对象数组中
3.  得到插入位置的前驱和后继节点
4.  遍历数据，将数据插入到指定位置

*  **public void addFirst(E e)**  
    将一个指定的节点插入到list的开始  
    ![在这里插入图片描述][20190609205521874.png]  
    实现比较简单，常规操作  
    ![在这里插入图片描述][20190609205534403.png]
 *  **public void addLast(E e)**  
    将一个指定的节点添加到链表尾部  
    ![在这里插入图片描述][20190609205608579.png]  
    同样是常规操作：  
    ![在这里插入图片描述][20190609205622140.png]

## 获取节点的方法们 ##

*  **public E get(int index)和获取头结点和尾节点的方法比较**

返回链表中指定位置的节点  
![在这里插入图片描述][20190609205840105.png]  
其实就是对链表进行遍历，判断从前遍历还是从后遍历比较快，然后找到对应索引的值。  
![在这里插入图片描述][20190609205909705.png]

*  **另外获取头结点（index = 0）有四个方法：**

public E getFirst() { 
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return f.item;
        }
    public E element() { 
            return getFirst();
        }
    public E peek() { 
            final Node<E> f = first;
            return (f == null) ? null : f.item;
        }
     
    public E peekFirst() { 
            final Node<E> f = first;
            return (f == null) ? null : f.item;
         }

**区别：** getFirst(),element(),peek(),peekFirst() 这四个获取头结点方法的区别在于对链表为空时的处理，是抛出异常还是返回null，其中getFirst() 和element() 方法将会在链表为空时，抛出异常

element()方法的内部就是使用getFirst()实现的。它们会在链表为空时，抛出NoSuchElementException

*  **获取尾节点数据方法:**

public E getLast() { 
            final Node<E> l = last;
            if (l == null)
                throw new NoSuchElementException();
            return l.item;
        }
     public E peekLast() { 
            final Node<E> l = last;
            return (l == null) ? null : l.item;
        }

**两者区别：** getLast() 方法在链表为空时，会抛出NoSuchElementException，而peekLast() 则不会，只是会返回 null。

## 获取指定元素的索引位置 和 判断元素是否存在 ##

*  **int indexOf(Object o)： 从头遍历找**

public int indexOf(Object o) { 
            int index = 0;
            if (o == null) { 
                //从头遍历
                for (Node<E> x = first; x != null; x = x.next) { 
                    if (x.item == null)
                        return index;
                    index++;
                }
            } else { 
                //从头遍历
                for (Node<E> x = first; x != null; x = x.next) { 
                    if (o.equals(x.item))
                        return index;
                    index++;
                }
            }
            return -1;
        }

*  **public int lastIndexOf(Object o)**

int lastIndexOf(Object o)： 从尾遍历找
     
    public int lastIndexOf(Object o) { 
            int index = size;
            if (o == null) { 
                //从尾遍历
                for (Node<E> x = last; x != null; x = x.prev) { 
                    index--;
                    if (x.item == null)
                        return index;
                }
            } else { 
                //从尾遍历
                for (Node<E> x = last; x != null; x = x.prev) { 
                    index--;
                    if (o.equals(x.item))
                        return index;
                }
            }
            return -1;
        }

*  contains(Object o)： 检查对象o是否存在于链表中

public boolean contains(Object o) { 
            return indexOf(o) != -1;
      }

## 删除元素的方法们 ##

*  **remove() ,removeFirst(),pop(): 删除头节点**  
    ![在这里插入图片描述][20190609210547629.png]  
    ![在这里插入图片描述][20190609210957615.png]
 *  **removeLast(),pollLast(): 删除尾节点**  
    ![在这里插入图片描述][20190609210609258.png]

区别： removeLast()在链表为空时将抛出NoSuchElementException，而pollLast()方法返回null。关于头节点和尾节点方法相似。

*  **remove(Object o): 删除指定元素**  
    ![在这里插入图片描述][20190609211051909.png]  
    当删除指定对象时，只需调用remove(Object o)即可，不过该方法一次只会删除一个匹配的对象，如果删除了匹配对象，返回true，否则false。

unlink(Node x) 方法：  
![在这里插入图片描述][20190609211126209.png]

*  **remove(int index)：删除指定位置的元素**  
    ![在这里插入图片描述][2019060921120244.png]  
    先使用checkElementIndex进行校验。  
    ![在这里插入图片描述][20190609211642471.png]  
    小于size的范围，才能移除：  
    ![在这里插入图片描述][20190609211849931.png]  
    unlink方法上面已经解析过。

LinkedList分析结束，下次将分析HashMap的源码。

[20190609204700904.png]: /images/20220121/ac2a0c3ad6e64773a901fec43ed1fa2c.png
[20190609204747841.png]: /images/20220121/1bb9a392da6d4dc2ae876790423b1566.png
[20190609204759997.png]: /images/20220121/e798ef4e3f3440d19e6447daf2e7f6d7.png
[20190609204908983.png]: /images/20220121/8c2fb9b9c31b46b287a59909f5c7d7d0.png
[20190609205009827.png]: /images/20220121/470622688a1e470c89a1a46b27aae154.png
[20190609205156714.png]: /images/20220121/a67fa03385d2409ca6debfd167bd780f.png
[20190609205229232.png]: /images/20220121/d8d6c9f13e8941658067e266dd800627.png
[20190609205315224.png]: /images/20220121/ed6df3ce83c84d2fb237d10f41d84eba.png
[20190609205333657.png]: /images/20220121/6bf7853fc8734177a1b5be0dcad52e73.png
[20190609205521874.png]: /images/20220121/04bfd3073a9244ba982005d119d3dc6a.png
[20190609205534403.png]: /images/20220121/d8377ddd53ed434dbbddcf64f4ee774c.png
[20190609205608579.png]: /images/20220121/61ce3f1f1e9448b39ff90bb231a1a57b.png
[20190609205622140.png]: /images/20220121/c31d6cc61be54d72926cc5ce35112b1b.png
[20190609205840105.png]: /images/20220121/26ba2e210cdc43649555424e316a0c52.png
[20190609205909705.png]: /images/20220121/d6a30ede7dc24d48ad7a80bacf40d8a7.png
[20190609210547629.png]: /images/20220121/331e4a45f3e6449e8c0f538e67863d48.png
[20190609210957615.png]: /images/20220121/020408de61b7441f850fa3ff910e69a7.png
[20190609210609258.png]: /images/20220121/68cfc72e54224f1db15011fd4f101fcb.png
[20190609211051909.png]: /images/20220121/6e618f36b1c541abbc42c873152bb177.png?
[20190609211126209.png]: /images/20220121/061688f9d8124c2387994c8599b8e7f4.png
[2019060921120244.png]: /images/20220121/98305473d9154a9fbab87848e8855175.png
[20190609211642471.png]: /images/20220121/389c2da92c5940e2b84a0cb5b22db7a0.png
[20190609211849931.png]: /images/20220121/2b2951dfe4b1495b8df02667e3a77835.png