武清区网站建设,中国铁建华南建设有限公司网站,北京网站策划联系电话,阿里云网站建设 部署与发布Java常用数据结构
Java中有几种常用的数据结构#xff0c;主要分为Collection和map两个主要接口#xff08;接口只提供方法#xff0c;并不提供实现#xff09;#xff0c;而程序中最终使用的数据结构是继承自这些接口的数据结构类。
一、几个常用类的区别 1#xff0e…Java常用数据结构
Java中有几种常用的数据结构主要分为Collection和map两个主要接口接口只提供方法并不提供实现而程序中最终使用的数据结构是继承自这些接口的数据结构类。
一、几个常用类的区别 1ArrayList: 元素单个效率高多用于查询 2Vector: 元素单个线程安全多用于查询 3LinkedList:元素单个多用于插入和删除 4HashMap: 元素成对元素可为空 5HashTable: 元素成对线程安全元素不可为空 二、Vector、ArrayList和LinkedList 大多数情况下从性能上来说ArrayList最好但是当集合内的元素需要频繁插入、删除时LinkedList会有比较好的表现但是它们三个性能都比不上数组另外Vector是线程同步的。所以 如果能用数组的时候(元素类型固定数组长度固定)请尽量使用数组来代替List 如果没有频繁的删除插入操作又不用考虑多线程问题优先选择ArrayList 如果在多线程条件下使用可以考虑Vector 如果需要频繁地删除插入LinkedList就有了用武之地 如果你什么都不知道用ArrayList没错。 三、Collections和Arrays 在Java集合类框架里有两个类叫做Collections注意不是Collection和Arrays这是JCF里面功能强大的工具但初学者往往会忽视。按JCF文档的说法这两个类提供了封装器实现Wrapper Implementations、数据结构算法和数组相关的应用。 想必大家不会忘记上面谈到的“折半查找”、“排序”等经典算法吧Collections类提供了丰富的静态方法帮助我们轻松完成这些在数据结构课上烦人的工作 binarySearch折半查找。 sort排序这里是一种类似于快速排序的方法效率仍然是O(n * log n)但却是一种稳定的排序方法。 reverse将线性表进行逆序操作这个可是从前数据结构的经典考题哦 rotate以某个元素为轴心将线性表“旋转”。 swap交换一个线性表中两个元素的位置。 …… Collections还有一个重要功能就是“封装器”Wrapper它提供了一些方法可以把一个集合转换成一个特殊的集合如下 unmodifiableXXX转换成只读集合这里XXX代表六种基本集合接口Collection、List、Map、Set、SortedMap和SortedSet。如果你对只读集合进行插入删除操作将会抛出UnsupportedOperationException异常。 synchronizedXXX转换成同步集合。 singleton创建一个仅有一个元素的集合这里singleton生成的是单元素Set singletonList和singletonMap分别生成单元素的List和Map。 空集由Collections的静态属性EMPTY_SET、EMPTY_LIST和EMPTY_MAP表示。
ArrayList实现了可变大小的数组。它允许所有元素包括null。ArrayList没有同步
LinkedList实现了List接口允许null元素。此外LinkedList提供额外的getremove insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈stack 队列queue或双向队列deque。
Vector非常类似ArrayList但是Vector是同步的。
Stack继承自Vector实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。 基本的push和pop方法还有peek方法得到栈顶的元素empty方法测试堆栈是否为空 search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。
Set是一种不包含重复的元素的Collection即任意的两个元素e1和e2都有e1.equals(e2)false Set最多有一个null元素。
Hashtable继承Map接口实现一个key-value映射的哈希表。任何非空non-null的对象都可作为key或者value。
HashMap和Hashtable类似不同之处在于HashMap是非同步的并且允许null即null value和null key。
WeakHashMap是一种改进的HashMap它对key实行“弱引用”如果一个key不再被外部所引用 那么该key可以被GC回收。
Java 线性表
ArrayList类
使用普通的数组来存储对象太过麻烦因为数组的一个很大的弱点就是长度从一开始就固定了所以Java提供了另一个容器 java.util.ArrayList 集合类,让我们可以更便捷的存储和操作对象数据。
ArrayList是一个可变大小的数组。它允许存储所有元素包括null它是基于数组实现的List类。
ArrayList没有同步。sizeisEmptygetset方法运行时间为常数。
该类封装了一个动态再分配的Object[]数组每一个类对象都有一个capacity属性表示它们所封装的Object[]数组的长度当向ArrayList中添加元素时该属性值会自动增加。
但是她的add方法开销为分摊的常数添加n个元素需要O(n)的时间。其他的方法运行时间为线性。 每个ArrayList实例都有一个容量Capacity即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加。
如果想ArrayList中添加大量元素可使用ensureCapacity方法一次性增加capacity可以减少增加重分配的次数提高性能。
ArrayList类常用方法
构造方法ArrayList()构造一个初值为空容量为10 的list。ArrayList(Collection? extends E c)构造一个元素包含collection的list顺序按照iterator来进行。c表示这个集合需要用来代替原来list中的元素。ArrayList(int initialCapacity)构造一个指定容量的空数组。使用方法add(Object element) 向列表的尾部添加指定的元素。size() 返回列表中的元素个数。get(int index) 返回列表中指定位置的元素index从0开始。add(int index, Object element) 在列表的指定位置插入指定元素。set(int i, Object element) 将索引i位置元素替换为元素element并返回被替换的元素。clear() 从列表中移除所有元素。isEmpty() 判断列表是否包含元素不包含元素则返回 true否则返回false。contains(Object o) 如果列表包含指定的元素则返回 true。remove(int index) 移除列表中指定位置的元素并返回被删元素。remove(Object o) 移除集合中第一次出现的指定元素移除成功返回true否则返回false。iterator() 返回按适当顺序在列表的元素上进行迭代的迭代器。LinkedList类
LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作LinkedList 是非同步的。
LinkedList 实现 List 接口能对它进行队列操作。
LinkedList 实现 Deque 接口即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口即覆盖了函数clone()能克隆。
LinkedList 实现java.io.Serializable接口这意味着LinkedList支持序列化能通过序列化去传输。
JDK1.6的时候是Entry结点实现的JDK1.7开始改用Node结点实现。
LinkedList也是线性表类之一与ArrayList相比两者存在一些相同点和区别。
ArrayList 底层是数组结构适合多查询少插入删除元素。
LinkedList 底层是链表结构适合多插入删除元素少查询操作。
常用方法
构造
public LinkedList() {header.next header.previous header;}public LinkedList(Collection? extends E c) {this();addAll(c);常用方法public void addFirst(Object element)向链表表头添加一个新节点该节点中的数据是参数element指定的对象。public void addLast(Object element)向链表表尾添加一个新节点该节点中的数据是参数element指定的对象。public Object removeFirst()删除第一个节点并返回这个节点中的对象。public Object removeLast()删除最后一个节点并返回这个节点中的对象。public Object remove(int index)删除指定位置的节点。public Object get(int index)得到指定位置的节点。public Object getFirst()得到链表第一个节点的对象。public Object getLast()得到链表最后一个节点的对象int indexOf(Object element) 返回节点对象element在链表中首次出现的位置如果链表中无此节点的对象则返回-1public int lastIndexOf(Object element)返回节点对象element在链表中最后出现的位置如果链表中无此节点的对象则返回-1public Object set(int index,Object element)将当前链表index位置节点中的对象替换成参数element指定的对象返回被替换对象public int size()返回链表的长度即节点个数。
