LinkedList源码阅读笔记（基于JDK1.8）

　　LinkedList是List接口的一个有序链表实现，存储节点是内部类Node，Node中有两个属性prev和next，负责连接前后两个元素。由于不是使用数组进行存储，所以查询需要遍历链表一半的元素（后面会解释），但是因为插入的时候只需要查询插入位置的元素，然后修改前后两个元素的对应属性即可，所以插入效率相对ArrayList较高（针对add(int index, E element)方法，add(E e)直接插入链表最后）。

1、添加

public void addFirst(E e) {    //添加元素到列表头

        linkFirst(e);

    }

public void addLast(E e) {    //添加元素到列表尾

        linkLast(e);

    }

 public boolean add(E e) {    //添加元素到列表头，会返回添加是否成功

        linkLast(e);

        return true;

    }

public void add(int index, E element) {    //添加元素到index位置

        checkPositionIndex(index);    //检查index是否越界

        if (index == size)    //如果index等于链表长度则插入到链表尾

            linkLast(element);

        else        //否则插入到链表头

            linkBefore(element, node(index));

    }

public boolean addAll(int index, Collection<? extends E> c) {    //在index位置插入集合c的全部元素

        checkPositionIndex(index);    //检查index是否越界

        Object[] a = c.toArray();

        int numNew = a.length;

        if (numNew == 0)

            return false;

        Node<E> pred, succ;

        if (index == size) {    //如果index为链表长度，则插入位置为链表尾

            succ = null;

            pred = last;

        } else {        //否则将记录index位置的前一个元素，为之后连接链表准备

            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;

        }

　　　　 //插入完毕，将原集合index之后的部分连接到链表尾

        if (succ == null) {

            last = pred;

        } else {

            pred.next = succ;

            succ.prev = pred;

        }

        size += numNew;

        modCount++;

        return true;

    }

    public E set(int index, E element) {    //修改index位置元素为element

        checkElementIndex(index);

        Node<E> x = node(index);

        E oldVal = x.item;

        x.item = element;

        return oldVal;

    }

2、取值

  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 get(int index) {    //获取链表index位置的元素

        checkElementIndex(index);

        return node(index).item;

    }

    Node<E> node(int index) {        //获取特定位置元素的实现方法

        // assert isElementIndex(index);

        if (index < (size >> 1)) {    //如果index小于链表长度的一半则从前向后遍历前一半链表

            Node<E> x = first;

            for (int i = 0; i < index; i++)

                x = x.next;

            return x;

        } else {    //如果index大于等于链表长度的一半则从后向前遍历后一半链表

            Node<E> x = last;

            for (int i = size - 1; i > index; i--)

                x = x.prev;

            return x;

        }

    }

3、删除

public E removeFirst() {    //删除链表头元素，类似pop

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

    }

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; // 这两个置为空是为了方便GC

        first = next;    //第二个元素提置第一位，将原第一位元素踢出链表

        if (next == null)    //如果没有next说明删除链表头元素后链表为空，将last置为空

            last = null;

        else    //next不为空说明删除后链表还存在元素，将现第一位元素的prev置为空（链表头元素prev为空）

            next.prev = null;

        size--;

        modCount++;

        return element;

    }

 private E unlinkLast(Node<E> l) {    //删除链表尾元素的实现方法

        // assert l == last && l != null;

        final E element = l.item;

        final Node<E> prev = l.prev;

        l.item = null;

        l.prev = null; // 这两个置为空是为了方便GC

        last = prev;    //将倒数第二个元素置为链表尾元素，将原链表尾元素踢出链表

        if (prev == null)    //如果prev为空则说明删除链表尾元素后链表为空，没有已保存的元素，此时first为空

            first = null;

        else    //如果prev不为空，说明删除之后链表还存在元素，此时需将链表尾元素的next元素置为空（链表尾元素next为空）

            prev.next = null;

        size--;

        modCount++;

        return element;

    }

public boolean remove(Object o) {    //删除指定元素实现方法

        if (o == null) {    //遍历空对象

            for (Node<E> x = first; x != null; x = x.next) {

                if (x.item == null) {    //如果有符合的元素则删除

                    unlink(x);

                    return true;

                }

            }

        } else {

            for (Node<E> x = first; x != null; x = x.next) {

                if (o.equals(x.item)) {    //如果有符合的元素则删除

                    unlink(x);

                    return true;

                }

            }

        }

        return false;

    }

public E remove(int index) {    //删除指定位置的元素

        checkElementIndex(index);

        return unlink(node(index));

    }

public E remove() {    //删除链表头元素

        return removeFirst();

    }

E unlink(Node<E> x) {    删除指定元素实现方法

        // assert x != null;

        final E element = x.item;        //参数元素的value，用于返回值

        final Node<E> next = x.next;    //参数元素的下一位元素

        final Node<E> prev = x.prev;    //参数元素的上一位元素

        if (prev == null) {    //prev为空说明参数元素是链表头元素，将下一位元素提置链表头

            first = next;

        } else {    //将上一位元素和下一位元素相连

            prev.next = next;

            x.prev = null;

        }

        if (next == null) {    //如果next为空说明参数元素是链表尾元素，将上一位元素置为链表尾

            last = prev;

        } else {    //将上一位元素和下一位元素相连

            next.prev = prev;

            x.next = null;

        }

        x.item = null;

        size--;

        modCount++;

        return element;

    }

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;

    }

4、迭代

LinkedList的迭代实现和其他几个集合的实现相比要强大一些，不仅可以向后遍历，也可以向前遍历，而且包含了实现fail-fast的增删改操作。

public E next() {    //获取下一个元素

            checkForComodification();

            if (!hasNext())

                throw new NoSuchElementException();

            lastReturned = next;

            next = next.next;

            nextIndex++;

            return lastReturned.item;

        }

public E previous() {        //获取上一个元素，需要注意的是当调用next然后调用previous时会返回同一个元素，因为调用next的时候nextIndex被加一，而previous中nextIndex减一，所以会取到同一个元素

            checkForComodification();

            if (!hasPrevious())

                throw new NoSuchElementException();

            lastReturned = next = (next == null) ? last : next.prev;

            nextIndex--;

            return lastReturned.item;

        }

public void remove() {    //实现了fail-fast的删除

            checkForComodification();

            if (lastReturned == null)

                throw new IllegalStateException();

            Node<E> lastNext = lastReturned.next;

            unlink(lastReturned);

            if (next == lastReturned)

                next = lastNext;

            else

                nextIndex--;

            lastReturned = null;

            expectedModCount++;

        }

        public void set(E e) {    //实现了fail-fast的修改

            if (lastReturned == null)

                throw new IllegalStateException();

            checkForComodification();

            lastReturned.item = e;

        }

        public void add(E e) {    //实现了fail-fast的新增

            checkForComodification();

            lastReturned = null;

            if (next == null)

                linkLast(e);

            else

                linkBefore(e, next);

            nextIndex++;

            expectedModCount++;

        }

巴特西

LinkedList源码阅读笔记（基于JDK1.8）

最新文章

热门文章