List线性表

2024-10-23 07:14:23

一、什么是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优缺点

优:可以通过下标进行随机访问

缺:添加/删除元素效率低(要移动元素),扩容的时候存在浪费空间情况

顺序表适合静态的数据查找和更新,不适合用来插入和删除数据(随用随分配链表来做)

码农公寓

一、什么是List？

二、List提供的方法(常用)

三、ArrayList的使用

相关文章