[数据结构与算法]javaSE 集合

javaSE集合

使程序能存储和操作元素不固定的一组数据,所有的Java集合类都位于java.util包中

Collection

• 如果要在集合里存放基本类型,一定要将其"装箱"成对应的

collection 是集合的父类,所以collection中的方法是集合中每个子类都有的"基本类型包装类"

继承体系
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FGPCaeNg-1626357043283)(2021-07-15-11-56-31.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rk7oUauO-1626357043287)(2021-07-15-11-59-29.png)]

• 并不是所有子接口或实现类都是最常用的。
  常用的几个子接口和实现类：
  Collection ——> List ——> ArrayList类
  Collection ——> List ——> LinkedList类
  Collection ——> Set ——> HashSet类
  Collection ——> Set ——> SortedSet接口 ——> TreeSet类
  Map ——> HashMap类
  Map ——> SortedMap ——> TreeMap类

collection常用方法
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BfdljvJd-1626357043289)(2021-07-15-12-04-27.png)]
使用

import java.util.ArrayList;
import java.util.Collection;
public class Collection_01 {
public static void main (String[]args){
	//创建
	Collection c1 = new ArrayList();
	System.out.println(c1.isEmpty());//判断是否为空
	//基本类型先进行自动装箱,然后再向上转型
	c1.add(1);//添加
	System.out.println(c1.isEmpty());
	System.out.println(c1.size());//多少数据
	c1.add("hbuyv");
	System.out.println(c1.size());
	//转换为数组进行遍历
	Object[] objects = c1.toArray();
	for(Object object:objects){
		System.out.print(object);
	}
	//删除
	c1.remove("hbuyv");
	System.out.println(c1.size());
	//清空集合
	c1.clear();
	System.out.println(c1.isEmpty());
}
}

• boolean contains(Object o):判断是否包含某个元素
  boolean contains(Object o):删除指定元素
  这两个方法,底层都会调用equals方法进行比较
  比如c.contains(“abc”);会用abc调用equals方法和集合中的所有元素比较
  如果要存储自定义类型,比如User等,想使用contains remove就需要自己在自定义类中对equals 覆写

import java.util.ArrayList;
import java.util.Collection;
public class Collection_03 {
public static void main(String[]args){
	Collection c = new ArrayList();
	c.add(1);
	c.add(new Integer(1));
	System.out.println(c.size());
	Integer i1 = new Integer(1);
    System.out.println(c.contains(i1));//判断是否有1
    Manager m1=new Manager(1,"张三");
    c.add(m1);
    Manager m2=new Manager(1,"张三");
    System.out.println(c.contains(m2));//值一样能不能找到要看有没有覆写equals方法让它对比值
}
}
class Manager{
	public boolean equals(Object obj){
		if (this == obj){
			return true;
		}
		if(obj instanceof Manager){
			Manager m = (Manager)obj;
			if(no==m.no&&name.equals(m.name)){
				return true;
			}
		}
		return false;
	}
	private int no;
	private String name;
	public Manager(int no,String name){
		super();
		this.no=no;
		this.name=name;
	}
	public int getNo() {
		return no;
	}
	public void setNo(int no) {
		this.no = no;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}	
}

Iterator(迭代器)
Collection接口的iterator()和toArray()方法都用于获得集合中的所有元素,前者返回一个Iterator对象,后者返回一个包含集合中的所有元素的数组.

• for与iterator对比
  iterator的好处在于可以使用相同的方式去遍历集合中的元素,而不需要考虑 集合类内部怎么实现的.使用iterator来遍历集合中的元素,如果不再使用List 转而使用Set,则遍历元素的代码不用做任何改变,而for因为List有序Set无序
  它必须改变for循环需要下标,for each和迭代器相近

• 迭代器:可以屏蔽底层数据存储的差异性

• 方法	描述
  Boolean hasNext()	如果被迭代的集合有下一个元素,返回true
  Object next()	返回集合里的下一个元素
  void remove()	删除集合里上一次next方法返回的元素

• 使用

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
public class Collection_04 {
public static void main(String[]args){
	Collection c = new ArrayList();
	c.add("we");
	c.add("sd");
	c.add("567");
	c.add("f76");
	c.add("ee");
	System.out.println(c.isEmpty());
	//生成迭代器
	Iterator it = c.iterator();
	//迭代器一旦创建,集合中元素不能删除和添加,否则就需要重新生成迭代器
	while (it.hasNext()){
		Object object = it.next();
		System.out.println(object);
		//使用迭代器过程中,如需删除,必须用迭代器的remove方法
		//it.remove();
	}
	//System.out.println(c.isEmpty());
	//迭代器遍历完之后,想再次遍历只能重新生成
	c.add("aa");
	it = c.iterator();
	while(it.hasNext()){
		Object object = it.next();
		System.out.println(object);		
	}
}
}

