集合是一个长度可变且可以存储多个数据（对象）的容器，顶级接口Collection<E>
<E>-----泛型：用于指定集合元素的数据类型，只能是引用类型。
int[] arr;arr的数据类型是数组类型，arr的元素是int类型。
Collection<String> c; c的数据类型是引用类型，c中的元素即对象是String类型。
集合想存储基本类型的数据 1，2，4 Integer in=1； in可以存储在集合中。
子接口List、Set、Quene
List（列表）保证存入数据有序 ，可以根据下标操作集合元素。
主要实现类：ArrayList，LinkedList，Stack，Vector。
ArrayList（有序表）底层是由数组来实现的，默认数组的初始长度为10，根据底层右移运算进行了扩容，每次在原来的基础上扩容一半10 15 22 33，基于右移运算。查询效率较高、增删元素效率较低。下面是通过数组还原ArrayList：
package cn.zyj; import java.util.Arrays; //用数组实现ArrayList public class sxArrayList { public static void main(String[] args) { ListArray la = new ListArray(); la.add("avc"); la.add("ca"); la.remove("avc"); System.out.println(la.toString()); } } class ListArray{ //实现ArrayList String[] date; //表示元素个数以及数组下标 int size=0; //默认初始容量 public ListArray(){ date=new String[10]; } //指定初始容量 public ListArray(int Length){ date = new String[Length]; } //数组扩容 public void grow(){ //判断数据原长度是否是0 if (date.length <=1) { date= Arrays.copyOf(date,date.length+1); }else { //在原来的基础上加上一半 date = Arrays.copyOf(date, date.length + (date.length >> 1)); } } //下标是否越界问题 public void out(int index){ //如果下标越界就抛出异常 if (index<0||index>=size){ throw new IllegalArgumentException("Index:"+index); } } //添加元素 public void add(String s){ //判断是否需要扩容 if(size>=date.length){ grow(); } //往数组添加元素 date[size++]=s; } public void add(int index,String s) { //判断下标是否越界 if (index<0||index>size){ //下标和元素个数比较 throw new IllegalArgumentException("Index:"+index); } //判断是否需要扩容 if (size>=date.length){ grow(); } //依次把index后面的数组元素往后赋值 // for (int i = size-1; i >=index; i--) { // //把前面的元素赋值给后面的元素 // date[i+1]=date[i]; // } System.arraycopy(date,index,date,index+1,size-index); //插入元素 date[index]=s; // size++; } //删除 //根据下标删除（元素个数和长度相等，删除最后一个元素） public void remove(int index){ //判断下标是否越界 out(index); //依次把index到后面的元素往前赋值 for (int i = index; i < size-1; i++) { date[i]=date[i+1]; } System.arraycopy(date,index+1,date,index,size-(index+1)); size--; } //根据元素进行删除 public void remove(String str){ //返回结果值 int index=indexOf(str); if (index!=-1){ remove(index); } } //indexOf返回元素第一次出现的下标 public int indexOf(String str){ //遍历数组依次比较 for (int i = 0; i < size; i++) { //只比元素 //判断是否相等 if (date[i]==str|| date[i]!=null&&date[i].equals(str)){//返回下标 return i; } } //没找到元素 return -1; } //清空集合 public void clear(){ size=0; //没有可遍历的元素 } public boolean contains(String str){ return indexOf(str)!=-1; } public String get(int index){ out(index); //返回指定的元素 return date[index]; } //判断集合是否为空 public boolean isEmpty(){ return size==0; } public void set(int index,String str){ //越界问题 out(index); //替换 date[index]=str; } //返回元素个数 public int size(){ return size; } //截取子链表 public ListArray subList(int fromIndex, int toIndex){ //越界 out(fromIndex); out(toIndex); //判断下标大小是否正确 if (toIndex<fromIndex){ throw new IllegalArgumentException("FromIndex:"+fromIndex+"ToIndex:"+toIndex); } //新建列表 //指定新链表长度 int count = toIndex-fromIndex; ListArray list = new ListArray(count); //数组复制 System.arraycopy(date,fromIndex,list.date,0,count); //赋值size---把赋值的元素个数赋值给新列表的size list.size=count; return list; } //重写toString方法，输出对象的时候输出的是元素 public String toString(){ StringBuilder sb = new StringBuilder("["); for (int i = 0; i < size; i++) { if (i==size-1){ sb.append(date[i]);} else sb.append(date[i]).append(", "); } //转出字符串 String str=sb.toString(); return str+"]"; } }LinkedList(链表)
底层是由节点（静态内部类）来进行存储元素的。底层内存不连续，不需要扩容，增删元素效率较高，查询元素效率较低
练习：实现LinkedList
如果这个场景需要用到ArrayList或者LinkedList，增删和查询的操作概率相当，用哪个？
优先使用LinkedList，因为是不连续内存，没有空间在浪费，提高内存利用率，如下所示链表在内存中的图
实现LinkedList代码如下：
import java.util.LinkedList; public class LinkedListText { public static void main(String[] args) { ListLinked lk = new ListLinked(); lk.add("avc"); lk.add("avc1"); lk.add("avc2"); lk.add("avc3"); lk.add("avc4"); lk.add("avc5"); lk.add("avc6"); System.out.println(lk.toString()); } } //实现LinkedList class ListLinked{ //元素个数 节点数 int size=0; //头节点--表示第一个节点 Node first; //尾节点 Node last; //节点----内部类 class Node{ //表示存储的元素 String item; //上一个节点 Node prev; //下一个节点 Node next; //有参构造,创建节点 public Node(String item,Node prev,Node next){ //元素给节点赋值 this.item=item; this.prev=prev; this.next=next; } } //添加 public void add(String str){ //新节点 Node node = new Node(str,null,null); //判断添加元素的位置 if (size==0){//表明添加第一个节点} //头节点指向新节点 this.first=node; //尾节点指向新节点 this.last=node; }else{//尾部添加 //原尾节点的下一个指向新节点 this.last.next=node; //新节点的上一个指向原尾节点 node.prev=this.last; } //尾节点指向新节点 this.last=node; //节点个数加1 size++; } //插入 public void add(int index,String str){ if(index<0||index>size){ throw new IllegalArgumentException("Index:"+index); } //创建新节点 Node node = new Node(str,null,null); //在尾部进行添加节点 if (index==size){ add(str); //结束方法，保证size不会添加两次 return; } //判断插入头结点但是已经有了头结点 //size不为0 if (index==0){ //原头结点的上一个指向新节点 this.first.prev=node; //新节点的下一个指向原头检点 node.next=this.first; //头节点指向新节点 this.first=node; }else{ //在中间插入 //获取指定下标的节点 Node no = getNode(index); //no节点的上一个节点的下一个指向新节点 no.prev.next=node; //新节点的上一个指向no节点的上一个节点 node.prev=no.prev; //no节点的上一个指向新节点 no.prev=node; //no节点的一下个指向no node.next=no; } size++; } //判断是否越界 public void out(int index){ if(index<0||index>=size){ throw new IllegalArgumentException("Index:"+index); } } //根据下标找节点 public Node getNode(int index){ Node no = this.first; for (int i = 0; i < index; i++) { no = no.next; } return no; } //删除根据下标进行删除 public void remove(int index){ out(index); //判断删除节点的位置 //判断是否删除的是头结点 if(index==0){ //原头节点的下一个节点的上一个为null this.first.next.prev=null; //头节点指向原头结点的一下一个节点 this.first=this.first.next; }else if (index==size-1){ //原尾节点上一个节点的next为null this.last.prev.next=null; //尾节点指向原尾节点上一个节点 this.last=this.last.prev; }else {//删除中间的节点 Node no =getNode(index); //no节点的上一个节点的next 指向no 的next no.prev.next = no.next; //no节点的下一个节点的上一个指向no的上一个节点 no.next.prev = no.prev; } size--; } //获取元素第一次出现的下标 public int indexOf(String str){ //遍历节点，找出满足要求的item Node no = this.first; for (int i = 0; i < size; i++) { if (str==no.item|| str!=null && str.equals(no.item)){ //返回下标值 return i; } no=no.next; } //没有找到return -1 return -1; } //根据指定元素删除 public void remove(String str){ int index = indexOf(str); //判断是否为-1 if(index!=-1){ remove(index); } } //重写toString public String toString(){ StringBuilder sb = new StringBuilder("["); Node no = this.first; for (int i = 0; i < size; i++) { sb.append(no.item).append(", "); no=no.next; } //转换字符串 String ss= sb.toString(); //判断元素是否为空 if(size>0){ ss=ss.substring(0,ss.length()-2); } return ss+="]"; } }
底层基于数组，扩容基于三目运算符，默认是增加一倍，但是可以指定增量，如果增量不为0就可以按照增量进行素组扩容。
Vetor是Java的第一个集合类，是一个线程安全的集合。通过调用elements方法返回古老的迭代器
Vector()
构造一个空向量，使其内部数据数组的大小 10及其标准容量增量为零。
Vector(Collection<? extends E> c)
构造一个包含指定集合元素的向量，它们在集合的迭代器返回的顺序中返回。
Vector(int initialCapacity)
用指定的初始容量构造一个空向量，并以其容量增量等于零。
Vector(int initialCapacity, int capacityIncrement)
用指定的初始容量和容量增量构造一个空向量。
初始值就是Vector底层数组的初始长度，可以定义增量
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);//这个就是不指定就是翻倍，指定capacityIncrement就是按指定值增长 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }遍历Vector
public static void main(String[] args) { //创建集合对象 Vector<String> v=new Vector<String>(); //添加元素 v.add("1"); v.add("2"); v.add("3"); v.add("4"); //调用方法返回古老的迭代器 Enumeration<String> e=v.elements(); //迭代遍历 while(e.hasMoreElements())//判断是否还有元素 { //获取元素 String s=e.nextElement(); System.out.println(s); } } }遵循先进后出（FILO） ，是Vector的子类。
栈顶元素：最后一个放入元素。
栈底元素：第一个放入元素。
压栈/入栈：存入元素。
弹栈/出栈：获取元素。
booleanempty()
测试此堆栈是否为空。
Epeek()查看此堆栈顶部的对象，而不将它从堆栈中删除。
Epop()在这个堆栈的顶部删除对象，并返回该对象的值作为该函数的值。
Epush(E item)将一个项目推到这个堆栈的顶部。
intsearch(Object o)返回元素一个对象在堆栈。
public class StackDemo { public static void main(String[] args) { Stack<String> s = new Stack<>(); //入栈 s.push("1"); s.push("2"); s.push("3"); s.push("4"); s.push("5"); //判断栈是否为空 System.out.println(s.isEmpty()); //获取栈顶元素不删除 System.out.println(s.peek()); //获取栈顶元素并删除栈顶元素 System.out.println(s.pop()); //查找元素第一次出现的下标值（从栈顶往下查找，从1开始，如果没有查找到元素就返回-1） System.out.println(s.search("2")); //保证存入数据有序 System.out.println(s); } }
