16、Collection接口及其子接口Set和List(常用类LinkedList,ArrayList,Vector和Stack)

16、Collection接口

Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Elements)。一些Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类,Java SDK提供的类都是继承自Collection的“子接口”如List和Set。

  所有实现Collection接口的类都必须提供两个标准的构造函数:无参数的构造函数用于创建一个空的Collection,有一个Collection参数的构造函数用于创建一个新的Collection,这个新的Collection与传入的Collection有相同的元素。后一个构造函数允许用户复制一个Collection。

      遍历Collection中元素:不论Collection的实际类型如何,它都支持一个iterator()的方法,该方法返回一个迭代子,使用该迭代子即可逐一访问Collection中每一个元素。典型的用法如下:     Iterator it = collection.iterator();    // 获得一个迭代子     while(it.hasNext()) {       Object obj = it.next();              // 得到下一个元素     }

16.1、Set接口

      Set是一种不包含重复元素的Collection,即任意的两个元素e1和e2都有e1.equals(e2)=false,Set最多有一个null元素。Set的构造函数有一个约束条件,传入的Collection参数不能包含重复的元素。   请注意:必须小心操作可变对象(Mutable Object)。如果一个Set中的可变元素改变了自身状态,将导致Object.equals(Object)=true将导致一些问题。

16.2、List接口

      List是有序的Collection,使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引(元素在List中的位置,类似于数组下标)来访问List中的元素,类似于Java的数组。和上面的Set不同,List允许有相同的元素。   除了具有Collection接口必备的iterator()方法外,List还提供一个listIterator()方法,返回一个ListIterator接口,和标准的Iterator接口相比,ListIterator多了一些add()之类的方法,允许添加,删除,设定元素,还能向前或向后遍历。

16.2.1、List接口常用类

AbstractList 是一个抽象类,它继承于AbstractCollection。AbstractList实现List接口中除size()、get(int location)之外的函数。 AbstractSequentialList 是一个抽象类,它继承于AbstractList。AbstractSequentialList 实现了“链表中,根据index索引值操作链表的全部函数”。

ArrayList 是一个数组队列,相当于动态数组。它由数组实现,随机访问效率高,随机插入、随机删除效率低。 LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低,但随机插入、随机删除效率低。 Vector 是矢量队列,和ArrayList一样,它也是一个动态数组,由数组实现。但是ArrayList是非线程安全的,而Vector是线程安全的。 Stack 是栈,它继承于Vector。它的特性是:先进后出(FILO, First In Last Out)。

16.2.1.1、LinkedList类

       LinkedList实现了List接口,允许null元素。此外LinkedList提供额外的get,remove,insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈(stack),队列(queue)或双向队列(deque)。   注意LinkedList没有同步方法。如果多个线程同时访问一个List,则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List:     List list = Collections.synchronizedList(new LinkedList(...));

16.2.1.2、ArrayList类   ArrayList实现了可变大小的数组。它允许所有元素,包括null。ArrayList没有同步。size,isEmpty,get,set方法运行时间为常数。但是add方法开销为分摊的常数,添加n个元素需要O(n)的时间。其他的方法运行时间为线性。   每个ArrayList实例都有一个容量(Capacity),即用于存储元素的数组大小。这个容量可随着不断添加新元素而自动增加,但是增长算法并没有定义。当需要插入大量元素时,在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。和LinkedList一样,ArrayList也是非同步的(unsynchronized)。

16.2.1.3、Vector类   Vector非常类似ArrayList,但是Vector是同步的。由Vector创建的Iterator,虽然和ArrayList创建的Iterator是同一接口,但是,因为Vector是同步的,当一个Iterator被创建而且正在被使用,另一个线程改变了Vector的状态(例如,添加或删除了一些元素),这时调用Iterator的方法时将抛出ConcurrentModificationException,因此必须捕获该异常。 16.2.1.4、Stack 类   Stack继承自Vector,实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法,还有peek方法得到栈顶的元素,empty方法测试堆栈是否为空,search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

16.2.2、List接口使用场景

      如果涉及到“栈”、“队列”、“链表”等操作,应该考虑用List,具体的选择哪个List,根据下面的标准来取舍。

(01) 对于需要快速插入,删除元素,应该使用LinkedList。        通过add(int index, E element)向LinkedList插入元素时。先是在双向链表中找到要插入节点的位置index;找到之后,再插入一个新节点。双向链表查找index位置的节点时,有一个加速动作:若index < 双向链表长度的1/2,则从前向后查找; 否则,从后向前查找。        ArrayList的add(int index, E element)函数,会引起index之后所有元素的改变,会将index之后所有元素都向后移动一位,从而使ArrayList中插入元素很慢。“删除元素”与“插入元素”的原理类似。 (02) 对于需要快速随机访问元素,应该使用ArrayList。        通过get(int index)获取LinkedList第index个元素时。先是在双向链表中找到index位置的元素,找到之后再返回。双向链表查找index位置的节点时,有一个加速动作:若index < 双向链表长度的1/2,则从前向后查找; 否则,从后向前查找。        通过get(int index)获取ArrayList第index个元素时。直接返回数组中index位置的元素,而不需要像LinkedList一样进行查找。 (03) 对于“单线程环境” 或者 “多线程环境,但List仅仅只会被单个线程操作”,此时应该使用非同步的类(如ArrayList)。 (04) 对于“多线程环境,且List可能同时被多个线程操作”,此时,应该使用同步的类(如Vector)。

