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或者compareToif(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 位置的元素设为 valuepublic void set(int pos, int value) {if(pos<0||pos>=this.usedSize){System.out.println("位置不合法");return ;}this.elem[pos]=value;}//删除第一次出现的关键字keypublic 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位置新增9myArrayList.add(2,9);myArrayList.display();System.out.println("=========");//return虽然返回值但是要打印!!!//判断是否含9System.out.println(myArrayList.contains(9));//查找1对应的位置System.out.println(myArrayList.indexOf(1));//获取1位置的元素System.out.println( myArrayList.get(1));//给5位置元素设置为999myArrayList.set(5,999);myArrayList.display();//删除99myArrayList.remove(99);//获取数组长度System.out.println(myArrayList.size());//清空数组myArrayList.clear();System.out.println(myArrayList.size());}
}

三、ArrayList的使用

ArrayList是以泛型方式实现的

1)ArrayList的构造

 public static void main(String[] args) {//实现的方法比较多 ArrayListArrayList<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下标改成99list2.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();//迭代器iteratorIterator<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();}