开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 认识List -> 正文阅读

[数据结构与算法]认识List

对List接口的认识

首先说一下：上一篇文章中编辑泛型顺序表时，构造方法写的是：

public MyArrayList() {
     this.elem = (E[])new Object[10];//顺序表容量初始化为10，作E[]的强转是为了匹配E[]的字段：elem
}

有一个问题就是：为什么不写成：

this.elem = new E[10];

因为：java中不可创建泛型数组，这是根据《Effective Java》第五章中说道的：

使用泛型的作用是使得程序在编译期可以检查出与类型相关的错误，但是如果使用了泛型数组，这种能力就会受到破坏。

其次说一下：关于Object[]强制类型转换的思考：

估计很多人人认为Object[]是其他数组类型的父类，其实不然，两者属于同级的关系。根据以上错误认识，可能会有如下代码：

public class TestDemo {
    public static void main(String[] args) {
        Object[] arr=(Object[])new String[10];
        arr[0]=10;
        arr[1]=20;
        System.out.println(arr[0]);
    }
//抛出异常 java.lang.ArrayStoreException: java.lang.Integer

用C的理解方式：String[10]是一个每个元素都是String类型的数组，假设这个数组的数组指针类型是str1*,而Object[]的数组指针类型是：str2 *，上述代码的强制类型转换，只是实现了数组指针类型的整体转换（之所以可以转换，是因为它俩属于同级别的关系），但是String[]中存放的元素是String,区别于Object,所以数组中只能放String的数据。而不是我们所期望的什么类型的数据都可以放。

总之，尽量不要使用整个数组类型的转换

什么是包装类🛰

java中的数据类型int，double等不是对象，无法通过向上转型获取到Object提供的方法，而像String却可以，只因为String是一个对象而不是一个类型。基本数据类型由于这样的特性，导致无法参与转型，泛型，反射等过程。为了弥补这个缺陷，java提供了包装类。

可以简单理解为基本数据类型的plus版本，包装类可以提供很多便捷的方法供我们使用，注意只有基本数据类型才有对应的包装类。且除了int的包装类为Integer,char的包装类是：Character，其余基本数据类型都是首字母大写。

包装类有什么用🗂

举例：将字符串变成整数：

public class TestDemo {
    public static void main(String[] args) {
        String ret="123";//这里不能写成“hehe"这种形式的字符串！必须是数字组成的字符串
        int a=Integer.valueOf(ret);
        System.out.println(a+1);//打印124
    }
}

从上述例子可以看出：如果像C那样去实现类型的转换，我们得面向过程去编程，而java中包装类的出现，让我们得以直接使用已经编写好的一些功能。即面向对象编程。

装包、拆包👊

用基本数据类型的plus版本去接收一个基本数据类型的数据，这就叫装包。反过来就是拆包。

如：

public class TestDemo {
    public static void main(String[] args) {
        Integer a=10;//装包（隐式）
        int b=a;//拆包（隐式）
        System.out.println("a="+a+",b="+b);
    }
}//打印：a=10,b=10

我们可以通过javap -c进行反汇编查看，底层到底怎么实现装包和拆包的。可以发现：

装包	拆包
Integer.valueOf()	Integer.intValue

所以显示的去装包和拆包就是：

public class TestDemo {
    public static void main(String[] args) {
        Integer a=Integer.valueOf(10);//装
        int b=a.intValue();//拆
        System.out.println("a="+a+",b="+b);
    }
}

注意:装完包，比如10装包了，10就是一个对象，被a引用。

所以类似于字符串对象的比较（前面的博文介绍过，还有很多变化的形式）：

一个问题：

public class TestDemo {
    public static void main(String[] args) {
        Integer a=10;
        Integer b=10;
        System.out.println(a==b);
    }
}//打印true

public class TestDemo {
    public static void main(String[] args) {
        Integer a=200;
        Integer b=200;
        System.out.println(a==b);
    }
}//打印false

明明装包的基本数据一样大，发现一个true一个false哎！

究其本质：针对装包:Integer.valueOf():

public static Integer valueOf(int i) {
     if (i >= IntegerCache.low && i <= IntegerCache.high)
         return IntegerCache.cache[i + (-IntegerCache.low)];
     return new Integer(i);
}

可以看出，装包的时候，如果不是new一个对象，只要i（要存的基本数据的值）介于一定的范围，底层就直接在默认的缓存数组当中直接拿了。其范围（值）：-128_{127，对应的下标：0}256。new一个对象的话，就和String的情况类似，如：

public class TestDemo {
    public static void main(String[] args) {
        Integer a=10;//存的值在-128-127之间
        Integer b=new Integer(10);//存的值在-128-127之间
        System.out.println(a==b);
    }
}//打印false，因为对象不同

认识ArrayList??

在这里插入图片描述

针对ArrayList的构造方法：

1、ArrayList(int)//给定初始容量的构造
2、ArrayList()//无参构造
3、ArrayList(Collection<?extends E>)//已现有顺序表进行构造

2.对ArrayList的遍历：

public class TestDemo {
    public static void main(String[] args) {
        ArrayList<String> arrayList=new ArrayList<>();
        arrayList.add("hehe");
        arrayList.add("xixi");
        arrayList.add("haha");
        //遍历1：直接打印
        System.out.println(arrayList);
        System.out.println("===========");//分隔一下
        //遍历2：利用for循环,size()返回顺序表存放元素的个数，get（i）获取到顺序表下标为i的元素
        for(int i=0;i<arrayList.size();i++){
            System.out.print(arrayList.get(i)+" ");
        }
        System.out.println();
        System.out.println("===========");//分隔一下
        //遍历3：利用for-each循环
        for (String ret:arrayList) {
            System.out.print(ret+" ");
        }
        System.out.println();
        System.out.println("===========");//分隔一下
        //遍历4：使用迭代器
        Iterator<String> it=arrayList.iterator();
        while(it.hasNext()){
            String ret=it.next();
            System.out.print(ret+" ");
        }
        System.out.println();
        System.out.println("===========");//分隔一下
    }
    public static void main1(String[] args) {
        ArrayList<String> arrayList=new ArrayList<>();
        ArrayList<String> arrayList1=new ArrayList<>(10);
        //发生向上转型时的构造
        List<String> arraylist2=new ArrayList<>();
        List<String> arraylist3=new ArrayList<>(10);
        //已现有
    }
}

针对迭代器：List有其特有的迭代器（一个接口）：ListIterator,此迭代器实现了Iterator接口，所以说ListIterator的功能更加丰富。举例：ListIterator有add(),remove()等方法：

public class TestDemo {
    public static void main(String[] args) {
        ArrayList<String> arrayList=new ArrayList<>();
        arrayList.add("hehe");
        arrayList.add("xixi");
        arrayList.add("haha");
        ListIterator<String> it=arrayList.listIterator();
        while(it.hasNext()){
            String ret=it.next();//迭代器it每次拿到一个元素，就会指向该位置
            if(ret.equals("hehe")){
                it.add("大威天龙");//这里是尾插到It当前所指向的元素后面，此处即：hehe后面
            }
        }
        System.out.println(arrayList);
    }
}//打印：[hehe, 大威天龙, xixi, haha]

注意：如果将it.add()改成arrayList.add()；编译可以通过，运行时抛出异常了！java.util.ConcurrentModificationException

首先对此：arrayList.add()，如果执行成功，其实是在整个顺序表的后面尾插一个元素，这里不成功的原因是：ArrayList不是线程安全的（单线程），如果将Arraylist改成CopyOnWriteArrayList就发现不会把报错了！

public class TestDemo {
    public static void main(String[] args) {
        CopyOnWriteArrayList<String> arrayList=new CopyOnWriteArrayList<>();
        arrayList.add("hehe");
        arrayList.add("xixi");
        arrayList.add("haha");
        ListIterator<String> it=arrayList.listIterator();
        while(it.hasNext()){
            String ret=it.next();//迭代器it每次拿到一个元素，就会指向该位置
            if(ret.equals("hehe")){
                arrayList.add("大威天龙");//这里是尾插到It当前所指向的元素后面，此处即：hehe后面
            }
        }
        System.out.println(arrayList);
    }
}
//打印：[hehe, xixi, haha, 大威天龙]

ArrayList的常见操作：🎃

方法	解释
boolean add(E e)	尾插e
void add(int index,E e)	在下标为index的位置插入一个e
boolean addAll(Collection<?extends E> c)	尾插一个已有的顺序表，注意是顺序表
E remove(int index)	获取到index位置的元素，且顺序表该位置的元素被删除
E get(int index)	获取到index位置的元素，且顺序表该位置的元素不被删除
E set(int index,E e)	在顺序表的index位置设置元素e（不是插入）
void clear()	清空顺序表
boolean contains(Object o)	查看顺序表中是否包含o
int indexOf(Object o)	返回第一个o的下标
int lastIndexOf(Object o)	从后往前，返回第一个o的下标，下标还是从前往后数的
List sublist(int from,int to)	左闭右开的区截取原List的元素生成一个新的顺序表

注意：最后一个功能截取出来的元素所组成的新的顺序表，如果我们对这个新的顺序表作一些修改，那么原来的顺序表也会被作同样的修改。并且返回的必须是一个List如：

public class TestDemo {
    public static void main(String[] args) {
        ArrayList<String> arrayList=new ArrayList<>();
        arrayList.add("hehe");
        arrayList.add("xixi");
        arrayList.add("haha");
        arrayList.add("gaga");
        List<String> ret=arrayList.subList(1,3);
        ret.set(0,"大威天龙");
        System.out.println(arrayList);
        System.out.println(ret);
    }
}//打印：
//[hehe, 大威天龙, haha, gaga]
//[大威天龙, haha]

ArrayList的扩容机制??

从源码的角度，剖析一下，源码是怎么实现扩容的

ArrayList<String> arrayList=new ArrayList<>();//这里调用无参构造，去查看不给初始容量的化，是这么一种情况

public ArrayList() {
     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}//DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};

我们发现，无参构造调用的构造方法给我们的结果是，将底层的数组初始化为一个空数组，接下来我们往这个数组里去放东西，那就可以进一步的观察ArrayList的扩容机制了：

arrayList.add("hehe");

进入add():

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  //理解为确保至少还有一个空位给我们放元素
    elementData[size++] = e;//上一步确保能放的下之后，我们就尾插我们要放的元素即可
    return true;
}//源码

