1.线性表(linear list) 是n个具有相同特性的数据元素的有序数列.线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表,链表,栈,队列...
线性表在逻辑上是线性结构的,也就是说是一条连续的直线.但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式储存
2.顺序表
顺序表是用一段物理地址连续的储存单元依次存储数据的线性结构,一般情况下采用的数组储存.在数组上完成增删改查
2.1接口的实现
public class SeqList {private int[] array;private int size;//默认构造方法public SeqList(){}//把顺序表的底层容量设为initcapacitySeqList(int initcapacity){}//新增加元素,默认在数组最后新增元素public void add(int data){}//在指定位置(pos) 位置新增元素public void add(int pos,int data){}//判断是否包含某个元素,如果包含这个元素就返回true,否则就返回falsepublic boolean contains(int toFind){return true;}//查找某个元素对应的位置,如果找到对应元素,就返回其元素的下标,如果没有找到元素,就返回-1;public int indexOf(int toFind){return -1;}//获取pos的位置的元素public int get(int pos){return -1;}//给pos的位置的元素设为 valuepublic void set(int pos,int value){}//删除第一次出现的关键字keypublic void remove(int toRemove){}//获取顺序表的长度public int size(){return 0;}//清空顺序表public void clear(){}//打印顺序表public void display(){}
}
ArrayList简介
在集合框架中,ArrayList是一个普通的类,实现了List接口
说明:
ArrayList是以泛型方式实现的,使用的时候必须先实例化.
ArrayList实现了RandomAccess接口,表明ArraList支持随机访问
ArraList实现了Cloneable接口,表明ArrayList是可以clone的
ArrayList实现了Serialiable接口,表明ArrayList是支持序列化的
ArrayList底层是一段连续的空间,并且可以动态扩容,是一个动态类型的顺序表
4.ArrayList的使用
4.1ArrayList的构造
import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {//ArrayList 创建,推荐写法//构造一个空的列表List<Integer> list1 = new ArrayList<>();//构造一个具有10个容量的列表List<Integer> list2 = new ArrayList<>(10);list2.add(1);list2.add(2);list2.add(3);//类型不匹配发生报错
// list2.add("hello");//如果我们要输入类似 list2.add("hello")这样的类型的内容,是不允许的.//我们在前面已经限定了泛型的类型是 Integer,类型不匹配就会报错.//我们可以通过创建 String 类型的 ArrayList 来存储 String 类型的数据List<String> list3 = new ArrayList<>();list3.add("hello");list3.add("world");//打印输出的内容是以数组的形式打印出来的System.out.println(list2);//我们在创建泛型的时候应该去避免出现,不指定存放元素类型这样的写法.//这样会导致顺序表中存放的内容的数据类型不明确,容易出现错误}
}4.2ArrayList常见的操作方法
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.List;
import java.util.Scanner;public class Main2 {public static void main(String[] args) {//创建了一个存放 String 类型的 ArrayListList<String> list = new ArrayList<String>();//我们向 ArrayList 中添加元素list.add("JavaSE");list.add("JavaWeb");list.add("JavaEE");list.add("JVM");list.add("测试");//先打印一下 ArrayList 查看一下里面的元素System.out.println(list);//我们下面使用不同的方法//获取 list 中的有效元素的个数System.out.println(list.size());//获取和设置 index 位置上的元素,注意的是 index 必须要介于[0,size)之间//简单的获取的 index 位置上的元素System.out.println(list.get(1));//我们可以加上一些判断,来确保发生数组越界的情况发生//通过try{} 来抛出异常
// Scanner scanner = new Scanner(System.in);
// System.out.println("请输入要获取的 index 位置:");
// int index = scanner.nextInt();
// try{
// if(index < 0 || index > list.size() - 1){
// //通过 throw 来抛出异常
// throw new InputMismatchException();
// }
// System.out.println(list.get(index));
// }//通过 catch{}来捕获异常并处理异常
// catch (InputMismatchException e){
// System.out.println("输入的 index 位置,发生数组越界的情况发生");
// }//我们通过 set() 方法来修改 index 位置上的元素list.set(1,"Java数据结构");//修改完毕后我们再次进行一次打印System.out.println(list);//删除自定元素,如果我们找到就删除,把该元素之后的元素同一向前搬移一个单位list.remove("JVM");System.out.println(list);//删除 list 中的 index 位置上的元素,注意 index 不要超过 list 中的有效元素的个数,否则会抛出下标异常//这里是删除了最后一个元素.list.remove(list.size() - 1);System.out.println(list);//检测 list 中是否包含某一个元素,如果存在返回 true,否则返回 falseif(list.contains("测试")){list.add("测试");}//查找指定元素第一次出现的位置:indexOf() 从前向后找,lastIndexOf() 从后向前找list.add("JavaSE");System.out.println(list.indexOf("JavaSE"));System.out.println(list.lastIndexOf("JavaSE"));//使用 list 中[0,4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组
// List<String> ret = new list.subList(0,4);//清空数组list.clear();System.out.println(list);System.out.println(list.size());}
}
4.3ArrayList的遍历
ArrayList可以使用三种方式进行遍历: for循环 + 下标,foreach,使用,迭代器
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;public class Main3 {public static void main(String[] args) {List<Integer> list = new ArrayList<Integer>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);System.out.println(list);//使用 for 循环来遍历for (int i = 0; i < list.size(); i++){System.out.println(list.get(i));}//借助 foreach 遍历for (Integer i : list){System.out.println(i + "");}System.out.println();//使用迭代器Iterator<Integer> it = list.listIterator();while(it.hasNext()){System.out.println(it.next() + " ");}}
}
注意的是:
ArrayList最常用的遍历的方式是:for循环+下标 以及foreach
2.迭代器是设计模式的一种方式,在后面才会使用
4.4ArrayList的扩容机制
ArrayList是一个动态类型的顺序表,即:在插入元素的过程中会自动扩容