List线性表
目录
一、什么是List？
二、List提供的方法(常用)
三、ArrayList的使用
一、什么是List？
在集合框架中,List是一个接口,继承自Collection接口
List就是一个线性表,是n个具有相同类型元素的有限序列,可以进行增删改查等操作
二、List提供的方法(常用)
List是一个接口,不能直接用来实例化,要使用,需要去实例化List的实现类
ArrayList和LinkedList实现了List接口
线性表:是n个具有相同特性的数据元素的有限序列(顺序表,链表,栈,队列...),在物理上通常以数组和链式结构的形式存储;(逻辑上是线性结构,物理上并不一定连续)
顺序表:用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般采用数组存储
顺序表接口的实现
import java.util.ArrayList;
import java.util.Arrays;
public class MyArrayList {
//数组
private int[] elem;
private int usedSize;//代表当前顺序表当中的有效数据个数
private static final int DEFAULT_SIZE=10;
public MyArrayList(){
this.elem=new int[DEFAULT_SIZE];
}
//指定容量
public MyArrayList(int initCapacity){
this.elem=new int[initCapacity];
}
// 新增元素,默认在数组最后新增
public void add(int data) {
if(isFull()){
//如果数组满了要扩容
this.elem= Arrays.copyOf(this.elem,2*this.elem.length);
}
this.elem[this.usedSize]=data;
usedSize++;
}
//判断数组是否填满
public boolean isFull(){
if(this.usedSize==this.elem.length){
return true;
}else {
return false;
}
}
// 在 pos 位置新增元素
public void add(int pos, int data) {
if(pos<0||pos>this.usedSize){
System.out.println("位置不合法");
return;
}
if (isFull()){
this.elem= Arrays.copyOf(this.elem,2*this.elem.length);
}
for (int i =this.usedSize-1; i >=pos ; i--) {
this.elem[i+1]=this.elem[i];
}
this.elem[pos]=data;
this.usedSize++;
}
// 判定是否包含某个元素
public boolean contains(int toFind) {
for (int i = 0; i <this.usedSize ; i++) {
//引用类型比较时用equals或者compareTo
if(this.elem[i]==toFind){
return true;
}
}
return false;
}
// 查找某个元素对应的位置
public int indexOf(int toFind) {
for (int i = 0; i <this.usedSize ; i++) {
if(this.elem[i]==toFind){
return i;
}
}
return -1;
}
// 获取 pos 位置的元素
public int get(int pos) {
if(pos<0||pos>=this.usedSize){
System.out.println("位置不合法");
return -1;
}
return this.elem[pos];
}
// 给 pos 位置的元素设为 value
public void set(int pos, int value) {
if(pos<0||pos>=this.usedSize){
System.out.println("位置不合法");
return ;
}
this.elem[pos]=value;
}
//删除第一次出现的关键字key
public void remove(int toRemove) {
int index=indexOf(toRemove);
if(index==-1){
System.out.println("没有这个元素");
return;
}
for (int i = index; i <this.usedSize-1 ; i++) {
this.elem[i]=this.elem[i+1];
}
this.usedSize--;
}
// 获取顺序表长度
public int size() {
return this.usedSize;
}
// 清空顺序表
public void clear() {
this.usedSize=0;
//如果为引用类型,清空时应给每个元素设为null
// for (int i = 0; i <this.usedSize ; i++) {
// this.elem[i]=null;
// }
}
// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
public void display() {
for (int i = 0; i <usedSize ; i++) {
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
}
class Test{
public static void main(String[] args) {
MyArrayList myArrayList=new MyArrayList();
myArrayList.add(1);
myArrayList.add(2);
myArrayList.add(3);
myArrayList.add(4);
myArrayList.add(5);
myArrayList.display();
System.out.println("============");
//在2位置新增9
myArrayList.add(2,9);
myArrayList.display();
System.out.println("=========");
//return虽然返回值但是要打印!!!
//判断是否含9
System.out.println(myArrayList.contains(9));
//查找1对应的位置
System.out.println(myArrayList.indexOf(1));
//获取1位置的元素
System.out.println( myArrayList.get(1));
//给5位置元素设置为999
myArrayList.set(5,999);
myArrayList.display();
//删除99
myArrayList.remove(99);
//获取数组长度
System.out.println(myArrayList.size());
//清空数组
myArrayList.clear();
System.out.println(myArrayList.size());
}
} 
三、ArrayList的使用
ArrayList是以泛型方式实现的
1)ArrayList的构造
public static void main(String[] args) {
//实现的方法比较多 ArrayList
ArrayList<Integer>list=new ArrayList<>();
ArrayList<Integer>list2=new ArrayList<>(10);
//向上转型1
//用接口引用一个具体的实现类List实现的方法比较少
List<Integer>list3=new ArrayList<>();
List<Integer>list4=new LinkedList<>();
list4.add(7);
list4.add(8);
list4.add(9);
List<Integer>list5=new ArrayList<>(list4);
list2.add(1);
list5.add(10);
//也是遍历顺序表的一种方式
System.out.println(list5);
} 
2)ArrayList常见操作
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,100);
list.add(4);
list.add(5);
//返回1下标的值
//System.out.println(list.get(1));
System.out.println(list);
//截取一段list左闭右开
List<Integer>list2=list.subList(1,3);
System.out.println(list2);
System.out.println("=======");
//删除0位置的下标
// list.remove(0);
// System.out.println(list);
// System.out.println("=======");
// //删除元素3的值
// list.remove(new Integer(3));
// System.out.println(list);
//把截取出来的list2[1,3],0下标改成99
list2.set(0,99);
System.out.println(list);
System.out.println(list2);
}
3)遍历
public static void main(String[] args) {
ArrayList<Integer>list=new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
//for遍历
for (int i = 0; i <list.size() ; i++) {
System.out.print(list.get(i)+" ");
}
System.out.println();
//foreach循环
for (Integer x:list){
System.out.print(x+" ");
}
System.out.println();
//迭代器iterator
Iterator<Integer>it=list.iterator();
while (it.hasNext()){
System.out.print(it.next()+" ");
}
System.out.println();
ListIterator<Integer>listIterator=list.listIterator();
while (listIterator.hasNext()){
System.out.print(listIterator.next()+" ");
}
System.out.println();
//从后往前遍历
ListIterator<Integer>listIterator2=list.listIterator(list.size());
while (listIterator.hasPrevious()){
System.out.print(listIterator.previous()+" ");
}
System.out.println();
}
4)ArrayList优缺点
优:可以通过下标进行随机访问
缺:添加/删除元素效率低(要移动元素),扩容的时候存在浪费空间情况
顺序表适合静态的数据查找和更新,不适合用来插入和删除数据(随用随分配链表来做)