集合框架
集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。任何集合框架都包含三大块内容：对外的接口、接口的实现和对集合运算的算法（接口：即表示集合的抽象数据类型。实现：也就是集合框架中接口的具体实现。实际上它们就是那些可复用的数据结构。算法：在一个实现了某个集合框架中的接口的对象身上完成某种有用的计算的方法，例如查找、排序等。这些算法通常是多态的，因为相同的方法可以在同一个接口被多个类实现时有不同的表现。事实上，算法时可复用的函数）
-
开发应用程序时，如果想存储多个同类型的数据，可以用数组来实现；但是使用数组存在如下一些明显缺陷：
数组长度固定不变，不能很好的适应元素数量的动态变化情况。
可通过数组名.length获取数组的长度，却无法直接获取数组中实际存储的元素个数。
数组采用在内存中分配连续空间的存储方式存储，根据元素信息查找时效率比较低，需要多次比较。
- 针对数组的缺陷Java提供了比数组更灵活、更实用的集合框架，可大大提高软件的开发效率，并且不同的集合可适用于不同应用场合
[图片上传失败...(image-fc2d50-1571024730637)]
- Java的集合类主要有Map接口和Collection接口派生而来，其中Collection接口有两个常用的子接口，即List接口和Set接口，所以通常说Java集合框架由3大类接口构成（Map接口、List接口和Set接口）。Java集合就像一个容器，可以存储任何类型的数据，也可以结合泛型来存储具体的类型对象。在运行程序时，Java集合可以动态的进行扩展，随着元素的增加而扩大。在Java中集合主要有两大体系构成，分别是Collection体系和Map体系，其中Collection和Map分别是两大体系中的顶层几口
- img
- img
- 虚线框表示接口或者抽象类，实现框表示开发中常用的实现类
List接口
- Collection接口时最基本的集合接口。它主要有三个子接口分别为List（列表）、Set（集）、Queue（列队）
[图片上传失败...(image-409d9f-1571024730637)]
List接口继承自Collection接口，是有序集合，可以使用索引访问List接口中的元素，类似于数组。List接口中允许存放重复元素，也就是说List可以存储一组不唯一有序的对象。
List接口常用的实现类有ArrayList和LinkedList。
使用ArrayList类动态存储数据
针对数组的一些缺陷，Java集合框架提供了ArrayList集合类，对数组进行了封装，实现了长度可变的数组，而且和数组采用相同的方式存储，在内存中分配连续的空间，所以经常称ArrayList为动态数组。该集合中可以添加任何类型的数据，并且添加的数据都将转换成Object类型，而在数组中只能添加同一数据类型的数据。ArrayList底层通过数组实现，随着元素的增加而动态扩容。它是一个数组队列，是线程不安全的。
- 特点：容量不固定，随着容量的增加而动态扩容（阈值基本不会达到）
- 有序集合（插入的顺序==输出的顺序）
- 插入的元素可以为null
- 增删改查效率更高（相对于LinkedList来说）
- 线程不安全
-
数据结构：img
-
ArrayList类常用的方法：
boolen add(Object o) 在列表的末尾添加元素o，起始索引位置从0开始
void add(int index,Object o) 在指定的索引位置添加元素o，索引位置必须介于0和列表中元素个数之间。
int size()返回列表中的元素个数。
Object get(int index)返回指定索引位置出的元素，取出的元素是Object类型，使用前需要进行强制类型转换
void set(int index,Object obj)将index索引位置的元素替换为obj元素
boolean contains(Object o)判断列表中是否存在指定元素o
int indextOf(Object obj)返回元素在集合中出现的索引位置
-
基本操作
public class ArrayListTest { public static void main(String[] agrs){ //创建ArrayList集合： List<String> list = new ArrayList<String>(); System.out.println("ArrayList集合初始化容量："+list.size()); //添加功能： list.add("Hello"); list.add("world"); list.add(2,"!"); System.out.println("ArrayList当前容量："+list.size()); //修改功能： list.set(0,"my"); list.set(1,"name"); System.out.println("ArrayList当前内容："+list.toString()); //获取功能： String element = list.get(0); System.out.println(element); //迭代器遍历集合：(ArrayList实际的跌倒器是Itr对象) Iterator<String> iterator = list.iterator(); while(iterator.hasNext()){ String next = iterator.next(); System.out.println(next); } //for循环迭代集合： for(String str:list){ System.out.println(str); } //判断功能： boolean isEmpty = list.isEmpty(); boolean isContain = list.contains("my"); //长度功能： int size = list.size(); //把集合转换成数组： String[] strArray = list.toArray(new String[]{}); //删除功能： list.remove(0); list.remove("world"); list.clear(); System.out.println("ArrayList当前容量："+list.size()); } }
在编程中将接口的引用指向实现类的对象是Java实现多态的一种形式，也是软件开发中实现低耦合的方式之一，这样的用法可以大大提高程序的灵活性
ArrayList集合因为可以使用索引来直接获取元素，所以其优点是遍历元素和随机访问元素的效率比较高。但由于ArrayList集合采用了和数组相同的存储方式，在内存中分配连续的空间，因此在添加和删除非尾部元素时会导致后面所有元素的移动，这就造成在插入、删除等操作频繁的应用场景下使用ArrayList会导致效率低下。
使用LinkedList类动态存储数据
LinkedList类是List接口的链接列表实现类。它支持实现所有List接口可选的列表的操作，并且允许元素值是任何数据，包括null
LinkedList类采用链表方式存储数据，优点在于插入、删除元素时效率比较高，但是LinkedList类的查找效率很低
- img
上图为LinkedList类的底层数据结构
-
LinkedList类的常用方法：
- void addFirst(Object obj)将指定元素插入到当前集合的首部
- void addLast(Object obj)将指定元素插入到当前集合的尾部
- Object getFirst()获得当前集合的第一个元素
- Object getLast()获得当前集合的最后一个元素
- Object removeFirst()移除并返回当前集合的第一个元素
- Object removeLast()移除并返回当前集合的最后一个元素
LinkedList类和ArrayList类所包含的大部分方法时完全一样的，这主要时因为它们都是List 接口的实现类。由于ArrayList采用和数组一样的连续的顺序存储方式，当对数据频繁检索时效率比较高，而LinkedList类采用链表存储方式，对数据添加、删除或修改比较多时，建议选择LinkedList类型存储数据
public class LinkedList<E>extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { transient int size = 0; //LinkedList中存放的元素个数 transient Node<E> first; //头节点 transient Node<E> last; //尾节点 //构造方法，创建一个空的列表 public LinkedList() { } //将一个指定的集合添加到LinkedList中，先完成初始化，在调用添加操作 public LinkedList(Collection<? extends E> c) { this(); addAll(c); } //插入头节点 private void linkFirst(E e) { final Node<E> f = first; //将头节点赋值给f节点 //new 一个新的节点，此节点的data = e , pre = null , next - > f final Node<E> newNode = new Node<>(null, e, f); first = newNode; //将新创建的节点地址复制给first if (f == null) //f == null，表示此时LinkedList为空 last = newNode; //将新创建的节点赋值给last else f.prev = newNode; //否则f.前驱指向newNode size++; modCount++; } //插入尾节点 void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } //在succ节点前插入e节点，并修改各个节点之间的前驱后继 void linkBefore(E e, Node<E> succ) { // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; } //删除头节点 private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; } //删除尾节点 private E unlinkLast(Node<E> l) { // assert l == last && l != null; final E element = l.item; final Node<E> prev = l.prev; l.item = null; l.prev = null; // help GC last = prev; if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; } //删除指定节点 E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; //获取指定节点的前驱 final Node<E> prev = x.prev; //获取指定节点的后继 if (prev == null) { first = next; //如果前驱为null, 说明此节点为头节点 } else { prev.next = next; //前驱结点的后继节点指向当前节点的后继节点 x.prev = null; //当前节点的前驱置空 } if (next == null) { //如果当前节点的后继节点为null ,说明此节点为尾节点 last = prev; } else { next.prev = prev; //当前节点的后继节点的前驱指向当前节点的前驱节点 x.next = null; //当前节点的后继置空 } x.item = null; //当前节点的元素设置为null ,等待垃圾回收 size--; modCount++; return element; } //获取LinkedList中的第一个节点信息 public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; } //获取LinkedList中的最后一个节点信息 public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; } //删除头节点 public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } //删除尾节点 public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } //将添加的元素设置为LinkedList的头节点 public void addFirst(E e) { linkFirst(e); } //将添加的元素设置为LinkedList的尾节点 public void addLast(E e) { linkLast(e); } //判断LinkedList是否包含指定的元素 public boolean contains(Object o) { return indexOf(o) != -1; } //返回List中元素的数量 public int size() { return size; } //在LinkedList的尾部添加元素 public boolean add(E e) { linkLast(e); return true; } //删除指定的元素 public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } //将集合中的元素添加到List中 public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } //将集合中的元素全部插入到List中，并从指定的位置开始 public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); Object[] a = c.toArray(); //将集合转化为数组 int numNew = a.length; //获取集合中元素的数量 if (numNew == 0) //集合中没有元素，返回false return false; Node<E> pred, succ; if (index == size) { succ = null; pred = last; } else { succ = node(index); //获取位置为index的结点元素，并赋值给succ pred = succ.prev; } for (Object o : a) { //遍历数组进行插入操作。修改节点的前驱后继 @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; } if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; } //删除List中所有的元素 public void clear() { // Clearing all of the links between nodes is "unnecessary", but: // - helps a generational GC if the discarded nodes inhabit // more than one generation // - is sure to free memory even if there is a reachable Iterator for (Node<E> x = first; x != null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; } //获取指定位置的元素 public E get(int index) { checkElementIndex(index); return node(index).item; } //将节点防止在指定的位置 public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; } //将节点放置在指定的位置 public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } //删除指定位置的元素 public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } //判断索引是否合法 private boolean isElementIndex(int index) { return index >= 0 && index < size; } //判断位置是否合法 private boolean isPositionIndex(int index) { return index >= 0 && index <= size; } //索引溢出信息 private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; } //检查节点是否合法 private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } //检查位置是否合法 private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } //返回指定位置的节点信息 //LinkedList无法随机访问，只能通过遍历的方式找到相应的节点 //为了提高效率，当前位置首先和元素数量的中间位置开始判断，小于中间位置， //从头节点开始遍历，大于中间位置从尾节点开始遍历 Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } //返回第一次出现指定元素的位置 public int indexOf(Object o) { int index = 0; if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; } //返回最后一次出现元素的位置 public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (Node<E> x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; } //弹出第一个元素的值 public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; } //获取第一个元素 public E element() { return getFirst(); } //弹出第一元素，并删除 public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } //删除第一个元素 public E remove() { return removeFirst(); } //添加到尾部 public boolean offer(E e) { return add(e); } //添加到头部 public boolean offerFirst(E e) { addFirst(e); return true; } //插入到最后一个元素 public boolean offerLast(E e) { addLast(e); return true; } //队列操作 //尝试弹出第一个元素，但是不删除元素 public E peekFirst() { final Node<E> f = first; return (f == null) ? null : f.item; } //队列操作 //尝试弹出最后一个元素，不删除 public E peekLast() { final Node<E> l = last; return (l == null) ? null : l.item; } //弹出第一个元素，并删除 public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } //弹出最后一个元素，并删除 public E pollLast() { final Node<E> l = last; return (l == null) ? null : unlinkLast(l); } //如队列，添加到头部 public void push(E e) { addFirst(e); } //出队列删除第一个节点 public E pop() { return removeFirst(); } //删除指定元素第一次出现的位置 public boolean removeFirstOccurrence(Object o) { return remove(o); } //删除指定元素最后一次出现的位置 public boolean removeLastOccurrence(Object o) { if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = last; x != null; x = x.prev) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } //遍历方法 public ListIterator<E> listIterator(int index) { checkPositionIndex(index); return new ListItr(index); } //内部类，实现ListIterator接口 private class ListItr implements ListIterator<E> { private Node<E> lastReturned = null; private Node<E> next; private int nextIndex; private int expectedModCount = modCount; ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; } public boolean hasNext() { return nextIndex < size; } public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } public boolean hasPrevious() { return nextIndex > 0; } public E previous() { checkForComodification(); if (!hasPrevious()) throw new NoSuchElementException(); lastReturned = next = (next == null) ? last : next.prev; nextIndex--; return lastReturned.item; } public int nextIndex() { return nextIndex; } public int previousIndex() { return nextIndex - 1; } public void remove() { checkForComodification(); if (lastReturned == null) throw new IllegalStateException(); Node<E> lastNext = lastReturned.next; unlink(lastReturned); if (next == lastReturned) next = lastNext; else nextIndex--; lastReturned = null; expectedModCount++; } public void set(E e) { if (lastReturned == null) throw new IllegalStateException(); checkForComodification(); lastReturned.item = e; } public void add(E e) { checkForComodification(); lastReturned = null; if (next == null) linkLast(e); else linkBefore(e, next); nextIndex++; expectedModCount++; } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } //静态内部类，创建节点 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; } } /** * @since 1.6 */ public Iterator<E> descendingIterator() { return new DescendingIterator(); } /** * Adapter to provide descending iterators via ListItr.previous */ private class DescendingIterator implements Iterator<E> { private final ListItr itr = new ListItr(size()); public boolean hasNext() { return itr.hasPrevious(); } public E next() { return itr.previous(); } public void remove() { itr.remove(); } } @SuppressWarnings("unchecked") private LinkedList<E> superClone() { try { return (LinkedList<E>) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(); } } /** * Returns a shallow copy of this {@code LinkedList}. (The elements * themselves are not cloned.) * * @return a shallow copy of this {@code LinkedList} instance */ public Object clone() { LinkedList<E> clone = superClone(); // Put clone into "virgin" state clone.first = clone.last = null; clone.size = 0; clone.modCount = 0; // Initialize clone with our elements for (Node<E> x = first; x != null; x = x.next) clone.add(x.item); return clone; } public Object[] toArray() { Object[] result = new Object[size]; int i = 0; for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; return result; } @SuppressWarnings("unchecked") public <T> T[] toArray(T[] a) { if (a.length < size) a = (T[])java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), size); int i = 0; Object[] result = a; for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; if (a.length > size) a[size] = null; return a; } private static final long serialVersionUID = 876323262645176354L; //将对象写入到输出流中 private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out any hidden serialization magic s.defaultWriteObject(); // Write out size s.writeInt(size); // Write out all elements in the proper order. for (Node<E> x = first; x != null; x = x.next) s.writeObject(x.item); } //从输入流中将对象读出 @SuppressWarnings("unchecked") private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in any hidden serialization magic s.defaultReadObject(); // Read in size int size = s.readInt(); // Read in all elements in the proper order. for (int i = 0; i < size; i++) linkLast((E)s.readObject()); } }
Set接口
- Set接口时Collection接口的另外一个常用子接口，Set接口描述的是一种比较简单的集合。集合中的对象并不按特定的方式排序，并且不能保存重复的对象，也就是说Set接口可以存储一组唯一、无序的对象
- Set接口常用的实现类有Hash Set
HashSet的定义：Hash Set类实现了Set接口，由一个实际上是HashMap实例的散列表支持。不能保证集合的迭代次序，这意味着该类不能保证元素随时间的不变顺序。
这个类允许null元素。
该类还未基本操作（如添加，删除，包含和大小）提供了恒定的时间性能
-
HashSet集合特点如下：
集合内的元素是无需排列的。
HashSet类是非线程安全的。
允许集合元素值为null。
-
HashSet类的常用方法：
boolean add(Object o)如果Set中尚未包含指定元素o，则添加指定元素o
void clear()从Set中移除所有元素
int size()返回Set中的元素的数量（Set的容量）
boolean isEmpty()如果Set不包含任何元素，则返回true
boolean contains(Object o)如果Set包含指定元素o，则返回true
boolean remove(Object o)如果指定元素o存在于Set中，则将其移除
Iterator接口
概述：Iterator接口表示对集合进行迭代的迭代器。Iterator接口为集合而生，专门实现集合的遍历。迭代器是一种设计模式，它是一个对象，它可以遍历并选择序列中的对象，而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象，以为创建它的代价小
-
Java中的Iterator功能比较简单，并且只能单向移动：
使用方法Iterator（）要求容器返回一个Iterator。第一次调用Iterator的next()方法时，它返回序列的第一个元素。注意：iterator()方法时java.lang.iterable接口，被Collection继承
使用next（）获得序列中的下一个元素
使用hasNext()检查序列中是否还有元素
使用remove()将迭代器新返回的元素删除
链表
-
链表是由一系列非连续的节点组成的存储结构，简单分以下类的话，链表又分为单项链表和双向链表，而单/双向量表又可以分为循环链表和非循环链表
-
单向链表：
-
单向链表就是通过每个结点的指针指向下一个结点从而链接起来的结构，最后一个结点的next指向null。
193331_JljJ_2927759.png每个元素包含两个域，值域和指针域，我们把这样的元素称之为节点。每个节点的指针域有一个指针，指向下一个节点，而最后一个节点则指向一个空值
img
-
-
-
单向循环链表：
单项循环链表和单向列表不同的是，最后一个节点的next不是指向null,而是指向head节点，形成一个“环”
193412_xGR9_2927759.png
-
双向链表：
从名字就可以看出，双向链表包含两个指针，pre指向前一个节点，next指向后一个节点，但是第一个节点head的pre指向null，最后一个节点的tail指向null
193440_9dt2_2927759.png
-
双向循环链表：
双向循环链表和双向链表的不同在于，第一个节点的pre指向最后一个节点，最后一个节点的next指向第一个节点，也形成一个“环”。而LinkedList就是基于双向循环链表设计的
193526_9m6M_2927759.png
