[数据结构与算法]day_18 集合、list、链表、比较器

1. Collection

1.1概述

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

问:之前我们需要把多个元素放到一起的时候,使用的是数组.那么为何还要提供java集合工具呢?

我们通过对比数组和hjava集合工具来解释java集合工具的必要性:

1.2继承体系

?由上图我们可以看出java集合类由清晰的继承关系,有很多子接口和实现类.但是,并不是所有子接口或实现类都是最常用的.

下面我们列举处最常用的集合子接口和实现类:

1.3常用方法

1.4使用方式

		// 创建集合对象
		Collection c1 = new ArrayList();
		// 判断是否为空(个数是否为0)
		System.out.println(c1.isEmpty());
		// 集合中是不能保存基本类型的,需要转换为对应包装类才可以
		// 这里会进行自动装箱为Integer类型,然后发生多态转型为Object类型 进行存储
		c1.add(123);
		c1.add(new Integer(1));
		c1.add(new Text01());
		// 个数
		System.out.println(c1.size());
		System.out.println(c1.isEmpty());
		
		// 删除,会调用要删除元素的equals方法,但是Integer覆写了,所以可以把1删掉
		c1.remove(1);
		
		A a = new A("张三");
		A a1 = new A("张三");
		c1.add(a);
		// 所以使用集合保存自定义类型的时候,要注意,是否要覆写equals方法,定义怎么算相等
		c1.remove(a1);
		// 把集合转换为数组
		Object[] arr = c1.toArray();
		for (Object object : arr) {
			System.out.println(object);
		}
		// 清空集合
		c1.clear();
		System.out.println(c1.size());
	

1.5注意Contains和remove

Contains(数据):判断集合中国是否包含某个元素

Remove(数据):删除指定元素

两个方法底层都会自动调用该对象的equals方法

因为不管是判断是否包含还是删除,都要先找到这个数据,而找到只能比较但是集合中国保存的都是引用类型,所以比较只能使用equalsfangfa

所以如果存储的是自定义类型,就要考虑equals方法的覆写问题

2.Iterator

2.1概述

/**
 * 在面向对象编程里，迭代器模式是一种设计模式，是一种最简单也最常见的设计模式。
 * 它可以让用户透过特定的接口巡访容器中的每一个元素而不用了解底层的实现。
 * 
 * 获取该集合的迭代器对象 
 * Iterator it = 集合对象.iterator();  
 * 		三个方法 : 
 * 				1 boolean hasNext() : 判断下面还有没有元素,如果有就返回true,没有就返回false
 * 				2 E next() : 获取下一个元素,并指向下一个元素
 * 				3 remove() : 删除当前指向的元素
 * 			三个方法的使用步骤 , 就是 1,2,3 按照这个顺序调用 
 * 
 * 注意 : 迭代器一旦创建,集合中就不能添加和删除元素(长度不能更改了)
 * 			如果添加或者删除了元素,那么迭代器必须重新生成
 * 增强for循环 就是为了让用iterator循环访问的方式简单,写起来更方便,当然功能不太全,比如删除,还是要用iterator来删除
 * @author 学到头秃的张张张
 *@Date 2021年10月21日下午9:50:49
 */

[for与iterator对比]

·Iterator的好处在于可以使用相同方式去遍历集合中元素,而不用考虑集合类的内部实现

·使用Iterator来遍历集合中元素,如果不再使用List转而使用Set来组织数据,则遍历元素的代码不用做任何修改

·使用for来遍历,那所有遍历此集合的算法都得做相应调整,因为List有序,Set无序,结构不同,他们的访问算法也不一样

·for循环需要下标

2.2常用方法

2.3使用方式

		// Collection c1 = new ArrayList();
		// Collection c1 = new HashSet();
		Collection c1 = new LinkedList();
		c1.add(1);
		c1.add("abc");
		// 判断是否包含
		System.out.println(c1.contains(1));
		// 1 创建迭代器
		Iterator it = c1.iterator();
		// 遍历 判断下面是否有元素
		while (it.hasNext()) {
			// 获取并指向下一个元素
			Object obj = it.next();
			System.out.println(obj);
		}

		// 使用完之后,想再次使用,需要重新创建
		it = c1.iterator();
		// 迭代器创建之后,不能添加和删除 , 必须重新生成迭代器
		c1.add(2);
		c1.add(3);
		c1.remove(1);
		it = c1.iterator();
		while (it.hasNext()) {
			// 获取并指向下一个元素
			Object obj = it.next();
			System.out.println(obj);
			// 使用迭代器的时候,不能更改集合个数,所以删除数据的时候不能使用集合的删除,应该使用迭代器的删除
			// c1.remove(obj);
			it.remove();
		}
		System.out.println(c1.size());
	

