1、Collection集合
2、Map集合
* 图片中略掉抽象类
1)Collection继承接口Iterable,所以其子类都可通过迭代器遍历元素。为了保证速度ArrayList适合用
for循环,LinkedList适合用迭代器
public static <T> void method(List<? super T> list) { int size = list.size(); //RandomAccess标记接口,由此标记,最好用for循环遍历 if ( list instanceof RandomAccess) { for (int i=0; i<size; i++){ //.... } } else { ListIterator<? super T> itr = list.listIterator(); for (int i=0; i<size; i++) { itr.next(); //.... } } }
2)Map 可以通过entrySet()、keySet()方法,得到一个Set集合进行迭代器遍历。
3)ListIterator可以向前和向后进行迭代
1)ArrayList<E>
数据结构:数组(线性序列)
适合操作:根据数据结构,善于随机访问元素,但是在其中间插入和移除元素时较慢
基本介绍:初始化时可设置数组容量大小,当实际元素个数size大于数组容量,对其进行扩容。因为其数
据结构是数组,每次查询可根据下标直接查到元素。删除一个元素时,后面元素统一向前移
一位。
2)LinkedList<E>
数据结构:双向链表
适合操作:根据数据结构,不善于随机访问元素,但是在其中间插入和移除元素时较快
基本介绍:每个元素都是一个Node,除了元素值位,还有一个指向左右的引用。每次增删Node,只需要改
变左右的引用指向即可,不用移动元素
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
3)Vector<E>
数据结构:跟ArrayList的数据结构一样(数组)
适合操作:跟ArrayList一样,因同步的,所以没有ArrayList快
基本介绍:其方法与ArrayList也基本相同,只是在增、删、改、查等方法前加了synchronized关键字。
单线程中不需使用,即使使用后台的编译期也会进行对其进行优化,消除同步代码。多线程中
一般也很少使用,因为速度比较慢,而且组合操作(如果存在删除)无法实现线程安全。
4)Stack<E>栈
数据结构:继承Vector (数组) ,可用LinkedList链表实现。
适合操作:“栈”,先进后出的容器,只有一个口,一端放入元素,同一端取出元素
应用:1)平衡符号:栈中:{{【{( 站外:)}】}} ,从栈中向外弹出元素做比较。
2)后缀表达式: 表达式a+b*c+(d*e+f)*g 转成后缀:abc*+de*f+g*+ ,先将abc压栈,遇到*,bc出栈做
乘法,结果x=b*c继续压入栈中,然后遇到+弹出ax做加法,,,,,,,
基本介绍: LinkedList能够直接实现栈的所有功能的方法,因此可以直接将LinkedList作为栈使用。
public class StackLinked<T> { private LinkedList<T> linked = new LinkedList<T>(); public T peek(){ return linked.getFirst(); } public T pop(){ return linked.removeFirst(); } public void push(T t){ linked.addFirst(t); } public boolean isEntry(){ return linked.isEmpty(); } @Override public String toString() {return linked.toString();} }
5)Queue<E> 队列
数据结构:数组(ArrayDeque)、链表(LinkedList)
适合操作:队列,先进先出的容器,从容器的一端放入事物, 从另一端取出
应用:并发,只是说思想,具体应用这里不介绍
基本介绍:放入顺序与取出顺序相同。
Queue<String> queueLinked = new LinkedList<String>(); Queue<String> queueArray = new ArrayDeque<String>();
6)PriorityQueue<E> 优先队列
数据结构:堆(数组)。
适合操作:优先队列,声明下一个弹出的元素是最需要的元素(最大值/最小值具有最高优先级)
基本介绍: 根据堆的性质,每次在[0]位置的都是最大或最小的元素。因为要进 行排序所以元素要实现接
口Comparator<T>。堆排介绍
public static void main(String[] args) { Queue<Integer> queue = new PriorityQueue<Integer>(Arrays.asList(1, 3, 5, 4, 6)); while (!queue.isEmpty()) { System.err.println(queue.remove());// 1 3 4 5 6 } }
7)Deque<E> 双向队列
数据结构:数组(ArrayDeque)、链表(LinkedList)
适合操作:双向队列,可以在任何一端添加或删除元素
基本介绍:因为ArrayDeque、LinkedList都实现了Deque接口,所以可以通过向上转型使用Deque
Deque<String> dequeLinked = new LinkedList<String>(); Deque<String> dequeArray = new ArrayDeque<String>();
8)HashMap<K,V>
数据结构:散列(数组+单向链表)
适合操作:当get()时使用线性搜索,执行速度会很慢,而HashMap通过散列码可以很快定位元素位置。
基本介绍:1)每个元素都是一个Entry<K,V>对象,其底层通过Entry<K,V>数组来存储元素,每
个Entry<K,V>对象中会有一个next属性来实现单向链表
2)通过hash算法(利用K的hashCode)为每个Entry的K生成一个hash值,然后根据hash值
和数组length算出Entry在数组中的位置。
3)不同的K可能生成相同的hash值,即会存储在数组的同一个位置,这时通过for循环用
equals比较当前位置的链表元素,如果是false将新插入的值放入计算出来的位置,
然后next指向oldEntry,如果是false,则替换value
4) 装(负)载因子默认是075,即当数组75%的位置都有值时,对数组进行扩容length*2,然后重新
计算每个元素在数组中的位置。
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } public final K getKey() { return key; } public final V getValue() { return value; } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } public final int hashCode() { return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()); } public final String toString() { return getKey() + "=" + getValue(); } void recordAccess(HashMap<K,V> m) { } void recordRemoval(HashMap<K,V> m) { } }
9)HashSet<E>
数据结构:散列
适合操作:无重复元素,可以快速超找到对象。
基本介绍:HashSet的元素可以看作是HashMap的key没有重复元素,查找块。所以HashSet的底层实现就
是HashMap
10)LinkedHashMap<K,V>
数据结构:散列,双向链表
适合操作:具有HashMap的查询速度,内部使用双向链表维护顺序(插入次序),迭代遍历按插入顺序显
示,因为使用链表维护内部顺序,所以迭代访问很快。
基本介绍:继承自HashMap,每个元素Entry<K,V>多出两个指向两边元素的引用来维护顺序。
private static class Entry<K,V> extends HashMap.Entry<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, HashMap.Entry<K,V> next) { super(hash, key, value, next); } private void remove() { before.after = after; after.before = before; } private void addBefore(Entry<K,V> existingEntry) { after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; } void recordAccess(HashMap<K,V> m) { LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; if (lm.accessOrder) { lm.modCount++; remove(); addBefore(lm.header); } } void recordRemoval(HashMap<K,V> m) { remove(); } }
11)LinkedHashSet<E>
数据结构:散列,双向链表
适合操作:无重复元素,可以快速超找到对象。迭代遍历按插入顺序显示
基本介绍:LinkedHashSet的元素可以看作是LinkedHashMap的key没有重复的有序元素,
所以LinkedHashSet的底层实现就是LinkedHashMap
12)TreeMap<K,V>
数据结构:红黑树
适合操作:对元素自动排序
基本介绍:下面是Entry<K,V>的属性。TreeMap会对K自动排序,次序由Comparable或Comparator决定,
TreeMap中的元素都是有序的,如果键被用于TreeMap,那么必须实现Comparable。
红黑树:一种自平衡的二叉树。在实践中是高效的,它可以在O(log n)时间内做查找,插入和删除,
这里的n是树中元素的数目。
学习红黑树建议: 先学习二叉查找树,然后学习平衡(AVL)树,再然后是红黑树
介绍:红黑树是内排(内存排序)中非常完美的结构,因为每种操作增、删、改、查时间复杂度都是
O(log n),再继续扩展的话就是b树,这种结构一般用来将数据存储在硬盘中,可用在数据库中。
对List集合排序可以用帮助类Collections.sort(),Arrays.sort()可对数组排序。
K key; V value; Entry<K,V> left = null; //左节点 Entry<K,V> right = null;//右节点 Entry<K,V> parent; //父节点 boolean color = BLACK;
13)TreeSet<E>
数据结构:红黑树
基本介绍:通过TreeMap实现,功能参照TreeMap
相关推荐
数据结构 和 Java集合框架
java数据结构及集合框架
Java数据结构和Java集合框架
学生通过学习方法描述和应用,可以逐步理解并有效地使用数据结构,还可以了解这些数据结构的多种实现,包括在Java集合框架中提供的一些实现。 本书内容非常丰富,且在每章章尾提供编程项目,以帮助学生提高实践能力...
清华大学出版社《数据结构和Java集合框架》源代码。
《数据结构和java集合框架》(Data Structures and the Java Collections Frameword)[美]William J.Collins 著 高清PDF格式 【共4个压缩包】 第1个
《数据结构和java集合框架》(Data Structures and the Java Collections Frameword)[美]William J.Collins 著 高清PDF格式[共2个压缩包】 第2个
java 集合泛型+数据结构
学生通过学习方法描述和应用,可以逐步理解并有效地使用数据结构,还可以了解这些数据结构的多种实现,包括在Java集合框架中提供的一些实现。 本书内容非常丰富,且在每章章尾提供编程项目,以帮助学生提高实践能力...
作者采用了独特的方法将数据结构分成说明和实现两部分,并充分利用了已有的数据结构库(Java集合类API)。本书分为四个部分:第一部分讨论适合大多数应用的集合类API的一个子集,并覆盖基本的算法分析技术、递归和...
JAVA版本的数据结构,里面主要阐述了各种集合结构的应用。
java数据结构经典例题 java 数据结构 算法 程序 代码……一个集合这么多知识的宝贵资源!希望对学习的朋友有帮助!
2.Java集合与数据结构.rar
作者采用了独特的方法将数据结构分成说明和实现两部分,并充分利用了已有的数据结构库(Java集合类API)。本书分为四个部分:第一部分讨论适合大多数应用的集合类API的一个子集,并覆盖基本的算法分析技术、递归和...
Java 设计 数据结构 集合 自己实现Java集合框架。
[数据结构和Java集合框架]源代码 [数据结构和Java集合框架]源代码