1. 机试题
1、输入一个字符串，判断判断这个字符串是否对称
例如abcba算对称 abccba也算对称
package com.wz.test01;
import java.util.Scanner;
public class test01 {
/**
* 输入一个字符串，判断判断这个字符串是否对称
* 例如abcba算对称 abccba也算对称
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("请输入字符串：");
String str = sc.next();
//定义两个指针
int start=0;
int end=str.length()-1;
boolean flag=true;
while(start<end){
char c1 = str.charAt(start);
char c2 = str.charAt(end);
if (c1!=c2){
flag=false;
break;
}
start++;
end--;
}
if (flag){
System.out.println("此字符串对称！");
}else {
System.out.println("此字符串不对称！");
}
sc.close();
}
}
2、实现HashMap的value排序
- 创建HashMap集合
- 利用EntrySet获取到集合内元素
- 把entrySet转为ArrayList数组
- 利用数组中的sort方法进行排序
- 重写compare排序规则
package com.wz.test02;
import java.util.*;
public class test01 {
/**
* 实现HashMap的value排序
*/
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
map.put("张三",26);
map.put("李四",22);
map.put("王五",16);
map.put("赵六",25);
map.put("AAA",21);
map.put("BBB",19);
map.put("CCC",28);
Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
ArrayList<Map.Entry<String, Integer>> list = new ArrayList<>(entrySet);
list.sort(new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
return Integer.compare(o1.getValue(),o2.getValue());
}
});
for (Map.Entry<String,Integer> entry:list
) {
System.out.println(entry);
}
}
}
3、设计一个线程（使用自定义线程池），使得字符串”成都是一座你来了就不想走的城市” 每隔1秒钟输出一个字符。 运 行结果如下：(多行输出)
成 成都 成都是 成都是一 成都是一座 成都是一座你 …… 成都是一座你来了就不想走的城市
package com.wz.test03;
public class Task implements Runnable{
@Override
public void run() {
String str = "成都是一座你来了就不想走的城市";
//字符串转换为字符数组
char[] cs = str.toCharArray();
for (int i = 0; i < cs.length; i++) {
for (int j = 0; j <= i; j++) {
System.out.print(cs[j]);
try {
Thread.sleep(1000);
} catch (InterruptedException e){
e.printStackTrace();
}
}
System.out.println();
}
}
}package com.wz.test03;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;
public class test01 {
/**
* 设计一个线程（使用自定义线程池），使得字符串”成都是一座你来了就不想走的城市” 每隔1秒钟输出一个字符。
* 运行结果如下：(多行输出)
* 成
* 成都
* 成都是
* 成都是一
* 成都是一座
* 成都是一座你
* ……
* 成都是一座你来了就不想走的城市
*/
public static void main(String[] args) {
/**
* 自定义线程池
* 1,核心线程数
* 1,最大线程数
* 0,闲置时间
* TimeUnit.SECONDS,时间单位
* new ArrayBlockingQueue<>(1)任务队列
*/
ThreadPoolExecutor pool = new ThreadPoolExecutor(1, 1, 0, TimeUnit.SECONDS, new ArrayBlockingQueue<>(1));
//创建任务对象
Task task = new Task();
//提交任务
pool.submit(task);
//关闭线程池
pool.shutdown();
}
}
4、任意输入一个字符串，编程输出这个字符串中第一个没有重复的字符的下标和该字符。如字符串为“dfablkfdalk”,则输出：3-b,如果所有字符均重复则输出“没有不重复的字符”。
package com.wz.test04;
import java.util.Scanner;
public class test01 {
/**
* 任意输入一个字符串，编程输出这个字符串中第一个没有重复的字符的下标和该字符。
* 如字符串为“dfablkfdalk”,则输出：3-b,如果所有字符均重复则输出“没有不重复的字符”。
*/
public static void main(String[] args) {
System.out.println("请输入一个字符串：");
Scanner sc = new Scanner(System.in);
String str = sc.next();
char[] cs = str.toCharArray();
for (int i = 0; i < cs.length; i++) {
char c = cs[i];
boolean flag=true;
for (int j = i+1; j < cs.length; j++) {
if (c==cs[j]){
flag = false;
break;
}
}
if (flag){
System.out.println(i+"--"+c);
break;
}
}
}
}
5、我们班现在要选举产生最卷的学生，每人有一次投票权，每人的票可以投给任意的学生，用面向对象编程实现这个功能。（假设班级人数6人）
package com.wz.test05;
public class Student {
private String name;
private int count;
public Student() {
}
public Student(String name) {
this.name = name;
}
public Student(String name, int count) {
this.name = name;
this.count = count;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", count=" + count +
'}';
}
}package com.wz.test05;
import java.awt.*;
import java.util.ArrayList;
import java.util.Scanner;
public class test01 {
/**
* 我们班现在要选举产生最卷的学生，每人有一次投票权，每人的票可以投给任意的学生
* 用面向对象编程实现这个功能。（假设班级人数6人）
*/
public static void main(String[] args) {
java.util.ArrayList<Student> list = new ArrayList<>();
list.add(new Student("张三"));
list.add(new Student("李四"));
list.add(new Student("王五"));
list.add(new Student("赵六"));
list.add(new Student("AAA"));
list.add(new Student("BBB"));
Scanner scan = new Scanner(System.in);
for (int i = 0; i < list.size(); i++) {
Student student = list.get(i);
System.out.println("请" + student.getName() + "同学投票：");
for (int j = 0; j < list.size(); j++) {
System.out.println((j+1) + " -- " + list.get(j).getName());
}
int index = scan.nextInt()-1;
list.get(index).setCount(list.get(index).getCount()+1);
}
for (Student student : list) {
System.out.println(student);
}
scan.close();
}
}
6、郭靖去银行办了一张银行卡和存折，卡上存了1000元，郭靖把存折给了黄蓉，他们俩同时去银行两个柜台，一人用银行卡，一人用存折取款，每次只能取100块，请使用多线程编程实现他们取出这1000块钱的过程。
package com.wz.test06;
public class Task implements Runnable{
private int money = 1000;
@Override
public void run() {
while (money>=100){
synchronized (this){
if (money>=100){
money-=100;
System.out.println(Thread.currentThread().getName()+"取钱了，余额为："+money);
}
}
}
}
}package com.wz.test06;
public class test01 {
/**
* 郭靖去银行办了一张银行卡和存折，卡上存了1000元，郭靖把存折给了黄蓉，
* 他们俩同时去银行两个柜台，一人用银行卡，一人用存折取款，
* 每次只能取100块，请使用多线程编程实现他们取出这1000块钱的过程。
*/
public static void main(String[] args) {
Task task = new Task();
Thread t1 = new Thread(task,"郭靖");
Thread t2 = new Thread(task, "黄蓉");
t1.start();
t2.start();
}
}
7、编写服务器和客户端，实现在服务器不断往客户端发送一个用户对象的过程，要求：服务器不断发送用户对象，客户端收到对象后不断存储在本地文件中。
注意：使用完需要关闭资源
package com.wz.test07;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.net.Socket;
public class Client {
/**
* 编写服务器和客户端，实现在服务器不断往客户端发送一个用户对象的过程，
* 要求：服务器不断发送用户对象，客户端收到对象后不断存储在本地文件中。
* @throws Exception
*/
public static void main(String[] args) throws Exception {
Socket socket = new Socket("127.0.0.1", 8080);
InputStream in = socket.getInputStream();
ObjectInputStream ois = new ObjectInputStream(in);
Student stu = null;
while((stu = (Student) ois.readObject()) != null){
System.out.println(stu);
}
}
}package com.wz.test07;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.net.ServerSocket;
import java.net.Socket;
import java.util.Scanner;
public class Server {
/**
* 编写服务器和客户端，实现在服务器不断往客户端发送一个用户对象的过程，
* 要求：服务器不断发送用户对象，客户端收到对象后不断存储在本地文件中。
*/
public static void main(String[] args) throws Exception {
ServerSocket server = new ServerSocket(8080);
Socket socket = server.accept();
Scanner scanner = new Scanner(System.in);
ObjectOutputStream oos = new ObjectOutputStream(socket.getOutputStream());
while (true) {
System.out.println("name:");
oos.writeObject(new Student(scanner.next()));
}
}
}package com.wz.test07;
import java.io.Serializable;
public class Student implements Serializable{
private static final long serialVersionUID = -3055854463625244431L;
private String name;
private int count;//获得的票数
public Student() {
}
public Student(String name) {
this.name = name;
}
public Student(String name, int count) {
this.name = name;
this.count = count;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
@Override
public String toString() {
return "Student [name=" + name + ", count=" + count + "]";
}
}
8、完成下列需求
1）创建部门枚举，对象有：JAVA、HTML、PYTHON 2）创建员工实体类，属性有：姓名、年龄、薪资、部门枚举 3) 实现员工的管理系统(底层数据结构不限)，有添加员工、删除员工、修改员工、查询员工 4）根据姓名、年龄段、薪资、部门等各种情况查询学生 5）编写统计员工信息方法，统计最高工资的员工、最低薪资的员工、根据部门统计员工，通过Stream流统计
//部门枚举
package com.wz.test08;
public enum Course {
JAVA,HTML,PYTHON;
}package com.wz.test08;
public class Staff {
private String name;
private int age;
private double salary;
private Course course;
public Staff() {
}
public Staff(String name, int age, double salary, Course course) {
this.name = name;
this.age = age;
this.salary = salary;
this.course = course;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public double getSalary() {
return salary;
}
public void setSalary(double salary) {
this.salary = salary;
}
public Course getCourse() {
return course;
}
public void setCourse(Course course) {
this.course = course;
}
@Override
public String toString() {
return "Staff{" +
"name='" + name + '\'' +
", age=" + age +
", salary=" + salary +
", course=" + course +
'}';
}
}package com.wz.test08;
import java.util.*;
import java.util.stream.Collectors;
public class test01 {
/**
* 1）创建部门枚举，对象有：JAVA、HTML、PYTHON
* 2）创建员工实体类，属性有：姓名、年龄、薪资、部门枚举
* 3) 实现员工的管理系统(底层数据结构不限)，有添加员工、删除员工、修改员工、查询员工
* 4）根据姓名、年龄段、薪资、部门等各种情况查询学生
* 5）编写统计员工信息方法，统计最高工资的员工、最低薪资的员工、根据部门统计员工，通过Stream流统计
*/
public static void main(String[] args) {
ArrayList<Staff> list = new ArrayList<>();
list.add(new Staff("张三",23,9500,Course.JAVA));
list.add(new Staff("李四",20,10000,Course.JAVA));
list.add(new Staff("王五",21,8500,Course.JAVA));
list.add(new Staff("赵六",18,9000,Course.PYTHON));
list.add(new Staff("AAA",19,5500,Course.HTML));
list.add(new Staff("BBB",27,6500,Course.PYTHON));
list.add(new Staff("CCC",30,7500,Course.JAVA));
list.add(new Staff("DDD",29,15000,Course.HTML));
list.add(new Staff("EEE",24,12000,Course.PYTHON));
//根据下标删除
list.remove(3);
//根据下标修改元素
list.get(1).setAge(18);
for (Staff staff:list
) {
System.out.println(staff);
}
System.out.println("-------------------");
ArrayList<Staff> newList = new ArrayList<>();
for (Staff staff:list
) {
if (staff.getCourse()==Course.JAVA){
newList.add(staff);
}
}
for (Staff staff:newList
) {
System.out.println(staff);
}
System.out.println("--------------------");
//编写统计员工信息方法，统计最高工资的员工、最低薪资的员工、根据部门统计员工，通过Stream流统计
//统计最高工资的员工
list.stream().sorted((staff1,staff2)->{
return Double.compare(staff2.getSalary(), staff1.getSalary());
}).limit(1).forEach(System.out::println);
System.out.println("------------------");
//最低薪资的员工
list.stream().sorted((staff1,staff2)->{
return Double.compare(staff1.getSalary(), staff2.getSalary());
}).limit(1).forEach(System.out::println);
System.out.println("------------------");
//根据部门统计员工
Map<Course, List<Staff>> map = list.stream().collect(Collectors.groupingBy(Staff::getCourse));
Set<Map.Entry<Course,List<Staff>>> entrySet = map.entrySet();
for (Map.Entry<Course, List<Staff>> entry : entrySet) {
Course key = entry.getKey();
List<Staff> value = entry.getValue();
System.out.println(key);
System.out.println(Arrays.toString(value.toArray()));
}
}
}
迭代器实现原理
1 .Iterator迭代器实现原理
Iterator接口
boolean hasNext();//判断是否有可迭代的数据
E next();//获取下一个元素
package com.qf.iterator01;
//迭代器的接口
//作用：指定遍历数据的标准
public interface Iterator<E> {
//判断是否有可迭代的数据
boolean hasNext();
//获取下一个元素
E next();
//删除功能（默认抛异常，意味着集合实现的迭代器可以选择是否有删除元素的功能）
default void remove() {
throw new UnsupportedOperationException("remove");
}
}AbstractList 的抽象类，
modCount是一个用于记录修改次数的变量 （外部操作数）
package com.qf.iterator01;
public abstract class AbstractList<E> {
protected int modCount;//5s
}ArrayList底层
这段代码是一个ArrayList类的实现，它继承了AbstractList类。ArrayList是一个动态数组，可以根据需要自动扩容。
下面是对代码的解析：
elementData：是一个Object类型的数组，用于存储元素。size：表示元素的个数。DEFAULT_CAPACITY：默认容量，初始化ArrayList时使用的默认容量大小。DEFAULTCAPACITY_EMPTY_ELEMENTDATA：空内容的数组，用于初始化elementData。MAX_ARRAY_SIZE：最大数组长度，用于限制数组的最大容量。ArrayList()：构造方法，初始化ArrayList对象。add(E e)：向ArrayList中添加元素。在添加之前，通过ensureCapacityInternal方法确保容量足够，然后将元素添加到elementData数组中。ensureCapacityInternal(int minCapacity)：确保容量足够。如果elementData数组为空，则将minCapacity设置为默认容量和minCapacity的较大值；然后调用ensureExplicitCapacity方法进行容量检查。ensureExplicitCapacity(int minCapacity)：进行容量检查。如果需要扩容，则调用grow方法进行扩容。grow(int minCapacity)：扩容方法。根据当前数组的容量，计算新的容量，然后通过Arrays.copyOf方法将元素复制到新的数组中。hugeCapacity(int minCapacity)：计算巨大容量。如果minCapacity小于0，抛出内存溢出异常；否则，返回最大容量值。这样，这段代码实现了一个基本的ArrayList类，具备添加元素和自动扩容的功能。
package com.qf.iterator01;
import java.util.Arrays;
public class ArrayList<E> extends AbstractList<E> {
//元素容器
public Object[] elementData;
//元素个数
private int size;//5
//默认容量
private static final int DEFAULT_CAPACITY = 10;
//空内容的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//最大数组长度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE-8;
public ArrayList() {
elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
//minCapacity - 1
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//minCapacity - 10
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//minCapacity - 10
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//minCapacity - 10
private void grow(int minCapacity) {
//oldCapacity - 0
int oldCapacity = elementData.length;
//newCapacity - 0
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
//newCapacity - 10
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // 长度小于0就报内存溢出
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
}测试类test01
package com.qf.iterator01;
public class Test01 {
/**
* 知识点：研究Iterator如何遍历
*/
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("AAA");
list.add("BBB");
list.add("CCC");
list.add("DDD");
list.add("EEE");
for(Object obj : list.elementData){
System.out.println(obj);
}
}
}2. ListIterator底层
ListIterator的接口
package com.qf.iterator01;
public interface ListIterator<E> extends Iterator<E> {
boolean hasNext();//判断是否有下一个可迭代的元素
E next();//获取下一个元素
boolean hasPrevious();//判断是否有上一个可迭代的元素
E previous();//获取上一个元素
int nextIndex();//获取下一个元素下标
int previousIndex();//获取上一个元素下标
void remove();//删除元素
void set(E e);//修改元素
void add(E e);//添加元素
}iterator的接口
package com.qf.iterator01;
//迭代器的接口
//作用：指定遍历数据的标准
public interface Iterator<E> {
//判断是否有可迭代的数据
boolean hasNext();
//获取下一个元素
E next();
//删除功能（默认抛异常，意味着集合实现的迭代器可以选择是否有删除元素的功能）
default void remove() {
throw new UnsupportedOperationException("remove");
}
}
AbstractList的抽象类， 代码中定义了一个名为modCount的protected修饰的整型变量，它用于记录对集合的修改次数 。protected修饰符表示该变量可以被子类访问，但不能被其他包中的类访问。
package com.qf.iterator01;
public abstract class AbstractList<E> {
protected int modCount;//5
}ArrayList类
以下是对代码的解析：
ArrayList(int initialCapacity)：带有初始容量参数的构造方法。根据给定的初始容量创建一个ArrayList对象。size()：返回ArrayList中元素的个数。add(int index, E element)：在指定位置插入元素。首先进行下标的合法性检查，然后根据需要进行扩容，并通过System.arraycopy方法进行元素的移动，最后将新元素插入到指定位置。remove(Object o)：移除指定元素。如果元素为null，则遍历ArrayList找到第一个为null的元素进行移除；如果元素不为null，则通过equals方法找到第一个与指定元素相等的元素进行移除。remove(int index)：移除指定位置的元素。首先进行下标的合法性检查，然后通过System.arraycopy方法将元素进行移动，最后将最后一个元素设为null。set(int index, E element)：将指定位置的元素替换为新的元素。首先进行下标的合法性检查，然后将新元素赋值给指定位置的元素，并返回被替换的旧元素。Iterator()：获取迭代器的方法。ListIterator()：获取ListIterator的方法。Itr内部类：实现了Iterator接口，用于实现ArrayList的迭代功能。使用游标cursor和遍历到的当前元素的下标lastRet来追踪迭代的状态。ListItr内部类：继承了Itr，实现了ListIterator接口，用于实现ArrayList的双向迭代功能。添加了hasPrevious()、previous()、nextIndex()、previousIndex()、set(E e)、add(E e)等方法。这样，这段代码实现了一个完整的ArrayList类，具备添加、删除、修改、迭代等功能。
package com.qf.iterator01;
import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.NoSuchElementException;
public class ArrayList<E> extends AbstractList<E> {
//元素容器
public Object[] elementData;
//元素个数
private int size;//5
//默认容量
private static final int DEFAULT_CAPACITY = 10;
//空内容的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//空内容的数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//最大数组长度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE-8;
public ArrayList() {
elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public int size() {
return size;
}
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
//插入元素
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // 判断是否扩容
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException("下标越界:" + index);
}
//minCapacity - 1
private void ensureCapacityInternal(int minCapacity) {
//使用无参构造创建ArrayList，第一次添加元素时进入的判断 -- 目的：确定初始化数组的长度
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//minCapacity - 10
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//minCapacity - 10
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//minCapacity - 10
private void grow(int minCapacity) {
//oldCapacity - 0
int oldCapacity = elementData.length;
//newCapacity - 0
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
//newCapacity - 10
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // 长度小于0就报内存溢出
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException("index:" + index);
}
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;//计算数据迁移的次数
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null;
}
public E set(int index, E element) {
rangeCheck(index);//判断下标是否合法
E oldValue = elementData(index);//通过下标获取到元素
elementData[index] = element;//把新的元素赋值给指定下标的位置
return oldValue;//返回被替换的值
}
//获取迭代器的方法
public Iterator<E> Iterator(){
return new Itr();
}
public ListIterator<E> listIterator() {
return new ListItr(0);
}
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
public class Itr implements Iterator<E>{
//游标 -- 判断是否有可迭代的数据的变量
int cursor; //0
//遍历到的当前元素的下标
int lastRet = -1;//-1
//内部操作数
int expectedModCount = modCount;//5
@Override
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
@Override
public E next() {
checkForComodification();//判断内外部操作数使用一致
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
final void checkForComodification() {
if(expectedModCount != modCount){
throw new ConcurrentModificationException();
}
}
@Override
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
//迭代器中删除功能还是依赖于ArrayList的删除功能
ArrayList.this.remove(lastRet);
//把当前元素的下标赋值给游标
cursor = lastRet;
//将-1赋值给lastRet，说明该元素删除
lastRet = -1;
//将外部操作数赋值给内部操作数
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
public class ListItr extends Itr implements ListIterator<E>{
public ListItr(int index) {
cursor = index;
}
@Override
public boolean hasPrevious() {
return cursor != 0;
}
@SuppressWarnings("unchecked")
@Override
public E previous() {
checkForComodification();//判断外部操作数和内部操作数是否一致
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
@Override
public int nextIndex() {
return cursor;
}
@Override
public int previousIndex() {
return cursor-1;
}
@Override
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);//依赖于外部类ArrayList的set方法
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
public void add(E e) {
checkForComodification();//判断外部操作数和内部操作数是否一致
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;//重新将外部操作数赋值给内部操作数
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
}3. LinkedList底层
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
//外部操作数
protected transient int modCount = 0;
public ListIterator<E> listIterator() {
return listIterator(0);
}
}
public abstract class AbstractSequentialList<E> extends AbstractList<E> {
public Iterator<E> iterator() {
return listIterator();
}
public ListIterator<E> listIterator() {
return listIterator(0);
}
public ListIterator<E> listIterator(final int index) {
rangeCheckForAdd(index);
return new ListItr(index);
}
}
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>{
//元素个数
transient int size = 0;
//开始节点
transient Node<E> first;
//结束节点
transient Node<E> last;
public LinkedList() {
}
public boolean add(E e) {
linkLast(e);
return true;
}
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++;
}
//index - 0
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
//index - 0
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
//获取指定下标上的节点对象
//index - 0
Node<E> node(int 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;
}
}
//节点类
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;
}
}
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;//第一个节点
private Node<E> next;//获取第三个节点
private int nextIndex;//2
private int expectedModCount = modCount;//3
ListItr(int 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;//lastReturned - 第二个节点
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();
}
}
}LinkedList<String> list = new LinkedList<>();
list.add("张三");
list.add("李四"）;
list.add("王五");