List

• 有序可重复,存入顺序和取出顺序一致
  ArrayList:底层是数组,查询和更改效率高增加和删除效率低,默认容量是10,扩大容量是1.5倍
  LinkedList:底层是双向链表,查询和更改效率低增加和删除效率高
  Vector:已经过时,底层是数组,ArrayList是其增强版Vector默认容量是10,扩大容量是2倍,线程安全,效率极低
  ArrayList

import java.lang.reflect.Field;
import java.util.ArrayList;
public class Collection_06 {
public static  void main(String[]args)throws Exception{
	//创建ArrayList对象的时候,长度为0,参考ArrayList的无参构造private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
	ArrayList arrayList  =  new ArrayList();
	//第一次添加元素时候,长度为10
	//扩容是原来的1.5倍:长度+长度>>1,>>1移位就是除以二
	arrayList.add(1);
    //访问不了底层的数组,因为权限不够
	//System.out.println(arrayList.elementData);
    //用反射获取
	//获取ArrayList运行时类
	Class c = arrayList.getClass();
	//获取elementData这个变量
	Field f = c.getDeclaredField("elementData");
	//打破封装性
	f.setAccessible(true);
	//获取这个变量的值,得到数组(这个变量是数组)
	Object[]arr = (Object[])f.get(arrayList);
	System.out.println(arr.length);
	//因为传的是引用获取的时候ArrayList中封装的对象
	//所以这里更改ArrayList数组内容也变
	arr[0]=2;
	//长度默认是10可以通过往数组中添加数据更改集合中内容
	arr[1]=33;
	//因为ArrayList中使用size保存已有元素个数,所以我们添加内容后如果不更改size的值就没用了
	Field size = c.getDeclaredField("size");
	size.setAccessible(true);
	//设置ArrayList 中size变量的值,因为数组是引用类型,所以默认值是null
	//因此数组中非元素内容都是null
	size.set(arrayList, 10);
	System.out.println(arrayList);
	// [2, 33, null, null, null, null, null, null, null, null]
}
}

• ArrayList基本使用
  ArrayList的底层是Object[]数组,也意味着只能保存引用类型,但是基本类型会自动装箱成包装类类型,所以导致Object[]数组啥都能放

import java.util.ArrayList;
import java.util.Iterator;
public class Collection_05 {
public static void main(String[]args){
	ArrayList list = new ArrayList();
	//add(E e);将元素添加到列表尾部
	list.add(32);
	//add(int index,E e);元素添加到指定位置
	list.add(1, "jj");
	//AeeayList覆写了toString方法,所以打印结果不是地址而是值
	System.out.println(list);
	//set(int index , E element);替换指定位置元素
	list.set(1, 22);
	System.out.println(list);
	//get(int index);根据索引获得元素
	System.out.println(list.get(0));
	//remove(int index);根据索引删除
	System.out.println(list.remove( 1)+"删除");
	System.out.println(list);
	//remove(Object obj)根据指定元素删除
	//如果想根据元素值删除32,不能直接写,直接写他就是个下标应该把他封装在Integer里
	list.remove(new Integer(32));
	System.out.println(list);
	list.add(11);
	list.add(22);
	list.add(33);
	list.add(44);
	list.add(55);
	//迭代器
	Iterator it = list.iterator();
	while(it.hasNext()){
		System.out.println(it.next());
	}
	System.out.println("============================");
	//forEach
	for(Object object : list){
		System.out.println(object);
	}
	System.out.println("============================");
	//for循环
	for(int i=0;i<list.size();i++ ){
		System.out.println(list.get(i));
	}
}
}

LinkedList
链表的节点 由三个部分组成:1.添加的元素2.下一个节点的引用3.上一个节点的引用
链表的数据结构,在内存中存储也不是连续的,所以没有固定的下标,因此查询效率低,添加和删除便更加容易

• 基本使用

import java.util.LinkedList;
public class Collecption_07 {
public static void main(String[]args){
	LinkedList linkedList = new LinkedList();
	//尾部添加成功返回true
	linkedList.add(1);
	//无返回
	linkedList.addLast(2);
	linkedList.offerLast(3);
	//头部添加成功返回true
	linkedList.addFirst(4);
	//不返回
	linkedList.push(5);
	linkedList.offerFirst(6);
	System.out.println(linkedList);
	//本质调用的都是linkedLast和linkedFirst,所以他们区别不大,主要是解决名名习惯
	//获取最后一个
	System.out.println(linkedList.getLast());
	//获取第一一个
	System.out.println(linkedList.getFirst());
	//根据循环次数获取模拟下标获取
	System.out.println(linkedList.get(3));
	//改,设置对应"下标"数据
	linkedList.set(2, 32);
	System.out.println(linkedList);
	//根据索引删除
	linkedList.remove(0);
	System.out.println(linkedList);
	//删除指定元素
	linkedList.remove(new Integer(2));
	System.out.println(linkedList);
	//获取第一个元素并删除
	linkedList.poll();
	System.out.println(linkedList);
	//获取第一个元素并删除会报错
	linkedList.pop();
	System.out.println(linkedList);	
}
}