怎么确保至少还有一个位置：(进入ensureCapacityInternal（）)：

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);//默认值是10
    }
    return minCapacity;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

可以看出：确保最小容量的时候，源码是先进行一个容量的计算:calculateCapacity(elementData, minCapacity)

该函数实现的功能是：如果是第一次放东西，那就初始化一个容量（较大值），反之返回minCapacity，返回值用作ensureExplicitCapacity（）的参数，这个函数可以明确是否扩容，当我们所需要的最小容量已经超过当前数组的长度后，进行grow(扩容),接下来看看具体怎么扩容：

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
}

可以看出，根据所需要的最小容量，想要扩充的目标容量最原始的是1.5倍扩容。

至此我们可以自己实现一个与源码相同的顺序表（当然可以先实现只放int类型数据的）。

几道与List相关的例题🔐

将学生放入List当中，每个学生的属性是：名字（String），班级（String）,成绩（score），考试结束之后，每个学生都获得各自的成绩，请遍历List集合，将班级信息打印出来：(本题的目的，是想让大家知道，使用泛型时，不一定非得指定成内置的包装类，也可以是指定成我们自己定义的类，如下面代码中的Student)

class Student{
    public String name;
    public String classes;
    public double score;

    public Student(String name, String classes, double score) {
        this.name = name;
        this.classes = classes;
        this.score = score;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", classes='" + classes + '\'' +
                ", score=" + score +
                '}';
    }
}
public class Message {
    public static void main(String[] args) {
        ArrayList<Student> arrayList=new ArrayList<>();
        arrayList.add(new Student("张三","102-1",89.9));
        arrayList.add(new Student("李四","102-2",79.9));
        arrayList.add(new Student("王五","102-3",99.9));
        System.out.println(arrayList);
    }
}//打印：
//[Student{name='张三', classes='102-1', score=89.9}, Student{name='李四', classes='102-2', score=79.9}, Student{name='王五', classes='102-3', score=99.9}]

