美文网首页
JAVA8 LinkedList源码学习总结

JAVA8 LinkedList源码学习总结

作者: 慢游世界 | 来源:发表于2019-01-16 21:53 被阅读0次

    一、LinkedList是一个双向链表,数据结构图如下(节点中的数字为节点存储的内容):

    LinkedList结构

    二、LinkedList内部有一个Node类,Node类有三个成员变量,分别是item(节点存储的内容)、prev(指向上一个Node)、next(指向下一个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;
            }
        }
    

    三、LinkedList实现了List、Queue、Deque(双端队列)接口,有List的特性(有顺序、不重复),支持Queue操作(先进后出),支持Deque操作(在队首队尾插入删除元素),此外,还提供了push、pop方法,因此还有栈的特性。

    四、LinkedList常用API

    1. 在链表头添加元素的方法:addFirst、offerFirst、push,在链表尾添加元素的方法:add、addLast、offerLast、offer。
    2. 在链表头删除元素的方法:(删除元素的同时会返回所删除的元素,但有可能元素不存在,即链表为空,当遇到这种情况时LinkedList提供了两种处理方式,返回null或者抛出异常),返回null的方法有poll、pollFirst,抛出异常的方法有removeFirst、remove、pop。在链表末端删除元素的方法(末端元素同样可以不存在,即链表为空):返回null的方法有pollLast,抛出异常的方法有removeLast。
    3. 获取链表头元素的方法(获取元素同样会出现链表为空的情况):返回null的方法有peek、peekFirst、element,抛出异常的方法有getFirst。获取链表末端元素的方法:返回null的方法有peekLast,抛出异常的方法有getLast。

    五、与ArrayList一样,有两个toArray方法,toArray()toArray(T[] a)toArray()返回一个Object[]数组,toArray(T[] a)返回一个特定类型的数组。

    六、内部有3个迭代器类,ListItr、DescendingIterator、LLSpliterator。

    1. ListItr可以向前向后遍历,还可以增加元素、设置某个位置的元素。
    2. DescendingIterator是从链表末端向前(单向)遍历的迭代器,内部其实是封装了一个ListItr,next方法委托了ListItr的previous方法,hasNext委托了ListItr的hasPrevious方法。
    3. LLSpliterator是java8并行迭代器的一个实现,此实现通过trySplit返回一个Spliterators.ArraySpliterator对象,该对象再通过trySplit可把元素分割两半,然后可以交给多个线程处理。

    相关文章

      网友评论

          本文标题:JAVA8 LinkedList源码学习总结

          本文链接:https://www.haomeiwen.com/subject/zooqrqtx.html