顺序表
- 顺序表是动态扩容的一个数组
- 顺序表物理地址和逻辑地址都是连续的
接口的实现
package myList;
import java.util.Arrays;
public class MyArrayList implements IList{
// 动态扩容的一个数组
public int[] arr;
public static final int numsize = 2;
int usesize;// 统计数组中有多少个有效元素
// 静态大小的数组
public MyArrayList(){
this.arr = new int[numsize];
}
// 动态的大小的数组
public MyArrayList(int capacity){
this.arr = new int[capacity];
}
/*
遍历顺序表
*/
public void display() {
for(int i = 0;i < this.usesize;i++){
System.out.print(this.arr[i]+" ");
}
System.out.println();
}
@Override
public boolean isFull() {
if(this.numsize == this.usesize) return true;
return false;
}
// 在数组的最后尾插一个元素
@Override
public void add(int data) {
checkCapacity();
this.arr[this.usesize] = data;
this.usesize++;
}
// 在指定位置(pos位置)新增元素
@Override
public void add(int pos, int data) {
try{
checkPos(pos);
}catch(PosIllegality e){
e.printStackTrace();
// 处理异常
return;
}
checkCapacity();
for(int i = usesize - 1;i >= pos;i--){
arr[i+1] = arr[i];
}
this.arr[pos] = data;
this.usesize++;
}
// 检查下标的合法性
private void checkPos(int pos) throws PosIllegality{
if(pos < 0 || pos > usesize){
System.out.println("下标不合法");
// 抛异常
throw new PosIllegality("下标不合法异常");
}
}
// 检查容量够不够函数
private void checkCapacity(){
if(isFull()){
// 扩容
arr = Arrays.copyOf(arr,arr.length*2);
}
}
// 判定是否包含某个元素
@Override
public boolean contains(int toFind) {
if(isEmpty()) return false;
for(int i = 0;i < usesize;i++){
// 如果是查找引用数据类型,一定要重写 比较方法
if(toFind == arr[i]) return true;
}
return false;
}
public boolean isEmpty(){
if(usesize == 0) return true;
else return false;
}
// 查找某个元素对应的位置
@Override
public int indexOf(int toFind) {
if(isEmpty()) return -1;
for(int i = 0;i < usesize;i++){
// 如果是查找引用数据类型,一定要重写 比较方法
if(toFind == arr[i]) return i;
}
return -1;
}
@Override
public int get(int pos) throws MyArrayEmpty {
checkPosOnGet(pos);
if(isEmpty()){
// 抛异常
throw new MyArrayEmpty("获取指定下标元素时,顺序表为空");
}
return arr[pos];
}
private void checkPosOnGet(int pos) throws PosIllegality{
if(pos < 0 || pos >= usesize){
System.out.println("下标不合法");
// 抛异常
throw new PosIllegality("下标不合法异常");
}
}
private void checkPosOnSet(int pos) throws PosIllegality{
if(pos < 0 || pos >= usesize){
System.out.println("下标不合法");
// 抛异常
throw new PosIllegality("下标不合法异常");
}
}
@Override
public void set(int pos, int value) {
checkPosOnSet(pos);
arr[pos] = value;
}
// 删除第一次出现的元素
@Override
public void remove(int toRemove) {
int k = indexOf(toRemove);
if(k == -1){
System.out.println("没有找到这个数");
return;
}
for(int i = k;i < this.usesize - 1;i++){
arr[i] = arr[i+1];
}
this.usesize--;
}
@Override
public int size() {
return this.usesize;
}
// 清空顺序表
@Override
public void clear() {
this.usesize = 0;
}
}
// MyArrayEmpty的异常的写法
package myList;
public class MyArrayEmpty extends RuntimeException {
public MyArrayEmpty(String msg){
super(msg);
}
}
// PosIllegality异常的写法
package myList;
public class PosIllegality extends RuntimeException{
public PosIllegality(String msg){
super(msg);
}
}
clear
- clear清空数组，如果类型是基本数据类型，可以把有效的长度置为0，如果为引用数据类型该怎么办呢？
垃圾回收的机制：当这个对象没有被引用的时候可以被回收
引用类型可以用for循环一个一个置空，然后有效元素个数置为0
ArrayList的使用
import java.util.ArrayList;
public class test {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(0,99);
for(int i = 0;i < list.size();i++){
System.out.print(list.get(i) + " ");
}
System.out.println();
System.out.println(list);
}
}
构造方法
- 带一个参数的构造方法（传入要扩容的空间大小）
- 不带参数的构造方法（在add的时候扩容10个空间大小）
3. 扩容：第一次add会分配大小为10的内存
对于ArrayList来说是1.5倍扩容，如果超过1.5倍大小，则按照用户所需大小进行扩容
使用copyOf进行扩容
底层：
- 用另一个对象构造新的对象，Collection是接口
1.ArrayList实现了Collection接口，那么Collection接口可以引用ArrayList的对象
2.list泛型类的类型是？（通配符），它的上界要是list2的子类或者其本身，list传给c
3. 只要实现了这个接口都可以传递给Collection
使用：
ArrayList<Integer> list = new ArrayList<>();
ArrayList<Number> list1 = new ArrayList<>(list);
// list必须是Number的子类或者是它本身(Integer)
函数使用
// 1. addAll
ArrayList<Number> list12 = new ArrayList<>();
// list12.addAll(list);
// 将list对象中的内容都复制入list12对象中
System.out.println(list12);
// 2. remove
// 删除下标2对应的内容
list12.remove(2);
// 删除3这个对象
list12.remove(new Integer(3));
// 3. get和set
System.out.println(list12.get(1));
list12.set(1,2);
// 4. clear
// list12.clear();
// 5. boolean contains(Object o) 判断o是否在线性表中
// 6. int indexOf(Object o) 返回出现o所在的第一个下标
// 7. int lastIndexOf(Object o) 返回最后一个o的下标 */
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
System.out.println(list);
// subList不会创建新的对象，只是让list1指向原对象的1下标位置
List<Integer> list1 = list.subList(1,3);
System.out.println(list1);// 2 3
list1.set(0,99);
System.out.println(list1);// 99 3
System.out.println(list);// 1 99 3 4 5
遍历
System.out.println(list);
for(Integer x : list){
System.out.print(x);
}
System.out.println();
// 迭代器
Iterator<Integer> it = list.iterator();
while(it.hasNext()){
System.out.print(it.next() + " ");
// it.next()自动向下执行
}
System.out.println();
应用
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> list = new ArrayList<>();
List<Integer> list1 = new ArrayList<>();
list1.add(1);
list.add(list1);
for(int i = 1;i < numRows;i++){
// 1.先插入第一个数字1
List<Integer> rowList = new ArrayList<>();
rowList.add(1);
// 拿到前一行的数组
List<Integer> prevList = list.get(i-1);
// 2.再插入中间数据
for(int j = 1;j < i;j++){
int val = prevList.get(j) + prevList.get(j-1);
rowList.add(val);
}
// 3. 插入最后一个数字1
rowList.add(1);
// 4. 在插入到二维数组中
list.add(rowList);
}
return list;
}
}