删除第一个字符串当中出现的第二个字符串中的字符

如：String str1=“welcome to my world”;

? String str2=“come”;

? 输出结果应为：wl t y wrld

public class TestDemo {
    public static void main(String[] args) {
        ArrayList<Character> arrayList=new ArrayList<>();
        String str1="welcome to my world";
        String str2="come";
        int len=str1.length();
        for (int i = 0; i <len ; i++) {
            arrayList.add(str1.charAt(i));
        }
        ListIterator<Character> it=arrayList.listIterator();
        while(it.hasNext()){
            char ret=it.next();
            if(str2.contains(ret+"")){
                it.remove();
            }
        }
        //System.out.println(arrayList);//[w, l,  , t,  , y,  , w, r, l, d]
        //因为要输出一个字符串
        String ans="";
        for(int i=0;i<arrayList.size();i++){
            ans=ans+arrayList.get(i);
        }
        System.out.println(ans);
    }
}

有一个List当中存放的是整型的数据，要求使用Collections.sort对List进行排

public class TestDemo {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList=new ArrayList<>();
        arrayList.add(10);
        arrayList.add(20);
        arrayList.add(30);
        arrayList.add(15);
        arrayList.add(29);
        Collections.sort(arrayList);
        System.out.println(arrayList);
    }
}//打印：[10, 15, 20, 29, 30],查看Collections的sort方法可以发现，本质还是调用了List的sort()