• 删除操作
  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UqbeyekZ-1626357043293)(2021-07-15-20-51-55.png)]
• 底层实现
• 添加
  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SMG8cb4L-1626357043295)(2021-07-15-20-53-23.png)]
• 删除
  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TggKVhIs-1626357043297)(2021-07-15-20-54-50.png)]

测试ArrayList和LinkedList效率

ArrayList初始化完成:100000条数据用时7
LinkedList初始化完成:100000条数据用时9
ArrayList查询:47421对应的值为47421
ArrayList查询完成:47421条数据用时0
LinkedList查询:47421对应的值为47421
LinkedList查询完成:47421条数据用时1
ArrayList删除完成:100000条数据用时375
LinkedList删除完成:100000条数据用时2248

数据分析 : 查询一定是数组快,但是结果有时候显示添加和删除也是数组快因为数组的自动扩容机制,1.5倍增长,导致添加数据,才需要创建一个数组对象进行扩容,而删除元素后,容量并没有更改变小而链表 每次添加都需要创建新的节点对象,而删除也是需要重新指向节点引用
总结 :
插入位置的选取对ArrayList影响非常大,一直向后面添加,ArrayList会比LinkedList快,因为ArrayList有自动扩容所以对于LinkedList是添加,但是对ArrayList来说,只是向已有空间中赋值,也就等于是更改操作,而数组查询和更改效率是比较高的都说数组比链表添加删除慢,是因为链表进行添加删除的时候,只需要引用指向即可,而数组需要数据移动位置所以如果向前边添加数据,则链表快很多

• 代码

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Random;

public class TestArr_Link {
private static ArrayList arrayList;
private static LinkedList linkedList;
private static int size = 100000;
public static void main(String[]args)throws NoSuchFieldException,SecurityException,IllegalArgumentException,IllegalAccessException{
	initArrayList();
	initLinkedList();
	Random random = new Random();
	int index = random.nextInt(size);
	getArrayList(index);
	getLinkedList(index);
	removeArrayList();
	removeLinkedList();
	
}//初始化ArrayList
public static void initArrayList(){
	long startTime = System.currentTimeMillis();
	arrayList = new ArrayList();
	for(int i = 0;i<size;i++){
		arrayList.add(i);
	}
	long endTime = System.currentTimeMillis();
	System.out.println("ArrayList初始化完成:"+size+"条数据用时"+(endTime-startTime));
}//初始化LinkedList
public static void initLinkedList(){
	long startTime = System.currentTimeMillis();
	linkedList = new LinkedList();
	for(int i = 0;i<size;i++){
		linkedList.add(i);
	}
	long endTime = System.currentTimeMillis();
	System.out.println("LinkedList初始化完成:"+size+"条数据用时"+(endTime-startTime));

}//删除ArrayList
public static void removeArrayList(){
	long startTime = System.currentTimeMillis();
	
	for(int i = 0;i<arrayList.size();i++){
		arrayList.remove(i);
	}
	long endTime = System.currentTimeMillis();
	System.out.println("ArrayList删除完成:"+size+"条数据用时"+(endTime-startTime));
}
//删除LinkedList
public static void removeLinkedList(){
	long startTime = System.currentTimeMillis();
	
	for(int i = 0;i<linkedList.size();i++){
		linkedList.remove(i);
	}
	long endTime = System.currentTimeMillis();
	System.out.println("LinkedList删除完成:"+size+"条数据用时"+(endTime-startTime));
}
public static void getArrayList(int index){
	long startTime = System.currentTimeMillis();
	System.out.println("ArrayList查询:"+index+"对应的值为"+arrayList.get(index));
	long endTime = System.currentTimeMillis();
	System.out.println("ArrayList查询完成:"+index+"条数据用时"+(endTime-startTime));
}
public static void getLinkedList(int index){
	long startTime = System.currentTimeMillis();
	System.out.println("LinkedList查询:"+index+"对应的值为"+linkedList.get(index));
	long endTime = System.currentTimeMillis();
	System.out.println("LinkedList查询完成:"+index+"条数据用时"+(endTime-startTime));
}
}