3.List

3.1概述

/**
 * List特点 : 有序 可重复 
 * 			有序 : 添加顺序和取出顺序是一致的
 * 			可重复 : 就是可以有重复的数据
 * 
 * ArrayList : 底层是个Object数组 , 随机查询和更改效率高, 随机添加和删除 效率低
 * 
 * LinkedList : 底层是一个双向链表,随机查询更改效率低,随机添加和删除效率高
 * 
 * @author 学到头秃的张张张
 *@Date 2021年10月21日下午10:00:59
 */

3.2ArrayList

/**
 * ArrayList底层是数组,下标从0开始
 * 		默认初始化容量为10,扩大容量为原始容量的1.5倍
 * 		并且默认容量是第一次添加数据的时候设置的
 * 	也就是说 我们 new ArrayList() 的时候,数组长度是为0的
 * 		1.5倍 : 长度 + 长度>>1
 *
 * @author 学到头秃的张张张
 *@Date 2021年10月21日下午10:07:42
 */

?

3.2.1基本使用

		// 创建对象
		// Vector 已经过时了,ArrayList是Vector的升级版,Vector是线程安全,而ArrayList是非线程安全的
		List list = new ArrayList();
		list.add(100);
		list.add(123);
		// [100, 123]  覆写了toString方法
		System.out.println(list);
	

3.2.2使用方法

		List list = new ArrayList();
		list.add(1);
		list.add(2);
		list.add(3);
		// add(E e ) : 尾部添加
		// add(int index , E e ) : 添加到指定位置
		// set(int index, E e ) : 更改指定位置上的元素值
		// remove(Object object) : 根据元素内容删除
		// remove(int index) : 根据索引删除
		// get(int index) : 获取指定位置的数据
		list.add(1, 4);
		list.set(3, 33);
		System.out.println(list.get(2));
		// 这是根据索引删除
		list.remove(1);
		// 删除元素值为1
		list.remove(new Integer(1));
		System.out.println(list);

3.2.3遍历

		// 传统for遍历
		for (int i = 0; i < list.size(); i++) {
			System.out.println(list.get(i));
		}
		// foreach遍历
		for (Object object : list) {
			System.out.println(object);
		}
		// 迭代器遍历
		Iterator it = list.iterator();
		while (it.hasNext()) {
			System.out.println(it.next());

3.3LinkedList

3.3.1基本使用和方法

总结:和ArrayList操作一模一样

		LinkedList list = new LinkedList();
		// add(E e ) : 尾部添加
		// add(int index , E e ) : 添加到指定位置
		// set(int index, E e ) : 更改指定位置上的元素值
		// remove(Object object) : 根据元素内容删除
		// remove(int index) : 根据索引删除
		// get(int index) : 获取指定位置的数据
		// 首部添加
		list.addFirst(1);
		// 首部添加
		list.push(11);
		// 首部添加 成功返回true
		list.offerFirst(111);
		// 尾部添加
		list.addLast(2);
		// 尾部添加 成功返回true
		list.offerLast(22);
		// 尾部添加 成功返回true
		list.offer(222);
		// 上面这几个方法 没啥区别,本质就是 linkLast 和 linkFirst
		
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(0, 4);
		list.set(3, 33);
		System.out.println(list.get(2));
		// 这是根据索引删除
		list.remove(1);
		// 删除元素值为1
		list.remove(new Integer(1));
		System.out.println(list);
		
		// 传统for遍历
		for (int i = 0; i < list.size(); i++) {
			System.out.println(list.get(i));
		}
		// foreach遍历
		for (Object object : list) {
			System.out.println(object);
		}
		// 迭代器遍历
		Iterator it = list.iterator();
		while (it.hasNext()) {
			System.out.println(it.next());
		}
	

3.3.2底层实现

3.3.2.1Node节点类

?

 * 链表 : 保存的都是节点,一个节点有三个属性 , 添加的数据 , 上一个节点引用, 下一个节点引用

?3.3.2.2LinkedList

3.3.2.3add方法实现

?

3.3.2.4Get方法实现

?

?获取数据

?

?

Get方法 只是模拟了下标获取数据的方式,本质就是遍历,从头挨个去找,所以这可以理解为 并不是下标,只是决定了循环次数,而 ArrayList的get才是根据下标获取

?

?