文章目录
- 1. 集合概述
- 2.Collection
- 2.1 Collection继承结构(基于Java21)
- 2.2 Collection接口的常用方法
- 2.3 Collection的遍历(集合的通用遍历方式)
- 2.4 所有的有序集合都实现了SequencedCollection接口
- 2.5 泛型
- 2.5.1 如何判断是否可以使用泛型?
- 2.5.2 泛型的擦除与补偿(了解)
- 2.5.3 泛型的使用
- 2.5.3.1 在类上定义泛型
- 2.5.3.2 在方法上定义泛型(上述示例已有)
- 2.5.3.3 在接口上定义泛型
- 2.5.4 泛型通配符(使用泛型)
- 2.6 迭代时删除元素
- 2.6.1 fail-fast机制
- 2.7 List接口
- 2.7.1 List接口特有方法
- 2.7.2 List接口特有迭代
- 2.7.3 使用Comparable和Comparator定义比较规则
- 2.7.3.1 数组的排序使用Comparable接口:
- 2.7.3.2 List接口的排序使用Comparator接口
- 2.7.4 ArrayList
- 2.7.5 Vector
- 2.7.6 链表
- 2.7.6.1 LinkedList
- 2.7.6.2 手写单向链表:
- 2.8 栈数据结构
- 2.9 队列
- 2.8.1 单向队列
- 2.8.2 双端(向)队列
这一章非常重要,每一个点都必须吃透!!!
1. 集合概述
- 什么是集合,有什么用?
①集合是一种容器,用来组织和管理数据的。非常重要。
②Java的集合框架对应的这套类库其实就是对各种数据结构的实现。
③每一个集合类底层采用的数据结构不同,例如ArrayList集合底层采用了数组,LinkedList集合底层采用了双向链表,HashMap集合底层采用了哈希表,TreeMap集合底层采用了红黑树。
④我们不用写数据结构的实现了。直接用就行了。但我们需要知道的是在哪种场合下选择哪一个集合效率是最高的。 - 集合中存储的是引用,不是把堆中的对象存储到集合中,是把对象的地址存储到集合中。
- 默认情况下,如果不使用泛型的话,集合中可以存储任何类型的引用,只要是Object的子类都可以存储。
- Java集合框架相关的类都在
java.util
包下。 - Java集合框架分为两部分:
①Collection结构:元素以单个形式存储。
②Map结构:元素以键值对的映射关系存储。
一个代码示例:如果不使用泛型的话,集合中可以存储任何类型的引用,只要是Object的子类都可以存储。
package collectiontest;import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;public class CollectionTest01 {public static void main(String[] args) {//创建一个CollectionCollection c = new ArrayList();//添加任意类型的元素c.add("String");c.add(false);c.add(1);c.add(22.3);c.add(new Dog());//获取其迭代器,遍历Iterator iterator = c.iterator();while (iterator.hasNext()) {Object object = iterator.next();System.out.println(object);}}
}class Dog{}
运行结果:
2.Collection
2.1 Collection继承结构(基于Java21)
SequencedCollection
和SequencedSet
接口都是Java21新增的接口。- 上图中蓝色的是实现类。其它的都是接口。
- 6个实现类中只有HashSet是无序集合。剩下的都是有序集合。
①有序集合:集合中存储的元素有下标或者集合中存储的元素是可排序的。
②无序集合:集合中存储的元素没有下标并且集合中存储的元素也没有排序。 - 每个集合实现类对应的数据结构如下:
①LinkedList:双向链表(不是队列数据结构,但使用它可以模拟队列)
②ArrayList:数组
③Vector:数组(线程安全的)
④HashSet:哈希表
⑤LinkedHashSet:双向链表和哈希表结合体
⑥TreeSet:红黑树 - List集合中存储的元素可重复。Set集合中存储的元素不可重复。
-
Java21新版UML图:
-
旧版(没有SequencedCollection和SequencedSet):
2.2 Collection接口的常用方法
①boolean add(E e); 向集合中添加元素 (对于普通数据类型,其会自动装箱)
②int size(); 获取集合中元素个数
③boolean addAll(Collection c); 将参数集合中所有元素全部加入当前集合
④boolean contains(Object o); 判断集合中是否包含对象o (底层会调用equals方法进行比对)
⑤boolean remove(Object o); 从集合中删除对象o (底层也会调用equals方法进行删除)
⑥void clear(); 清空集合
⑦boolean isEmpty(); 判断集合中元素个数是否为0
⑧Object[] toArray(); 将集合转换成一维数组
示例代码:
package collectiontest;import java.util.ArrayList;
import java.util.Collection;public class CollectionTest02 {public static void main(String[] args) {Collection c = new ArrayList();//添加元素c.add(100); //自动装箱c.add(2.34); //自动装箱c.add(false); //自动装箱c.add("字符串");c.add(new Object());//查看集合中元素个数System.out.println("集合中元素个数:" + c.size());//再创建一个集合对象Collection c2 = new ArrayList();//添加元素c.add(101); //自动装箱c.add(true); //自动装箱c.add(new Object());//一次添加多个,将一个集合中的所有元素添加打当前集合对象中c.addAll(c2);//查看集合中元素个数System.out.println("集合中元素个数:" + c.size());//判断集合中是否包含某个元素System.out.println(c.contains(101)); //trueSystem.out.println(c.contains(200)); //falseString str1 = new String("字符串");System.out.println(c.contains(str1)); //true//判断集合是否为空System.out.println("当前集合是否为空:" + c.isEmpty());//删除集合中指定元素System.out.println("-----------删除一个元素-----------");String str2 = new String("字符串");c.remove(str2);System.out.println("集合中元素个数:" + c.size());//将集合转换为数组Object[] objects = c.toArray();for (Object o:objects) {System.out.println(o);}//清空集合c.clear();//判断集合是否为空System.out.println("集合中元素个数:" + c.size());}
}
运行结果:
2.3 Collection的遍历(集合的通用遍历方式)
第一步:获取当前集合依赖的迭代器对象:
Iterator it = collection.iterator();
第二步:编写循环,循环条件是:当前光标指向的位置是否存在元素:
while(it.hasNext()){}
第三步:如果有,将光标指向的当前元素返回,并且将光标向下移动一位:
Object obj = it.next();
原理说明:
示例代码:
package collectiontest;import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;/*** Collection下所有类都通用的遍历方式*/
public class CollectionTest03 {public static void main(String[] args) {Collection c = new ArrayList();c.add(100);c.add(false);c.add(2.34);c.add("string");System.out.println("使用while循环遍历:");Iterator iterator = c.iterator();while (iterator.hasNext()){System.out.println(iterator.next());}System.out.println("============================");System.out.println("使用for循环遍历:");//或者使用for循环for (Iterator iterator1 = c.iterator(); iterator1.hasNext();) {System.out.println(iterator1.next());}}
}
运行结果:
2.4 所有的有序集合都实现了SequencedCollection接口
- SequencedCollection接口是Java21版本新增的。
- SequencedCollection接口中的方法:
①void addFirst(Object o):向头部添加
②void addLast(Object o):向末尾添加
③Object removeFirst():删除头部
④Object removeLast():删除末尾
⑤Object getFirst():获取头部节点
⑥Object getLast():获取末尾节点
⑦SequencedCollection reversed(); 反转集合中的元素 - ArrayList,LinkedList,Vector,LinkedHashSet,TreeSet,Stack 都可以调用这个接口中的方法。
示例代码:
package collectiontest;import java.util.ArrayList;
import java.util.Iterator;
import java.util.SequencedCollection;/*** 有序集合的祖宗接口*/
public class SequencedCollectionTest {public static void main(String[] args) {SequencedCollection c = new ArrayList();c.add(1);c.add(2);c.add(3);c.add(4);//向头部添加一个元素c.addFirst(0);//向尾部添加一个元素c.addLast(5);//获取头部元素System.out.println("头部元素:" + c.getFirst());//获取尾部元素System.out.println("尾部元素:" + c.getLast());//遍历Iterator iterator = c.iterator();while (iterator.hasNext()){System.out.println(iterator.next());}//从头部删除一个元素c.removeFirst();//从尾部删除一个元素c.removeLast();//再次遍历Iterator iterator1 = c.iterator();while (iterator1.hasNext()){System.out.println(iterator1.next());}//倒置SequencedCollection reversedc = c.reversed();//遍历Iterator iterator2 = c.iterator();while (iterator2.hasNext()){System.out.println(iterator2.next());}}
}
运行结果:无(因为用的是java8,所以运行不了)
2.5 泛型
- 泛型是Java5的新特性,属于编译阶段的功能。
- 泛型可以让开发者在编写代码时指定集合中存储的数据类型。
- 泛型作用:
①类型安全:指定了集合中元素的类型之后,编译器会在编译时进行类型检查,如果尝试将错误类型的元素添加到集合中,就会在编译时报错,避免了在运行时出现类型错误的问题。
②代码简洁:使用泛型可以简化代码,避免了繁琐的类型转换操作。比如,在没有泛型的时候,需要使用 Object 类型来保存集合中的元素,并在使用时强制类型转换成实际类型,而有了泛型之后,只需要在定义集合时指定类型即可。 - 在集合中使用泛型
Collection<String> strs = new ArrayList<String>();
这就表示该集合只能存储字符串,存储其它类型时编译器报错。
并且以上代码使用泛型后,避免了繁琐的类型转换,集合中的元素可以直接调用String类特有的方法。 - Java7的新特性:钻石表达式(省略后面<>中的类型)
Collection<String> strs = new ArrayList<>();
示例代码(不使用泛型):
package collectiontest;import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.UUID;/*** 当前程序不使用泛型缺点:* 代码写得比较多,每一次从集合中取出的元素要想访问子类中特有的方法,必须向下转型* 而实际大部分都是需要写向下转型的吗,因为Object类中的方法肯定是不够用的,一定会调用子类方法*/
public class GenericTest01 {public static void main(String[] args) {//创建集合Collection c = new ArrayList();//创建User对象User user1 = new User("Li");User user2 = new User("Wang");User user3 = new User("Zhao");//向集合中添加User对象c.add(user1);c.add(user2);c.add(user3);//遍历Iterator it = c.iterator();while (it.hasNext()){Object o = it.next();if(o instanceof User){User user = (User)o; //必须向下转型才能调用User中的pay方法user.pay();}}}
}
示例代码(使用泛型):
package collectiontest;import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;/*** 使用泛型*/
public class GenericTest02 {public static void main(String[] args) {//创建集合,要求其只能存放User类型的对象,不能存储其他类型Collection<User> c = new ArrayList<>();//创建User对象User user1 = new User("Li");User user2 = new User("Wang");User user3 = new User("Zhao");//向集合中添加User对象c.add(user1);c.add(user2);c.add(user3);//编译器报错,不能添加其他类型
// c.add("ada");//遍历Iterator<User> it = c.iterator();while (it.hasNext()){User u = it.next(); //获取到的就是User类型的对象u.pay(); //不用转型,直接调用}}
}
运行结果:
2.5.1 如何判断是否可以使用泛型?
看帮助文档中对应类、方法上是否有“<>”符号,有这个符号的就都可以使用泛型。
2.5.2 泛型的擦除与补偿(了解)
- 泛型的出现提高了编译时的安全性,正因为编译时对添加的数据做了检查,则程序运行时才不会抛出类型转换异常。因此泛型本质上是编译时期的技术,是专门给编译器用的。加载类的时候,会将泛型擦除掉(擦除之后的类型为Object类型),这个称为泛型擦除。
- 为什么要有泛型擦除呢?其本质是为了让JDK1.4和JDK1.5能够兼容同一个类加载器。在JDK1.5版本中,程序编译时期会对集合添加的元素进行安全检查,如果检查完是安全的、没有错误的,那么就意味着添加的元素都属于同一种数据类型,则加载类时就可以把这个泛型擦除掉,将泛型擦除后的类型就是Object类,这样擦除之后的代码就与JDK1.4的代码一致。
- 由于加载类的时候,会默认将类中的泛型擦除为Object类型,所以添加的元素就被转化为Object类型,同时取出的元素也默认为Object类型。而我们获得集合中的元素时,按理说取出的元素应该是Object类型,为什么取出的元素却是实际添加的元素类型呢?
- 这里又做了一个默认的操作,我们称之为泛型的补偿。在程序运行时,通过获取元素的实际类型进行强转,这就叫做泛型补偿(不必手动实现强制转换)。获得集合中的元素时,虚拟机会根据获得元素的实际类型进行向下转型,也就是会恢复获得元素的实际类型,因此我们就无需手动执行向下转型操作,从本质上避免了抛出类型转换异常。
2.5.3 泛型的使用
2.5.3.1 在类上定义泛型
class 类名<泛型1,泛型2,泛型3...>{}
示例代码:
package collectiontest;/*** 在类上定义泛型* @param <NameType>* @param <AgeType>*/
public class MyClass<NameType, AgeType> { //在类声明的时候,给类声明/定义一个泛型private NameType name;private AgeType age;public MyClass() {}public MyClass(NameType name, AgeType age) {this.name = name;this.age = age;}public NameType getName() {return name;}public void setName(NameType name) {this.name = name;}public AgeType getAge() {return age;}public void setAge(AgeType age) {this.age = age;}public static void main(String[] args) {MyClass<String,Integer> myClass = new MyClass<>("lulu",24);
// MyClass<String,Integer> myClass = new MyClass<>("lulu","24"); //类型检查不通过,编译报错System.out.println(myClass.getName());System.out.println(myClass.getAge());}
}
运行结果:
2.5.3.2 在方法上定义泛型(上述示例已有)
在类上定义的泛型,在静态方法中无法使用。
如果在静态方法中使用泛型,则需要再方法返回值类型前面进行泛型的声明。语法格式:static <泛型1, 泛型2, 泛型3, ...> 返回值类型 方法名(形参列表) {}
。
示例代码:
package collectiontest;public class Customer {public static <E> void print(E[] elts){ //在静态方法处使用泛型,需要在返回值前面先声明泛型for (E e: elts) {System.out.println(e);}}public static void main(String[] args) {String[] str = {"li","wang"};Customer.print(str);}
}
运行结果:
2.5.3.3 在接口上定义泛型
语法格式:interface 接口名<泛型1,泛型2,...> {}
例如:public interface Flayable<T>{}
- 实现接口时,如果知道具体的类型,则:
public class MyClass implements Flyable<Bird>{}
- 实现接口时,如果不知道具体的类型,则:
public class MyClass<T> implements Flyable<T>{}
示例代码:
package collectiontest;public interface MyComparable<T> { //接口上定义泛型int compareTo(T o);
}
package collectiontest;public class Product implements MyComparable<Product>{ //继承自定义接口,并指定泛型对应的类private int price;public Product() {}public Product(int price) {this.price = price;}@Overridepublic int compareTo(Product o) {int flag = this.price - o.price;if (flag > 0){return 1;}else if(flag == 0){return 0;}return -1;}public static void main(String[] args) {Product product1 = new Product(101);Product product2 = new Product(10);System.out.println(product1.compareTo(product2)); }
}
2.5.4 泛型通配符(使用泛型)
- 泛型是在限定数据类型,当在集合或者其他地方使用到泛型后,那么这时一旦明确泛型的数据类型,那么在使用的时候只能给其传递和数据类型匹配的类型,否则就会报错。
- 有的情况下,我们在定义方法时,根本无法确定集合中存储元素的类型是什么。为了解决这个“无法确定集合中存储元素类型”问题,那么Java语言就提供了泛型的通配符。
- 通配符的几种形式:
- 无限定通配符,<?>,此处“?”可以为任意引用数据类型。
- 上限通配符,<? extends Number>,此处“?”必须为Number及其子类。
- 下限通配符,<? super Number>,此处“?”必须为Number及其父类。
示例代码:
package collectiontest;import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;/*** 使用泛型*/
public class GenericTest03 {public static void print(ArrayList<?> list){}public static void print1(ArrayList<? extends Number> list){}public static void print2(ArrayList<? super String> list){}public static void print3(ArrayList<? super B> list){}public static void main(String[] args) {print(new ArrayList<String>());print(new ArrayList<Integer>());print(new ArrayList<Object>());print(new ArrayList<A>());print1(new ArrayList<Float>());print1(new ArrayList<Double>());print1(new ArrayList<Integer>());//编译报错
// print1(new ArrayList<A>());print2(new ArrayList<String>());print2(new ArrayList<Object>());//编译报错
// print2(new ArrayList<Number>());print3(new ArrayList<A>());print3(new ArrayList<B>());//编译报错
// print3(new ArrayList<C>());}
}class A{}class B extends A{}class C extends B{}
2.6 迭代时删除元素
- 迭代时,使用集合带的remove方法(
集合对象.remove(元素)
)删除元素
package collectiontest;import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;public class CollectionTest04 {public static void main(String[] args) {Collection<String> c = new ArrayList<>();c.add("Mili");c.add("Dahuang");c.add("Yuanbao");c.add("Qiuqiu");System.out.println("当前集合元素个数:" + c.size());Iterator<String> iterator = c.iterator();//迭代集合时删除集合中的某个元素while (iterator.hasNext()){String name = iterator.next(); //java.util.ConcurrentModificationException并发修改异常if("Dahuang".equals(name)){//使用集合带的remove方法删除元素c.remove(name);}}System.out.println("当前集合元素个数:" + c.size());}
}
运行结果:
- 迭代时,使用迭代器带的remove方法(
迭代器对象.remove()
)删除元素
package collectiontest;import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;public class CollectionTest04 {public static void main(String[] args) {Collection<String> c = new ArrayList<>();c.add("Mili");c.add("Dahuang");c.add("Yuanbao");c.add("Qiuqiu");System.out.println("当前集合元素个数:" + c.size());Iterator<String> iterator = c.iterator();//迭代集合时删除集合中的某个元素while (iterator.hasNext()){String name = iterator.next();if("Dahuang".equals(name)){//使用迭代器带的remove方法删除元素,可以正常删除iterator.remove();}}System.out.println("当前集合元素个数:" + c.size());}
}
运行结果:
2.6.1 fail-fast机制
- 如何解决并发修改问题:fail-fast机制
fail-fast机制又被称为:快速失败机制。也就是说只要程序发现了程序对集合进行了并发修改。就会立即让其失败,以防出现错误。 - fail-fast机制是如何实现的?以下是源码中的实现原理:
1)集合中设置了一个modCount
属性,用来记录修改次数,使用集合对象执行增,删,改中任意一个操作时,modCount
就会自动加1。
2)获取迭代器对象的时候,会给迭代器对象初始化一个expectedModCount
属性。并且将expectedModCount
初始化为modCount
,即:int expectedModCount = modCount;
3)当使用集合对象删除元素时:modCount
会加1。但是迭代器中的expectedModCount
不会加1。而当迭代器对象的next()
方法执行时,会检测expectedModCount
和modCount
是否相等,如果不相等,则抛出:ConcurrentModificationException
异常。
4)当使用迭代器删除元素的时候:modCount
会加1,并且expectedModCount
也会加1。这样当迭代器对象的next()
方法执行时,检测到的expectedModCount
和modCount
相等,则不会出现ConcurrentModificationException
异常。
注意:虽然我们当前写的程序是单线程的程序,并没有使用多线程,但是通过迭代器去遍历的同时使用集合去删除元素,这个行为将被认定为并发修改。
结论:迭代集合时,删除元素要使用迭代器对象.remove()
方法来删除,避免使用集合对象.remove(元素)
。主要是为了避免ConcurrentModificationException
异常的发生。
注意:迭代器的remove()
方法删除的是next()
方法的返回的那个数据。remove()
方法调用之前一定是先调用了next()
方法,如果不是这样的,就会报错。
2.7 List接口
- List集合存储元素特点:有序可重复。
1) 有序:List集合中的元素都是有下标的,从0开始,以1递增。
2) 可重复:存进去1,还可以再存一个1。 - List接口下常见的实现类有:
ArrayList:数组
Vector、Stack:数组(线程安全的)
LinkedList:双向链表
2.7.1 List接口特有方法
在Collection和SequencedCollection中没有的方法,只适合List家族使用的方法,这些方法都和下标有关系:
void add(int index, E element) 在指定索引处插入元素
E set(int index, E element); 修改索引处的元素
E get(int index); 根据索引获取元素(通过这个方法List集合具有自己特殊的遍历方式:根据下标遍历)
E remove(int index); 删除索引处的元素
int indexOf(Object o); 获取对象o在当前集合中第一次出现时的索引。
int lastIndexOf(Object o); 获取对象o在当前集合中最后一次出现时的索引。
List subList(int fromIndex, int toIndex); 截取子List集合生成一个新集合(对原集合无影响)。[fromIndex, toIndex)
static List of(E… elements); 静态方法,返回包含任意数量元素的不可修改列表。(获取的集合是只读的,不可修改的。)
示例代码:
package collectiontest;import java.util.ArrayList;
import java.util.List;/*** List家族:有序(每个元素有下标,从0开始,以1递增),可重复(可存储相同元素)*/
public class ListTest01 {public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);list.add(1);//获取list中指定元素第一次出现的位置System.out.println(list.indexOf(1));//获取list中指定元素最后一次出现的位置System.out.println(list.lastIndexOf(1));//修改指定下标的元素list.set(0, -1); //将下标0处的元素修改为-1//移除指定下标处的元素list.remove(5);//List家族特有的遍历方法for (int i = 0; i < list.size(); i++) {System.out.println(list.get(i));}System.out.println("-------------------------------------");//获取指定下标范围的list,返回新的子listList<Integer> subList = list.subList(2, 4); //[2,4)for (int i = 0; i < subList.size(); i++) {System.out.println(subList.get(i));}//获取一个不可修改的集合,只读的集合(这里因为jdk版本不够,无法运行)
// List<Integer> nums = List.of(1,2,4,56,7);}
}
运行结果:
2.7.2 List接口特有迭代
- 特有的迭代方式
ListIterator listIterator(); 获取List集合特有的迭代器(该迭代器功能更加强大,但只适合于List集合使用)
ListIterator listIterator(int index); 从列表中的指定位置开始,返回列表中元素的列表迭代器
- ListIterator接口中的常用方法:
boolean hasNext(); 判断光标当前指向的位置是否存在元素。
E next(); 将当前光标指向的元素返回,然后将光标向下移动一位。
void remove(); 删除上一次next()方法返回的那个数据(删除的是集合中的)。remove()方法调用的前提是:你先调用next()或previous()方法。不然会报错。
void add(E e); 添加元素(将元素添加到光标指向的位置,然后光标向下移动一位。)
boolean hasPrevious(); 判断当前光标指向位置的上一个位置是否存在元素。
E previous(); 获取上一个元素(将光标向上移动一位,然后将光标指向的元素返回)
int nextIndex(); 获取光标指向的那个位置的下标
int previousIndex(); 获取光标指向的那个位置的上一个位置的下标
void set(E e); 修改的是上一次next()方法返回的那个数据(修改的是集合中的)set()方法调用的前提是:你先调用了next()或previous()方法。不然会报错。
示例代码:
package collectiontest;import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;public class ListTest02 {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("Mili");list.add("Dahuang");list.add("Yuanbao");list.add("Qiuqiu");//使用List特有的迭代器进行遍历System.out.println("使用List特有的迭代器进行遍历:");ListIterator<String> ListIterator1 = list.listIterator();while (ListIterator1.hasNext()){String name = ListIterator1.next();System.out.println(name);}System.out.println("------------------------");//测试List特有的add方法ListIterator<String> ListIterator2 = list.listIterator();while (ListIterator2.hasNext()){String name = ListIterator2.next();if("Dahuang".equals(name)){ListIterator2.add("小圆"); //不能使用从Collection继承过来的add方法,会出现ConcurrentModificationException异常}}for (int i = 0; i < list.size(); i++) {System.out.println(list.get(i));}System.out.println("------------------------");//测试hasPrevious,判断是否有上一个//判断当前光标指向位置的上一个位置是否存在元素ListIterator<String> ListIterator3 = list.listIterator();System.out.println("当前光标指向位置的上一个位置是否存在元素:" + ListIterator3.hasPrevious());while (ListIterator3.hasNext()){String name = ListIterator3.next();System.out.println(name);}System.out.println("当前光标指向位置的上一个位置是否存在元素:" + ListIterator3.hasPrevious());System.out.println("------------------------");//测试previous,获取上一个元素(将光标向上移动一位,然后将光标指向的元素返回)ListIterator<String> ListIterator4 = list.listIterator();while (ListIterator4.hasNext()){String name = ListIterator4.next();System.out.println(name);}System.out.println("当前光标指向元素的上一个元素:" + ListIterator4.previous()); //调用一次,光标向上移动一次System.out.println("当前光标指向元素的上一个元素:" + ListIterator4.previous());System.out.println("当前光标指向元素的上一个元素:" + ListIterator4.previous());System.out.println("当前光标指向元素的上一个元素:" + ListIterator4.previous());System.out.println("当前光标指向元素的上一个元素:" + ListIterator4.previous());
// System.out.println("当前光标指向元素的上一个元素:" + ListIterator4.previous()); //“越界”:java.util.NoSuchElementExceptionSystem.out.println("------------------------");//测试nextIndex(): 获取光标指向的那个位置的下标ListIterator<String> ListIterator5 = list.listIterator();while (ListIterator5.hasNext()){String name = ListIterator5.next(); //取出当前元素后,光标已下移if("Yuanbao".equals(name)){System.out.println(ListIterator5.nextIndex()); //4//previousIndex():获取光标指向的那个位置的上一个位置的下标System.out.println(ListIterator5.previousIndex()); //3}System.out.println(name);}System.out.println("------------------------");//测试set(E e): 修改的是前面next()方法返回的那个数据(修改的是集合中的),前提是前面有调用next()方法或者previous()方法,否则报错ListIterator<String> ListIterator6 = list.listIterator();while (ListIterator6.hasNext()){String name = ListIterator6.next();if("Yuanbao".equals(name)){ListIterator6.set("元宝");}}for (int i = 0; i < list.size(); i++) {System.out.println(list.get(i));}System.out.println("------------------------");}
}
运行结果:
2.7.3 使用Comparable和Comparator定义比较规则
2.7.3.1 数组的排序使用Comparable接口:
所有自定义类型排序时必须指定排序规则。(int不需要指定,String不需要指定,因为他们都有固定的排序规则。int按照数字大小。String按照字典中的顺序)
如何给自定义类型指定排序规则?让自定义类型实现java.lang.Comparable
接口,然后重写compareTo
方法,在该方法中指定比较规则。
package collectiontest;import java.util.Arrays;public class ListTest03 {public static void main(String[] args) {Person[] people = new Person[4];Person person1 = new Person(23,"nini");Person person2 = new Person(16,"jingjing");Person person3 = new Person(34,"yingying");Person person4 = new Person(14,"huanhuan");people[0] = person1;people[1] = person2;people[2] = person3;people[3] = person4;Arrays.sort(people);System.out.println(Arrays.toString(people));}
}/*** Person实现Comparable接口,Comparable接口可以使用泛型*/
class Person implements Comparable<Person>{int age;String name;public Person() {}public Person(int age, String name) {this.age = age;this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}@Overridepublic String toString() {return "Person{" +"age=" + age +", name='" + name + '\'' +'}';}//重写compareTo方法@Overridepublic int compareTo(Person p) {return this.age - p.age ; //按年龄升序}
}
运行结果:
2.7.3.2 List接口的排序使用Comparator接口
default void sort(Comparator<? super E> c)
:对List集合中元素排序可以调用此方法。sort方法需要一个参数: java.util.Comparator
。我们把这个参数叫做比较器。这是一个接口。
如何给自定义类型指定比较规则?
-
可以对
Comparator
提供一个实现类,并重写compare
方法来指定比较规则。 -
Comparator
接口的实现类也可以采用匿名内部类的方式。 -
方法一:创建一个类实现Comparator接口:
package collectiontest;public class Person {int age;String name;public Person() {}public Person(int age, String name) {this.age = age;this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}@Overridepublic String toString() {return "Person{" +"age=" + age +", name='" + name + '\'' +'}';}
}
package collectiontest;import java.util.Comparator;/*** PeopleComparator定义Person的比较规则,实现Comparator接口,可以使用泛型*/
public class PeopleComparator implements Comparator<Person> {@Overridepublic int compare(Person o1, Person o2) {return o1.age - o2.age; //按年龄升序排序}
}
package collectiontest;import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;public class ListTest03 {public static void main(String[] args) {List<Person> people = new ArrayList<>();Person person1 = new Person(23,"nini");Person person2 = new Person(16,"jingjing");Person person3 = new Person(34,"yingying");Person person4 = new Person(14,"huanhuan");people.add(person1);people.add(person2);people.add(person3);people.add(person4);people.sort(new PeopleComparator()); //创建PeopleComparator对象并传入sort方法for (int i = 0; i < people.size(); i++) {System.out.println(people.get(i));}}
}
- 方法二:使用匿名内部类:
package collectiontest;import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;public class ListTest03 {public static void main(String[] args) {List<Person> people = new ArrayList<>();Person person1 = new Person(23,"nini");Person person2 = new Person(16,"jingjing");Person person3 = new Person(34,"yingying");Person person4 = new Person(14,"huanhuan");people.add(person1);people.add(person2);people.add(person3);people.add(person4);people.sort(new Comparator<Person>() { //使用匿名内部类@Overridepublic int compare(Person o1, Person o2) {return o1.age - o2.age;}});for (int i = 0; i < people.size(); i++) {System.out.println(people.get(i));}}
}
运行结果:
2.7.4 ArrayList
- ArrayList集合底层采用了数组这一数据结构。
- ArrayList集合优点:底层是数组,因此根据下标查找元素的时间复杂度是O(1)。因此检索效率高。
- ArrayList集合缺点:随机增删元素效率较低。不过只要数组的容量还没满,对末尾元素进行增删,效率不受影响。
- ArrayList集合适用场景:
需要频繁的检索元素,并且很少的进行随机增删元素时建议使用。 - ArrayList默认初始化容量:从源码角度可以看到,当调用无参数构造方法时,初始化容量0;当第一次调用add方法时将ArrayList容量初始化为10个长度。
- ArrayList集合扩容策略:底层扩容会创建一个新的数组,然后使用数组拷贝。扩容之后的新容量是原容量的1.5倍。
(使用ArrayList集合时最好也是预测大概数量,给定初始化容量,减少扩容次数。)
2.7.5 Vector
- Vector底层也是数组,和ArrayList相同。
- 不同的是Vector几乎所有的方法都是线程同步的(被synchronized修饰:线程排队执行,不能并发),因此Vector是线程安全的,但由于效率较低,很少使用。因为控制线程安全有新方式。
- Vector初始化容量:10
- Vector扩容策略:扩容之后的容量是原容量的2倍。
2.7.6 链表
-
单向链表:
-
双向链表
-
环形链表
- 环形单链表
- 环形双链表
- 链表优点:因为链表节点在空间存储上,内存地址不是连续的。因此删除某个节点时不需要涉及到元素位移的问题。因此链表随机增删元素效率较高。时间复杂度O(1)。
- 链表缺点:链表中元素在查找时,只能从某个节点开始顺序查找,因为链表节点的内存地址在空间上不是连续的。链表查找元素效率较低,时间复杂度O(n)。
- 链表的适用场景:需要频繁进行随机增删,但很少的查找的操作时。
2.7.6.1 LinkedList
LinkedList是一个双向链表,创建时调用无参构造方法是创建一个空链表。
简单示例代码:
package collectiontest;import java.util.LinkedList;public class LinkedListTest01 {public static void main(String[] args) {LinkedList<String> linkedList = new LinkedList<>();//新增linkedList.add("1");linkedList.add("3");linkedList.add("5");linkedList.add("4");//修改String oldValue = linkedList.set(2, "110");System.out.println(oldValue);//删除String removeValue = linkedList.remove(1);System.out.println(removeValue);//根据下标查询元素System.out.println(linkedList.get(1));}
}
运行结果:
2.7.6.2 手写单向链表:
package collectiontest;public class SingleLinkedList<E> {//链表长度private int size = 0;//单向链表的头结点private Node<E> first;public SingleLinkedList() {}//结点类:内部类/*** 单向链表的结点(建议定义成静态内部类)*/private static class Node<E>{/*** 数据*/E item;/*** 下一个结点的内存地址*/Node<E> next;/*** 构造一个结点对象* @param item 结点中的数据* @param next 下一个结点的内存地址*/public Node(E item, Node<E> next){this.item = item;this.next = next;}}/*** 增加元素到末尾* @param data 数据*/public void add(E data){Node<E> newNode = new Node<>(data,null);//如果当前为空链表if(first == null){first = newNode;size++;return;}Node<E> last = findLast();last.next = newNode;size++;}/*** 找到末尾结点* @return 末尾结点*/private Node<E> findLast() {//first为空,即为空链表if(first == null){return null;}//假设第一个结点就是最后一个结点Node<E> last = first;while (last.next != null){last = last.next;}return last;}/*** 在指定位置增加元素* @param index 下标* @param data 数据*/public void add(int index, E data){//按理应该先进行下标检查//创建新的结点对象Node<E> newNode = new Node<>(data,null);//找到需要插入位置的前一个结点Node<E> prev = node(index -1);newNode.next = prev.next;prev.next = newNode;size++;}/*** 返回索引处的结点对象* @param index 索引* @return 结点对象*/private Node<E> node(int index) {//假设头结点是下一个结点Node<E> next = first;for (int i = 0; i < index; i++) {next = next.next;}return next;}/*** 删除指定位置结点* @param index 下标*/public void remove(int index){//按理应该先进行下标检查//假设删除头结点if(index == 0){Node<E> oldFirst = first;first = first.next;oldFirst.next = null;oldFirst.item = null;size--;return;}//删除的不是头结点//获取被删除节点的上一个结点Node<E> prev = node(index-1);//获取被删除节点Node<E> removedNode = node(index);prev.next = removedNode.next;removedNode.next = null;removedNode.item = null;size--;}/*** 修改指定位置结点* @param index 下标* @param data 数据*/public void set(int index, E data){//按理应该先进行下标检查Node<E> node = node(index);node.item = data;}///*** 查询指定位置结点* @param index 下标* @return 数据*/public E get(int index){//按理应该先进行下标检查Node<E> node = node(index);return node.item;}//获取链表长度public int size(){return this.size;}
}
测试代码:
package collectiontest;/*** 手写单向链表*/
public class SingleLinkedListTest01 {public static void main(String[] args) {SingleLinkedList linkedList = new SingleLinkedList();linkedList.add(1);linkedList.add(2);linkedList.add(3);linkedList.add(4);linkedList.add(2,5);linkedList.remove(1);for (int i = 0; i < linkedList.size(); i++) {System.out.println(linkedList.get(i));}}
}
运行结果:
2.8 栈数据结构
LIFO原则(Last In,First Out):后进先出。
实现栈数据结构,可以用数组来实现,也可以用双向链表来实现。
- 用数组实现的代表是:Stack、ArrayDeque
- Stack:Vetor的子类,实现了栈数据结构,除了具有Vetor的方法,还扩展了其它方法,完成了栈结构的模拟。不过在JDK1.6(Java6)之后就不建议使用了,因为它是线程安全的,太慢了。Stack中的方法如下:
①E push(E item):压栈
②E pop():弹栈(将栈顶元素删除,并返回被删除的引用)
③int search(Object o):查找栈中元素(返回值的意思是:以1为开始,从栈顶往下数第几个)
④E peek():窥视栈顶元素(不会将栈顶元素删除,只是看看栈顶元素是什么。注意:如果栈为空时会报异常。) - ArrayDeque:实现了Deque接口
①E push(E item)
②E pop()
- 用链表实现的代表是:LinkedList
①E push(E item)
②E pop()
示例代码:
package collectiontest;import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Stack;/*** java.util.Stack:底层是数组,线程安全的,jdk1.6不建议用了* java.util.LinkedList:底层是双向链表(实现LIFO的同时,又实现了双向队列)* java.util.ArrayDeque:底层是数组(实现LIFO的同时,又实现了双向队列)* 以上三个类都实现了栈数据结构,都实现了LIFO*/
public class StackTest {public static void main(String[] args) {//创建栈Stack<String> stack1 = new Stack<>();LinkedList<String> stack2 = new LinkedList<>();ArrayDeque<String> stack3 = new ArrayDeque<>();//压栈stack1.push("1");stack1.push("2");stack1.push("3");stack1.push("4");//查看栈顶元素System.out.println("栈顶元素为:" + stack1.peek());//搜索栈中元素(返回位置,从栈顶开始计数,没有对应元素返回-1)System.out.println("1的位置:" + stack1.search("1"));//弹栈System.out.println(stack1.pop());System.out.println(stack1.pop());System.out.println(stack1.pop());System.out.println(stack1.pop());System.out.println("================================");// 压栈stack2.push("1");stack2.push("2");stack2.push("3");stack2.push("4");//弹栈System.out.println(stack2.pop());System.out.println(stack2.pop());System.out.println(stack2.pop());System.out.println(stack2.pop());System.out.println("================================");// 压栈stack3.push("1");stack3.push("2");stack3.push("3");stack3.push("4");//弹栈System.out.println(stack3.pop());System.out.println(stack3.pop());System.out.println(stack3.pop());System.out.println(stack3.pop());}
}
运行结果:
2.9 队列
- 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,队列是一种操作受限制的线性表。进行插入操作(入口)的端称为队尾,进行删除操作(出口)的端称为队头。
- 队列的插入操作只能在队尾操作,队列的删除操作只能在队头操作,因此队列是一种先进先出(First In First Out)的线性表,简称FIFO表。
- Queue接口是一种基于FIFO(先进先出)的数据结构,而Deque接口则同时支持FIFO和LIFO(后进先出)两种操作。因此Deque接口也被称为“双端(向)队列”。
- Java集合框架中队列的实现:
①链表实现方式:LinkedList
②数组实现方式:ArrayDeque
LinkedList和ArrayDeque都实现了Queue、Deque接口,因此这两个类都具备队列和双端队列的特性。
- LinkedList底层是基于双向链表实现的,因此它天然就是一个双端队列,既支持从队尾入队,从队头出队,也支持从队头入队,从队尾出队。用Deque的实现方式来说,就是它既实现了队列的offer()和poll()方法,也实现了双端队列的offerFirst()、offerLast()、pollFirst()和pollLast()方法等。
- ArrayDeque底层是使用环形数组实现的,也是一个双端队列。它比LinkedList更加高效,因为在数组中随机访问元素的时间复杂度是O(1),而链表中需要从头或尾部遍历链表寻找元素,时间复杂度是O(N)。环形数组并不是说数组是环形的结构,而是在逻辑上环形,或者说循环,循环数组下标:index = (start + i) % capacity
示例代码:
package collectiontest;import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;/*** java.util.ArrayQueue* java.util.LinkedList* 以上两个类都实现队列的FIFO结构*/
public class QueueTest {public static void main(String[] args) {//创建队列对象Queue<String> queue1 = new ArrayDeque<>();//入队queue1.offer("1");queue1.offer("2");queue1.offer("3");queue1.offer("4");//出队System.out.println(queue1.poll());System.out.println(queue1.poll());System.out.println(queue1.poll());System.out.println(queue1.poll());System.out.println("=====================");//创建队列对象Queue<String> queue2 = new LinkedList<>();//入队queue2.offer("a");queue2.offer("b");queue2.offer("c");queue2.offer("d");//出队System.out.println(queue2.poll());System.out.println(queue2.poll());System.out.println(queue2.poll());System.out.println(queue2.poll());}
}
运行结果:
2.8.1 单向队列
Queue接口基于Collection扩展的方法包括:
①boolean offer(E e); 入队。
②E poll(); 出队,如果队列为空,返回null。
③E remove(); 出队,如果队列为空,抛异常。
④E peek(); 查看队头元素,如果为空则返回null。
⑤E element(); 查看对头元素,如果为空则抛异常。
2.8.2 双端(向)队列
Deque接口基于Queen接口扩展的方法包括:
以下2个方法可模拟队列:
①boolean offerLast(E e); 从队尾入队
②E pollFirst(); 从队头出队
以下4个方法可模拟双端队列:
①boolean offerLast(E e); 从队尾入队
②E pollFirst(); 从队头出队
③boolean offerFirst(E e); 从队头入队
④E pollLast(); 从队尾出队
另外,offerLast+pollLast或者pollFirst+offerFirst可以模拟栈数据结构。或者也可以直接调用push/pop方法。
示例代码:
package collectiontest;import java.util.ArrayDeque;
import java.util.Deque;public class DequeTest {public static void main(String[] args) {//创建双端队列对象Deque<String> deque1 = new ArrayDeque<>();//队尾进,队头出System.out.println("队尾进,队头出:");deque1.offerLast("1");deque1.offerLast("2");deque1.offerLast("3");deque1.offerLast("4");System.out.println(deque1.pollFirst());System.out.println(deque1.pollFirst());System.out.println(deque1.pollFirst());System.out.println(deque1.pollFirst());System.out.println("队头进,队尾出:");//队头进,队尾出deque1.offerFirst("a");deque1.offerFirst("b");deque1.offerFirst("c");deque1.offerFirst("d");System.out.println(deque1.pollLast());System.out.println(deque1.pollLast());System.out.println(deque1.pollLast());System.out.println(deque1.pollLast());}
}
运行结果: