当前位置:首页 > 开发 > 互联网 > 正文

介绍些不主流的Collection的工具

发表于: 2013-10-10   作者:cywhoyi   来源:转载   浏览次数:
摘要: Common Definitions First, let’s start with some definitions. In common usage of the word, a queue is FIFO (first-in-first-out). Just like the first person in line at the post office gets served first

Common Definitions

First, let’s start with some definitions. In common usage of the word, a queue is FIFO (first-in-first-out). Just like the first person in line at the post office gets served first. A stack is LIFO (last in first out). Think of a stack of books – the last book you put on the stack is the first book you take off.

Choices in Java

In Java, things are a little more complicated, but the same principles apply. There is the aforementioned Queue interface which has the expected methods to add, remove and look at elements. (Actually, those methods come in two flavors: one throws an exception if the operation fails, the other returns a special value such as null or false; see more here).

There is also a sub-interface of Queue called Deque, short for “double ended queue” and is usually pronounced “deck”. This interface defines methods to access the elements at both ends of the collection. This functionality makes Deque a useful base for both queue and stack implementations.

However, both Queue and Deque are interfaces, so we still haven’t found a concrete implementation to use yet…

The shortlist: ArrayDeque & LinkedList

The 2 main choices are: ArrayDeque and LinkedList. There are a couple of other implementation of Deque such as ConcurrentLinkedDeque and LinkedBlockingDeque, and a plethora of implementations of Queue such as DelayQueue, LinkedBlockingDeque and PriorityQueue. Since those are more specialized (and I haven’t used them much), I won’t go into here.

ArrayDeque

From the javadocs, ArrayDeque is a resizable-array implementation of the Deque interface. Most ArrayDeque operations run in amortized constant time (i.e. slower “once in a while”, but on average constant) except for remove*, contains* and the bulk operations, all of which run in linear time. The docs point out that this class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue. It is this statement that leads me to use ArrayDeque as my default implmentation for both stacks and queues.

LinkedList

The LinkedList class implements the List, Queue and Deque interfaces. In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue.

LinkedList vs ArrayDeque

So, when would you use a LinkedList over an ArrayDeque?

Pros of a LinkedList implementation are:

  • more flexible than the ArrayDeque implementation, as it
    • implements all optional list operations.
    • allows null elements (not allowed in ArrayDeque)
  • well suited when you need to remove/insert items in the middle of the list frequently (something that can result in large array copies for the ArrayDeque).

Cons of a LinkedList implementation:

  • not ideal when iterating over items in general
  • consumes more memory than the ArrayDeque implementation

Overall

In terms of efficiency, ArrayDeque is more efficient than the LinkedList for iteration and add/remove operation at both ends. So, as the javadocs point out, in general, ArrayDeque is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

        

介绍些不主流的Collection的工具

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
Garbage Collection 译为垃圾收集器(以下简称GC),主要负责内存分配、确保所有被引用的对象保留在内
Garbage Collection 译为垃圾收集器(以下简称GC),主要负责内存分配、确保所有被引用的对象保留在内
原文: http://mobile.51cto.com/aengine-387752_all.htm 游戏引擎是指一些已编写好的可编辑电脑游
所谓的“浏览器内核”无非指的是一个浏览器最核心的部分——“Rendering Engine”,直译这个词汇叫
1 背景概述 由于在项目中需要在页面上显示数量非常多的数据, 在进行数据库查询时首先会把所有的数
The following list describes the core collection interfaces: Collection — the root of the co
collection 接口 Collection是最基本的集合接口. 所有实现Collection接口的类都必须提供两个标准的
移动Web开发语言被称为“第五次工业革命的原动力”,移动web开发有哪些优点呢? ◆易于开发,新用户
尽管大多数的互联网用户都在使用包括 IE、火狐和 Chrome 等主流浏览器,但互联网就是这么百花齐放,
一个快速加载网页在很大程度上节约用户的浏览页面时间成本,作为一名站长,我们要寻求一些解决办法
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号