LinkedList 源码阅读

桃扇骨 2023-07-14 12:57 10阅读 0赞

### 第一部分：单向链表  ###

public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable

1、使用了transient修改size，链表中的两个指针

transient int size = 0;
    
        /**
         * Pointer to first node.
         * Invariant: (first == null && last == null) ||
         *            (first.prev == null && first.item != null)
         */
        transient Node<E> first;
    
        /**
         * Pointer to last node.
         * Invariant: (first == null && last == null) ||
         *            (last.next == null && last.item != null)
         */
        transient Node<E> last;

2、 LinkedList的有参构造

public LinkedList(Collection<? extends E> c) {
            this();
            addAll(c);
        }

需要通过size进行添加所有的节点

public boolean addAll(Collection<? extends E> c) {
            return addAll(size, c);
        }

添加的时候会按照list的顺序依次添加到数组中，当然checkPositionIndex需要判断是否在（0，size）范围

public boolean addAll(int index, Collection<? extends E> c) {
            checkPositionIndex(index);
    
            Object[] a = c.toArray();
            int numNew = a.length;
            if (numNew == 0)
                return false;
    
            Node<E> pred, succ;
            if (index == size) {
                succ = null;
                pred = last;
            } else {
                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;
            } else {
                pred.next = succ;
                succ.prev = pred;
            }
    
            size += numNew;
            modCount++;
            return true;
        }

3、linkFirst 开始节点上添加一个节点，时间复杂度O(1)

将first节点前的前驱置空，然后把新元素赋值给首节点

/**
         * Links e as first element.
         */
        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++;
        }

此处需要用到Node的构造方法，其中prev指前驱，next指后继节点

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

4、linkBefore 在非空节点前插入节点,，时间复杂度O(1)

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

首先确定要将元素插入到节点succ前面

关键的就是把newNode 和前后节点指针建立联系，succ.prev = newNode;   pred.next = newNode;

5、unlinkFirst 删除一个非空的first节点，是把指向这个节点的指针都移除，同时把first指向他的next节点，如果next节点也为空，说明这个节点是List中的最后一个节点，那么first和last都指向空，时间复杂度是o(1)

/**
         * Unlinks non-null first node 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;
        }

unlinkLast 同，将最后一个节点置为null

6、unlink(node) 删除一个非空节点

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

7、getFirst、getLast、removeFirst、removeLast、addFrist、addLast未采用以上方法进行获取，时间复杂度O(1)

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;
        }
    
        public E removeFirst() {
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return unlinkFirst(f);
        }
    
        public E removeLast() {
            final Node<E> l = last;
            if (l == null)
                throw new NoSuchElementException();
            return unlinkLast(l);
        }
    
        public void addFirst(E e) {
            linkFirst(e);
        }
    
        public void addLast(E e) {
            linkLast(e);
        }

以上的方法，算法复杂度为O(1)，以下的方法也是linkedList差评的地方

8、contains方法,算法复杂度O(n)

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

其中的indexOf方法，算法复杂度有点高，因为for循环进行的计算

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

***9、node(index)方法 \*\*\*\* ，算法复杂度O(n)***

/**
         * Returns the (non-null) Node at the specified element index.
         */
        Node<E> node(int index) {
            // assert isElementIndex(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;
            }
        }

### Queue 队列操作  ###

>   ***//    查看第一个，但是不删除***    
> 
>    public E peek() \{  
>         final Node<E> f = first;  
>         return (f == null) ? null : f.item;  
>     \}
> 
>    ***//    查看第一个，但不删除***
> 
>     public E element() \{  
>         return getFirst();  
>     \}
> 
>    ***//     获取第一个，并且删除***
> 
>     public E poll() \{  
>         final Node<E> f = first;  
>         return (f == null) ? null : unlinkFirst(f);  
>     \}
> 
>     ***//    获取第一个并且删除***
> 
>     public E remove() \{  
>         return removeFirst();  
>     \}
> 
>     ***//    在队列尾部添加一个***
> 
>     public boolean offer(E e) \{  
>         return add(e);  
>     \}

### Qeque 双向队列 ###

>   ***  //    在队列头部添加一个***  
>     public boolean offerFirst(E e) \{  
>         addFirst(e);  
>         return true;  
>     \}
> 
>    *** //    在队列尾部添加一个***  
>     public boolean offerLast(E e) \{  
>         addLast(e);  
>         return true;  
>     \}
> 
>  ***   //    查看队列头部但不删除***  
>     public E peekFirst() \{  
>         final Node<E> f = first;  
>         return (f == null) ? null : f.item;  
>      \}
> 
> ***    //    查看队列尾部但不删除***  
>     public E peekLast() \{  
>         final Node<E> l = last;  
>         return (l == null) ? null : l.item;  
>     \}
> 
>  ***   //    获取并且删除队列头部元素***  
>     public E pollFirst() \{  
>         final Node<E> f = first;  
>         return (f == null) ? null : unlinkFirst(f);  
>     \}
> 
>    *** //    获取并且删除队列尾部元素***  
>     public E pollLast() \{  
>         final Node<E> l = last;  
>         return (l == null) ? null : unlinkLast(l);  
>     \}

### stack 栈的操作 ###

>     ***//    查看栈顶但不删除***  
>     public E poll() \{  
>         final Node<E> f = first;  
>         return (f == null) ? null : unlinkFirst(f);  
>     \}
> 
>    ***//    压栈***
> 
>     public void push(E e) \{  
>         addFirst(e);  
>     \}
> 
>    ***//    出栈***
> 
>     public E pop() \{  
>         return removeFirst();  
>     \}

### 实现第一次发生和最后一次发生 ###

> ***    //     移除第一次出现***  
>     public boolean removeFirstOccurrence(Object o) \{  
>         return remove(o);  
>     \}
> 
>   ***  //    移除最后一次出现***  
>     public boolean removeLastOccurrence(Object o) \{  
>         if (o == null) \{  
>             for (Node<E> x = last; x != null; x = x.prev) \{  
>                 if (x.item == null) \{  
>                     unlink(x);  
>                     return true;  
>                 \}  
>             \}  
>         \} else \{  
>             for (Node<E> x = last; x != null; x = x.prev) \{  
>                 if (o.equals(x.item)) \{  
>                     unlink(x);  
>                     return true;  
>                 \}  
>             \}  
>         \}  
>         return false;  
>     \}
> 
>

> 结论：
> 
> LinkedList***最大的好处***在于***头尾和已知节点的插入和删除***时间复杂度都是o(1)。
> 
> 但是涉及到***先确定位置再操作***的情况，则时间复杂度会变为***o(n)***。当然，每个节点都需要保留prev和next指针也是经常被吐槽是浪费了空间。

### 第二部分 谷歌android改造的部分代码 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 1][]

以下为给定location

谷歌有点高明的地方就是，***通过简单的代码确定在前半部分或者在后半部分进行查询***

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 2][]

删除方法也如此

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 3][]

toArray方法

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 4][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70]: /images/20230529/9c357fea0be24ee9940b4a9bb5bbaeb1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 1]: /images/20230529/ac0213319c72448ea56c59ec2473b2eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 2]: /images/20230529/1acef27444c241c1aff859eb68a68ccd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 3]: /images/20230529/4d1f95916f06447a918e82690402e350.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 4]: /images/20230529/dcbcc2059d8448eaa1f2aa5506962a04.png