通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

说说java中的LinkedList及其在算法中的应用

296人浏览 / 0人评论 / | 作者:因情语写  | 分类: 设计模式与算法  | 标签: 设计模式与算法  | 

作者:因情语写

链接:https://www.proprogrammar.com/article/560

声明:请尊重原作者的劳动,如需转载请注明出处


    先前说了一下算法题中常用的java数据结构,讲了java中常用的各种数据结构,今天要来详细说一下其中的LinkedList,还是以应用为主,不说让人头疼的原理实现,只讲一讲在实际中的具体应用(本人不爱看源码^-^),为什么要说LinkedList呢,大家可能都知道LinkedList和ArrayList一样都是List,有List的功能,不同之处在于ArrayList内部实现是数组,所以查询的效率比较高,但更新的效率较低,而LinkedList内部是双向链表,所以查询的效率比较低,但更新的效率较高。由于LinkedList内部实现是双向链表,通过双向链表这一结构,它又可以完成队列(双向队列),栈的功能,所以它在算法中的应用还是比较多的。下面就来具体说一说LinkedList。

    查询jdk1.8文档可以知道,LinkedList的继承结构是下面这样的:

    java.lang.Object
        java.util.AbstractCollection<E>
            java.util.AbstractList<E>
                java.util.AbstractSequentialList<E>
                    java.util.LinkedList<E>

    它继承了AbstractSequentialList,所以是个有序的List

    它实现了下面的接口:

    Serializable , Cloneable , Iterable <E>, Collection <E>, Deque <E>, List <E>, Queue <E>

    由于实现了Serializable , Cloneable , Iterable <E>,所以可以序列化,克隆与迭代操作,他既是一个List,又是一个Deque(双端队列,双端队列还可以实现队列和栈的功能)

    既然LinkedList内部是链表,那么查找的效率是不高的,如果用普通for循环去遍历,效率较低,如果换用增强的for循环或者迭代器进行遍历,那么效率就会提高,因为迭代时不是每次都从头部重新遍历,这是LinkedList使用时的一个小技巧。

    下面重点说一说做为双端队列(队列,栈)使用时的情况,双端队列即是两端都可以插入删除的队列,队列是在尾部插入,头部删除的数据结构,有先进先出的特点,栈是在一端插入删除,有先进后出的特点。当作为队列时,队头在List的索引最大处,队尾在索引0处。

    当用做栈时,常用的方法有下面四个:

    E peek() 查看栈顶元素
    void push(E e) 入栈
    E pop() 出栈
    boolean isEmpty() 判空

 

    当用做队列时,常用的方法有下面七个:

    boolean add(E e) 入队
    E remove() 出队
    E element() 查看队头元素

    上面三个方法,当因容量限制不能入队,空队列不能出队或查看队头元素时,会抛出异常,而下面三个类似操作是安全的,并不会抛出异常

    boolean offer(E e) 入队
    E poll() 出队
    E peek() 查看栈顶元素

    boolean isEmpty() 判空

 

    当用做双端队列时,常用的方法如下:

    void addFirst(E e)
    void addLast(E e)
    boolean offerFirst(E e)
    boolean offerLast(E e)

    上面四个方法在队头和队尾增加元素,add与offer的不同是offer是安全的,而add在容量超过限制时会抛出异常

    E getFirst()
    E getLast()

    E peekFirst()
    E peekLast()

    上面的四个方法查看队头队尾元素,get与peek的不同之处是peek是安全的,而get在队列为空时会抛出异常

    E removeFirst()
    E removeLast()
    E pollFirst()
    E pollLast()

    上面四个方法返回并删除队头队尾元素,remove与poll的不同之处在于poll是安全的,而remove在队列为空时会抛出异常

    boolean remove(Object o) 删除对应第一次出现的元素
    boolean removeFirstOccurrence(Object o) 删除对应第一次出现的元素
    boolean removeLastOccurrence(Object o) 删除对应最后一次出现的元素
    boolean contains(Object o) 判断是否包含一个元素
    int size() 计算队列的大小
    boolean isEmpty() 判断队列是否为空

    上面六个是增强和辅助的方法

    Iterator<E> iterator() 正向迭代器
    Iterator<E> descendingIterator() 反向迭代器

    上面两个返回迭代器

 

    LinkedList中的其它方法主要与他的列表属性相关,涉及到索引的操作,主要如下

    void add(int index, E element) 指定索引处增加元素
    boolean addAll(Collection<? extends E> c) 增加一个集合中的所有元素
    boolean addAll(int index, Collection<? extends E> c) 在指定索引处增加一个集合中的所有元素
    void clear() 清空
    E remove(int index) 删除指定索引处的元素
    E set(int index, E element) 修改指定索引处的元素
    E get(int index) 获取指定索引处的元素
    int indexOf(Object o) 获取指定元素的索引
    int lastIndexOf(Object o) 获取指定元素的最后一个索引
    ListIterator<E> listIterator(int index) 从指定索引开始的迭代器

    下面是一些辅助的方法

    Spliterator<E> spliterator() 迭代器,与Iterator不同的是这是并行迭代器
    Object clone() 浅克隆
    Object[] toArray() 转为数组
    <T> T[] toArray(T[] a) 转为指定类型的数组

    LinkedList在算法题中最大的用处就是作为队列(双端队列)或者栈使用了,作为栈使用时,可以代替Stack,因为Stack是线程安全的,所以一般使用时用LinkedList就可以了,另一个可以选择的双端队列是ArrayDeque,与LinkedList内部使用双向链表不同,ArrayDeque内部是用数组实现的。


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告