16.2.2.1、Vector和ArrayList比较

相同之处:      (1) 它们都是List,都继承于AbstractList,并且实现List接口。      (2) 它们都实现了RandomAccess和Cloneable接口。实现RandomAccess接口,意味着它们都支持快速随机访问;实现Cloneable接口,意味着它们能克隆自己。      (3) 它们都是通过数组实现的,本质上都是动态数组。ArrayList.java中定义数组elementData用于保存元素;Vector.java中也定义了数组elementData用于保存元素      (4) 它们的默认数组容量是10。若创建ArrayList或Vector时,没指定容量大小;则使用默认容量大小10。      (5) 它们都支持Iterator和listIterator遍历。它们都继承于AbstractList,而AbstractList中分别实现了 “iterator()接口返回Iterator迭代器” 和 “listIterator()返回ListIterator迭代器”。 不同之处:      (1) 线程安全性不一样。ArrayList是非线程安全;而Vector是线程安全的,它的函数都是synchronized的,即都是支持同步的。ArrayList适用于单线程,Vector适用于多线程。      (2) 对序列化支持不同。ArrayList支持序列化,而Vector不支持;即ArrayList有实现java.io.Serializable接口,而Vector没有实现该接口。      (3) 构造函数个数不同。ArrayList有3个构造函数,而Vector有4个构造函数。Vector除了包括和ArrayList类似的3个构造函数之外,另外的一个构造函数可以指定容量增加系数。           ArrayList的构造函数如下: // 默认构造函数 ArrayList() // capacity是ArrayList的默认容量大小。当由于增加数据导致容量不足时,容量会添加上一次容量大小的一半。 ArrayList(int capacity) // 创建一个包含collection的ArrayList ArrayList(Collection<? extends E> collection)           Vector的构造函数如下: // 默认构造函数 Vector() // capacity是Vector的默认容量大小。当由于增加数据导致容量增加时,每次容量会增加一倍。 Vector(int capacity) // 创建一个包含collection的Vector Vector(Collection<? extends E> collection) // capacity是Vector的默认容量大小,capacityIncrement是每次Vector容量增加时的增量值。 Vector(int capacity, int capacityIncrement)       (4) 容量增加方式不同。逐个添加元素时,若ArrayList容量不足时,“新的容量”=“(原始容量x3)/2 + 1”;而Vector的容量增长与“增长系数有关”,若指定了“增长系数”,且“增长系数有效(即,大于0)”;那么,每次容量不足时,“新的容量”=“原始容量+增长系数”。若增长系数无效(即,小于/等于0),则“新的容量”=“原始容量 x 2”。       (5) 对Enumeration的支持不同。Vector支持通过Enumeration去遍历,而List不支持

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

集合类操作优化经验总结

在实际的项目开发中会有很多的对象,如何高效、方便地管理对象,成为影响程序性能与可维护性的重要环节。Java 提供了集合框架来解决此类问题,线性表、链表、哈希表等...

562
来自专栏软件开发 -- 分享 互助 成长

装饰模式

一、相关介绍 1、装饰模式是为已有功能动态地添加更多功能的一种方式。 2、举例:QQ中的服装秀可以动态的搭配不同的服饰来进行修饰。 3、UML图 ? 4、所属类...

1759
来自专栏Java编程

Java基础—String、StringBuffer、StringBuilder

我有一个微信公众号,经常会分享一些Java技术相关的干货。如果你喜欢我的分享,可以用微信搜索“Java团长”或者“javatuanzhang”关注。

3540
来自专栏xingoo, 一个梦想做发明家的程序员

Java程序员的日常 —— 《编程思想》持有对象

集合框架可以说是Java里面必备的知识点了,日常的使用中也会遇到各种情况需要使用到集合。下面就简单介绍下各种集合的使用场景: ? List List可以看...

1988
来自专栏JavaEE

Java的反射机制前言:Java反射的使用:总结:

1024
来自专栏angularejs学习篇

c#中jeson字符串和OBJECT对象的相互转换

说明:首先,当然是项目是3.5+的;必须添加引用:System.Runtime.Serialization 和 System.ServiceModel

622
来自专栏大数据钻研

Java集合类操作优化经验总结

本文首先针对 Java 集合接口进行了一些介绍,并对这些接口的实现类进行详细描述,包括 LinkedList、ArrayList、Vector、Stack、Ha...

34916
来自专栏JAVA高级架构

Java常见面试题及答案 21-30(集合类)

21.HashMap的工作原理是什么? HashMap内部是通过一个数组实现的,只是这个数组比较特殊,数组里存储的元素是一个Entry实体(jdk 8为Node...

2515
来自专栏互联网开发者交流社区

ArrayList Vector LinkedList(一)

896
来自专栏好好学java的技术栈

“面试不败计划”:集合知识整体总结

1213

扫码关注云+社区