List 接口的链接列表实现。实现所有可选的列表操作,并且允许所有元素(包括 null)。除了实现 List 接口外,LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。
此类实现 Deque 接口,为 add、poll 提供先进先出队列操作,以及其他堆栈和双端队列操作。所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表(从靠近指定索引的一端)。
注意,此实现不是同步的。
如果多个线程同时访问一个链接列表,而其中至少一个线程从结构上修改了该列表,则它必须 保持外部同步。(结构修改指添加或删除一个或多个元素的任何操作;仅设置元素的值不是结构修改。)这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象,则应该使用 Collections.synchronizedList
方法来“包装”该列表。最好在创建时完成这一操作,以防止对列表进行意外的不同步访问,如下所示:
List list = Collections.synchronizedList(new LinkedList(...));
此类的 iterator 和 listIterator 方法返回的迭代器是快速失败 的:在迭代器创建之后,如果从结构上对列表进行修改,除非通过迭代器自身的 remove 或 add 方法,其他任何时间任何方式的修改,迭代器都将抛出 ConcurrentModificationException
。因此,面对并发的修改,迭代器很快就会完全失败,而不冒将来不确定的时间任意发生不确定行为的风险。
注意,迭代器的快速失败行为不能得到保证,一般来说,存在不同步的并发修改时,不可能作出任何硬性保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此,编写依赖于此异常的程序的方式是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测程序错误。
双端队列
堆栈
从 Queue 接口继承的方法完全等效于 Deque 方法,
Deque 一个线性 collection,支持在两端插入和移除元素。名称 deque 是“double ended queue(双端队列)”的缩写,通常读为“deck”。大多数 Deque 实现对于它们能够包含的元素数没有固定限制,但此接口既支持有容量限制的双端队列,也支持没有固定大小限制的双端队列。此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式:一种形式在操作失败时抛出异常,另一种形式返回一个特殊值(null 或 false,具体取决于操作)。插入操作的后一种形式是专为使用有容量限制的 Deque 实现设计的;在大多数实现中,插入操作不能失败。
//后进先出
public void stack(){
System.out.println("stack started");
Deque<Integer> stack = new LinkedList<Integer>();
for(int i=0;i<11;i++){
//如栈
stack.push(i);
}
//出栈
while(!stack.isEmpty()){
System.out.println(stack.pop());;
}
System.out.println("stack end");
}
//先进先出
public void queue(){
System.out.println("queue started");
Queue<Integer> queue = new LinkedList<Integer>();
for(int i=0;i<11;i++){
//入列
queue.offer(i);
}
while(!queue.isEmpty()){
//出队
System.out.println(queue.poll());;
}
System.out.println("queue end");
}
ArrayDeque
Deque
接口的大小可变数组的实现。数组双端队列没有容量限制;它们可根据需要增加以支持使用。它们不是线程安全的;在没有外部同步时,它们不支持多个线程的并发访问。禁止 null 元素。此类很可能在用作堆栈时快于 Stack
,在用作队列时快于 LinkedList
。大多数 ArrayDeque 操作以摊销的固定时间运行。异常包括remove
、removeFirstOccurrence
、removeLastOccurrence
、contains
、iterator.remove()
以及批量操作,它们均以线性时间运行。此类的 iterator 方法返回的迭代器是快速失败 的:如果在创建迭代器后的任意时间通过除迭代器本身remove 方法之外的任何其他方式修改了双端队列,则迭代器通常将抛出 ConcurrentModificationException
。因此,面对并发修改,迭代器很快就会完全失败,而不是冒着在将来不确定的时刻任意发生不确定行为的风险。
注意,迭代器的快速失败行为不能得到保证,一般来说,存在不同步的并发修改时,不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此,编写依赖于此异常的程序是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测 bug。
此类及其迭代器实现 Collection
和 Iterator
接口的所有可选 方法。
分享到:
相关推荐
ArrayDeque实现了Deque接口,LinkedList实现了Deque,List接口 (1)对比: ArrayDeque 为数组结构,插入元素不能为null,无法确定数据量时,后期扩容会影响效率 LinkedList 链表结构,插入元素不能为null,无法确定...
聊一聊java 的集合类 概述 Java中集合分为两种类型 第一种:以单个元素存储。其超级父接口是:java.util.Collection; 第二种:以键值对存储...Queue又有Deque、Stack、LinkedList SET 无序不可重复,没有下标。规定S
超全Java集合框架讲解 - 超全Java集合框架讲解 - 集合框架总览 - Iterator Iterable ListIterator - Map 和 Collection 接口 ... - LinkedList - Queue接口 - Deque 接口 - AbstractQueue 抽象类 - Lin
LinkedList同时实现了List接口和Deque接口,也是说它既可以看作一个顺序容器,又可以看作一个队列(Queue),同时又可以看作一个栈(Stack)。这样看来,LinkedList简直是个全能。当你需要使用栈或者队列时,可以...
LinkedList Queue接口Deque 接口 AbstractQueue 抽象类LinkedList ArrayDeque PriorityQueue 反射的思想及作用 反射的基本使用 获取类的 Class 对象构造类的实例化对象获取-个类的所有信息 获取类中的变量(Field) ...
链表(LinkedList) 单向链表 双向链表 循环链表 静态链表 栈(Stack) 队列(Queue) 双端队列(Deque) 循环队列 哈希表(HashTable) 树形数据结构 二叉树(BinaryTree)、二叉搜索树(BinarySearchTree、BST) ...
约瑟夫环 leetcode ...LinkedList双向链表实现解决约瑟夫环问题 04-栈 Stack利用java组合实现栈 05-队列 Queue队列实现 Deque双端队列实现 CircleQueue环形队列实现 CircleDeque环形双端队列实现 06-二叉树
吗啡 用JavaScript编写的完整数据结构库。 数据结构 堆 队列 出队 哈希图 哈希集 堆 链表 MultiHashMap 作者 Zakaria Maaraki-初期工作 执照 此项目已获得MIT许可证的许可-有关详细信息,请参阅文件
C宏集合 C语言中易于使用,仅标头,宏生成,通用和类型安全的数据结构。 目录 安装 无需安装。 整个库由头文件组成,可以直接包含在您的项目中。 贡献 有很多事情要做。 您可以检查存储库根目录中的TODO文件或...
Implementing a LinkedList Class ........................................................................................................... 16 The Node ...................................................