Java集合的Queue和LinkedList怎么使用
导读:本文共10435.5字符,通常情况下阅读需要35分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: LinkedList概述LinkedList与ArrayList一样实现List接口,只是ArrayList是List接口的大小可变数组的实现,LinkedList是List接口链表的实现。基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList,而随机访问则比ArrayList逊色些。LinkedList实现所有可选的列表操作,并允许所... ...
目录
(为您整理了一些要点),点击可以直达。LinkedList与ArrayList一样实现List接口,只是ArrayList是List接口的大小可变数组的实现,LinkedList是List接口链表的实现。基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList,而随机访问则比ArrayList逊色些。
LinkedList实现所有可选的列表操作,并允许所有的元素包括null。
除了实现 List 接口外,LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。
此类实现 Deque 接口,为 add、poll 提供先进先出队列操作,以及其他堆栈和双端队列操作。
所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表(从靠近指定索引的一端)。
同时,与ArrayList一样此实现不是同步的。
首先我们先看LinkedList的定义:
在LinkedList中提供了两个基本属性size、header。
private transient Entry
private transient int size = 0;
其中size表示的LinkedList的大小,header表示链表的表头,Entry为节点对象。
LinkedList提供了两个构造方法:LinkedList()和LinkedList(Collection<? extends E> c)。
LinkedList()构造一个空列表。里面没有任何元素,仅仅只是将header节点的前一个元素、后一个元素都指向自身。
LinkedList(Collection<? extends E> c): 构造一个包含指定 collection 中的元素的列表,这些元素按其 collection 的迭代器返回的顺序排列。该构造函数首先会调用LinkedList(),构造一个空列表,然后调用了addAll()方法将Collection中的所有元素添加到列表中。以下是addAll()的源代码:
从该方法有两个遍历方向中我们也可以看出LinkedList是双向链表,这也是在构造方法中为什么需要将header的前、后节点均指向自己。
如果对数据结构有点了解,对上面所涉及的内容应该问题,我们只需要清楚一点:LinkedList是双向链表,其余都迎刃而解。
由于篇幅有限,下面将就LinkedList中几个常用的方法进行源码分析。
在addBefore方法中无非就是做了这件事:构建一个新节点newEntry,然后修改其前后的引用。
LinkedList还提供了其他的增加方法:
该方法首先会判断移除的元素是否为null,然后迭代这个链表找到该元素节点,最后调用remove(Entry
其他的移除方法:
Queue接口定义了队列数据结构,元素是有序的(按插入顺序),先进先出。Queue接口相关的部分UML类图如下:
DeQueue(Double-ended queue)为接口,继承了Queue接口,创建双向队列,灵活性更强,可以前向或后向迭代,在队头队尾均可心插入或删除元素。它的两个主要实现类是ArrayDeque和LinkedList。
优先队列跟普通的队列不一样,普通队列是一种遵循FIFO规则的队列,拿数据的时候按照加入队列的顺序拿取。 而优先队列每次拿数据的时候都会拿出优先级最高的数据。
优先队列内部维护着一个堆,每次取数据的时候都从堆顶拿数据(堆顶的优先级最高),这就是优先队列的原理。
先执行 siftDown() 下滤过程:
再执行 siftUp() 上滤过程:
1、jdk内置的优先队列PriorityQueue内部使用一个堆维护数据,每当有数据add进来或者poll出去的时候会对堆做从下往上的调整和从上往下的调整。
2、PriorityQueue不是一个线程安全的类,如果要在多线程环境下使用,可以使用 PriorityBlockingQueue 这个优先阻塞队列。其中add、poll、remove方法都使用 ReentrantLock 锁来保持同步,take() 方法中如果元素为空,则会一直保持阻塞。
Java集合的Queue和LinkedList怎么使用的详细内容,希望对您有所帮助,信息来源于网络。