使用顺序表制作一副扑克牌🐤

买牌→洗牌→三个人斗地主(揭牌)

class Card{
    public String suit;//花色
    public int rank;//数字

    public Card(String suit, int rank) {
        this.suit = suit;
        this.rank = rank;
    }

    @Override
    public String toString() {
        return  suit + ':' +
                 + rank ;
    }
}
public class PlayCard {
    private static final String[] suits={"?","?","?","?"};//花色数组
    //买牌
    private static List<Card> buyCrad(){
        ArrayList<Card> cards=new ArrayList<>();
        for (int i = 0; i <suits.length ; i++) {
            for (int j = 1; j <= 13; j++) {
                cards.add(new Card(suits[i],j));
            }
        }
        return cards;
    }
    private static void shuffle(List<Card> cards){
        int size=cards.size();
        Random random=new Random();//生成随机起点
        for(int i=size-1;i>0;i--){
            Card tmp=cards.get(i);//最后一张牌
            //将最后一张牌与前面的某一张牌进行交换
            int rand=random.nextInt(i);//[0,i)随机取一个下标
            Card tmp1=cards.get(rand);
            cards.set(rand,tmp);
            cards.set(i,tmp1);
        }
    }
    public static void main(String[] args) {
        List<Card> cards=buyCrad();//买牌
        //System.out.println(cards);此语句仅作检查买来的牌有没有毛病
        shuffle(cards);//洗牌
        //揭牌，用集合去写的话，那就是一个二维数组，假如三个人在打牌
        //那行数就是3，每个人的牌都一样多5张，一圈一圈去拿牌，最后展示每个人的牌，比如在炸金花
        ArrayList<List<Card>> hand=new ArrayList<>();
        List<Card> hand1=new ArrayList<>();
        List<Card> hand2=new ArrayList<>();
        List<Card> hand3=new ArrayList<>();
        hand.add(hand1);
        hand.add(hand2);
        hand.add(hand3);


        for(int i=0;i<5;i++){
            for (int j = 0; j <3 ; j++) {
                Card card=cards.remove(0);//每次都是揭最上面的牌
                hand.get(j).add(card);
            }
        }
        //看一下每个人的牌
        System.out.println("第一个人的牌："+hand.get(0));
        System.out.println("第二个人的牌："+hand.get(1));
        System.out.println("第三个人的牌："+hand.get(2));

    }
}
//打印：
第一个人的牌：[?:3, ?:9, ?:9, ?:4, ?:13]
第二个人的牌：[?:7, ?:2, ?:12, ?:1, ?:11]
第三个人的牌：[?:1, ?:13, ?:6, ?:4, ?:2]