LinkedList源码探险记

矫情吗；* 2022-07-11 12:22 177阅读 0赞

1.进入到linkedList里面，首先发现一个size属性，记录当前链表的长度  
2.存在一个结点内部类Node,该类没有什么特别之处，就简单的记录该结点的前驱与后继，与结点存的当前元素

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;
            }
        }

3.存在着一个first属性与一个last属性，记录着链表的第一个结点与最后一个结点

4.移除结点是通过其中一个方法进行控制的，代码如下：

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;
        }

5.添加结点方法addFirst,把元素添加了链表的头部中去，通过该代码进行添加（相应的addLast不再探索）

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++;
        }

6.contains方法需要对整个链表进行遍历探索，直到查出具体的元素

7.普通的add方法是把新的结点添加到尾部

8.remove方法需要从链表里面先查出该元素再对元素进行移除。线性表也需要查出元素的具体坐标，但是链表不需要进行移位

9.get(int index) 方法需要对链表进行一次遍历的操作