2023面试高手

这个屌丝很懒，什么也没留下！

热门标签

【JAVA学习笔记】53 - 集合-List类及其子类Collection、ArrayList、LinkedList类、Vector类

作者：2023面试高手 | 2024-02-12 08:55:44

踩

项目代码

https://github.com/yinhai1114/Java_Learning_Code/tree/main/IDEA_Chapter14/src/com/yinhai/collection_

https://github.com/yinhai1114/Java_Learning_Code/tree/main/IDEA_Chapter14/src/com/yinhai/list_

四、ArrayList 的底层结构和源码分析（建议多看看）

1.ArrayList的细节

2.ArrayList的源码分析（重点难点）

五、Vector类的底层结构和源码分析（建议多看看）

1.Vector的基本介绍

2.Vector和ArrayList的比较

编辑

六、LinkedList的底层结构和源码分析

4.ArrayList和inkedList的比较

如何选择ArrayList和LinkedList:

集合

一、引入

前面我们保存多个数据使用的是数组，那么数组有不足的地方，我们分析一下。

数组

1)长度开始时必须指定，而且一旦指定，不能更改

2)保存的必须为同类型的元素

3)使用数组进行增加元素的示意代码-比较麻烦

写出Person数组扩容示意代码。

                Person[] pers = new Person[1];
                per[0]=new Person();

                Person[] pers2 = new Person[pers.length+ 1]; //新创建数组
                for(){} //拷贝pers数组的元素到pers2
                pers2[pers2.length-1]=new Person();//添加新的对象

集合

1)可以动态保存任意多个对象，使用比较方便!

2)提供了一系列方便的操作对象的方法: add、remove、set、 get等

3)使用集合添加，删除新元素的示意代码-简洁了

二、集合的框架体系

集合主要分两组单列和双列

单列集合

两个重要的两个子接口List Set

双列集合

属于双列集合，存放K-V的数据

Collection类

一、Collection类接口和常用方法

Collection接口实现类的特点

public interface Collection<E> extends iterable <E>

1) collection实现子类可以存放多个元素，每个元素可以是Object

2)有些Collection的实现类，可以存放重复的元素，有些不可以

3)有些Collection的实现类，有些是有序的(List)，有些不是有序(Set)

4) Collection接口没有直接的实现子类，是通过它的子接口Set和List来实现的


public class CollectionMethod {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        List list = new ArrayList();
        //add:添加单个元素
        list.add("jack");
        list.add(10);//list.add(new Integer(10))对象
        list.add(true);
        System.out.println("list=" + list);
 
        //remove:删除指定元素
        //list.remove(0);//删除第一个元素
        list.remove(true);//指定删除某个元素
        System.out.println("list=" + list);
 
        //contains:查找元素是否存在
        System.out.println(list.contains("jack"));//T
        //size:获取元素个数
        System.out.println(list.size());//2
 
        //isEmpty:判断是否为空
        System.out.println(list.isEmpty());//F
 
        //clear:清空
        list.clear();
        System.out.println("list=" + list);
 
        //addAll:添加多个元素
        ArrayList list2 = new ArrayList();
        list2.add("红楼梦");
        list2.add("三国演义");
        list.addAll(list2);
        System.out.println("list=" + list);
        
        //containsAll:查找多个元素是否都存在
        System.out.println(list.containsAll(list2));//T
        
        //removeAll：删除多个元素
        list.add("聊斋");
        list.removeAll(list2);
        System.out.println("list=" + list);//[聊斋]
    }
}

二、Iterator迭代器

Collection接口遍历元素方式1-使用Iterator(迭代器)

1.基本介绍

1) Iterator对象称为迭代器，主要用于遍历Collection集合中的元素。

2)所有实现了Collection接的集合类都有个iterator(方法，用以返回一个实现了Iterator接口的对象，即可以返回一个迭代器。

3) Iterator的结构

4) Iterator仅用于遍历集合，Iterator 本身并不存放对象。

2.迭代器的执行原理

Iterator iterator = coll.iterator(): //得到一个集合的迭代器

//hasNext():判断是否还有下一个元素
while(iterator.hasNext()){

//next(:@下移②将下移以后集合位置上的元素返回
System.out.println(iterator.next());


public class CollectionIterator {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
 
        Collection col = new ArrayList();
 
        col.add(new Book("三国演义", "罗贯中", 10.1));
        col.add(new Book("小李飞刀", "古龙", 5.1));
        col.add(new Book("红楼梦", "曹雪芹", 34.6));
        System.out.println("col=" + col);
        //希望遍历该集合
        //1.先得到col对应的迭代器
        Iterator iterator = col.iterator();
        //2.使用while循环遍历
        while(iterator.hasNext()){//判断是否还有数据
            //返回下一个元素，类型是Object
            Object obj = iterator.next();
            System.out.println("obj" + obj);
        }
        //快捷键，快速的生成while循环->itit (Ctrl +J 可以显示快捷模版)
        //
        //3.当退出while循环后，这是iterator迭代器指向最后的元素
        //iterator.next();//NoSuchElementException
        //4.再次遍历需要重置我们的迭代器
        iterator = col.iterator();
    }
}
 
class Book {
    private String name;
    private String author;
    private double price;
 
    public Book(String name, String author, double price) {
        this.name = name;
        this.author = author;
        this.price = price;
    }
 
    public String getName() {
        return name;
    }
 
    public void setName(String name) {
        this.name = name;
    }
 
    public String getAuthor() {
        return author;
    }
 
    public void setAuthor(String author) {
        this.author = author;
    }
 
    public double getPrice() {
        return price;
    }
 
    public void setPrice(double price) {
        this.price = price;
    }
 
    @Override
    public String toString() {
        return "Book{" +
                "name='" + name + '\'' +
                ", author='" + author + '\'' +
                ", price=" + price +
                '}';
    }
}

3.增强for循环完成迭代器

增强for循环，可以代替iterator迭代器，特点:增强for就是简化版的iterator本质样。只能用于遍历合或数组。

基本语法

for(元素类型元素名:集合名或数组名) {访问元素}


public class CollectionFor {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        Collection col = new ArrayList();
 
        col.add(new Book("三国演义", "罗贯中", 10.1));
        col.add(new Book("小李飞刀", "古龙", 5.1));
        col.add(new Book("红楼梦", "曹雪芹", 34.6));
 
        for (Object o : col) {
            System.out.println("book=" + o);
        }
        //1. 使用增强for, 在Collection集合
        //2. 增强for， 底层仍然是迭代器
        //3. 增强for可以理解成就是简化版本的 迭代器遍历
 
        //4. 快捷键方式 I
        // for (Object book : col) {
        //     System.out.println("book=" + book);
        // }
 
 
        //增强for，也可以直接在数组使用
        // int[] nums = {1, 8, 10, 90};
        // for (int i : nums) {
        //     System.out.println("i=" + i);
        // }
 
 
    }
}

增强for，底层仍然是迭代器

增强for可以理解成就是简化版本的迭代器遍历

4.迭代器练习


public class CollectionExercise {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add(new Dog("小黑", 3));
        list.add(new Dog("大黄", 100));
        list.add(new Dog("大壮", 8));
 
 
        //先使用for增强
        for (Object dog : list) {
            System.out.println("dog=" + dog);
        }
 
        //使用迭代器
        System.out.println("===使用迭代器来遍历===");
        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            Object dog =  iterator.next();
            System.out.println("dog=" + dog);
 
        }
 
    }
}
/**
 * 创建  3个 Dog {name, age}  对象，放入到 ArrayList 中，赋给 List 引用
 * 用迭代器和增强for循环两种方式来遍历
 * 重写Dog 的toString方法， 输出name和age
 */
class Dog {
    private String name;
    private int age;
 
    public Dog(String name, int age) {
        this.name = name;
        this.age = age;
    }
 
    public String getName() {
        return name;
    }
 
    public void setName(String name) {
        this.name = name;
    }
 
    public int getAge() {
        return age;
    }
 
    public void setAge(int age) {
        this.age = age;
    }
 
    @Override
    public String toString() {
        return "Dog{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

三、List接口方法

1.List接口基本介绍

List接口是Collection接口的子接口

1) List集合类中元素有序(即添加顺序和取出顺序一致)、且可重复

2) List集合中的每个元素都有其对应的顺序索引，即支持索引。

3) List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。

List list = new ArrayList(;

4) JDK API中List接口的实现类有

2.List的常用方法


public class ListMethod {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("张三丰");
        list.add("贾宝玉");
 
        //void add(int index, Object ele):在index位置插入ele元素
        //在index = 1的位置插入一个对象
        list.add(1, "韩顺平");
        System.out.println("list=" + list);
 
        //boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来
        List list2 = new ArrayList();
        list2.add("jack");
        list2.add("tom");
        list.addAll(1, list2);
        System.out.println("list=" + list);
 
        //Object get(int index):获取指定index位置的元素
        //collection方法有
 
        //int indexOf(Object obj):返回obj在集合中首次出现的位置
        System.out.println(list.indexOf("tom"));//2
 
        //int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置
        list.add("韩顺平");
        System.out.println("list=" + list);
        System.out.println(list.lastIndexOf("韩顺平"));
 
        // Object remove(int index):移除指定index位置的元素，并返回此元素
        list.remove(0);
        System.out.println("list=" + list);
 
        //Object set(int index, Object ele):设置指定index位置的元素为ele , 相当于是替换.
        list.set(1, "玛丽");//一定要存在才能替换
        System.out.println("list=" + list);
 
        //List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的子集合
        // 注意返回的子集合 fromIndex <= subList < toIndex [0,2)
        List returnlist = list.subList(0, 2);
        System.out.println("returnlist=" + returnlist);
    }
}

3.List练习


public class ListExercise {
    public static void main(String[] args) {
        List list = new ArrayList();
        for (int i = 0; i < 12; i++) {
            list.add("hello" + i);
        }//在索引为1插入一个元素
        list.add(1,"hspedu");
        System.out.println("list=" + list);//在abstractCollection内有toString方法
        //获得下标为4的元素
        System.out.println("第五个元素" + list.get(4));
        //删除下标为5的元素
        list.remove(5);
        System.out.println("list" + list);
        //修改第七个元素
        list.set(6,"三国演义");
        //使用迭代器
        for (Object o : list) {
            System.out.println(o);
        }
        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            Object next =  iterator.next();
            System.out.println(next);
        }
 
    }
}

4.ListFor三种遍历方式与三种子类

List的三种遍历方式while for增强 for普通

[ArrayList, LinkedList,Vector]三种运行类型。只要是实现List接口的子类都能这么遍历。（区别后面会讲）

//List 接口的实现子类 Vector LinkedList
List list = new ArrayList();
List list = new Vector();
List list = new LinkedList();


public class ListFor {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
 
        //List 接口的实现子类 Vector LinkedList
        //List list = new ArrayList();//换成ArrayList代码也不会报错
        //List list = new Vector();//换成Vector也不会报错
        List list = new LinkedList();
 
        list.add("jack");
        list.add("tom");
        list.add("鱼香肉丝");
        list.add("北京烤鸭子");
 
        //遍历
        //1. 迭代器
        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            Object obj =  iterator.next();
            System.out.println(obj);
 
        }
 
        System.out.println("=====增强for=====");
        //2. 增强for
        for (Object o : list) {
            System.out.println("o=" + o);
        }
 
        System.out.println("=====普通for====");
        //3. 使用普通for
        for (int i = 0; i < list.size(); i++) {
            System.out.println("对象=" + list.get(i));
        }
    }
}

5.List接口课堂练习


public class ListExercise01 {
    @SuppressWarnings({"ALL"})
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add(new Book("三国演义", "罗贯中", 10.1));
        list.add(new Book("小李飞刀", "古龙", 5.1));
        list.add(new Book("红楼梦", "曹雪芹", 34.6));
        list.add(new Book("活着", "余华", 12.4));
        list.add(new Book("3年模拟", "新华", 60.0));
        //如何对集合进行排序
        sort(list);
 
        for (Object o : list) {
            //直接sout(list)的话调用的是AbstactCoolection的toShtring方法，虽然也会调用对象的toString,但格式不对
            System.out.println(o);
        }
 
    }
    public static void sort(List list){
        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = 0; j < list.size() - i - 1; j++) {
                //取出对象
                Book book = (Book)list.get(j);
                Book book1 = (Book)list.get(j + 1);
                if (book.getPrice() < book1.getPrice()){
                    list.set(j,book1);
                    list.set(j + 1,book);
                }
            }
        }
    }
}
class Book {
    private String name;
    private String author;
    private double price;
 
    public Book(String name, String author, double price) {
        this.name = name;
        this.author = author;
        this.price = price;
    }
 
    public String getName() {
        return name;
    }
 
    public void setName(String name) {
        this.name = name;
    }
 
    public String getAuthor() {
        return author;
    }
 
    public void setAuthor(String author) {
        this.author = author;
    }
 
    public double getPrice() {
        return price;
    }
 
    public void setPrice(double price) {
        this.price = price;
    }
 
    @Override
    public String toString() {
        return "名字=" + name + "\t\t作者=" + author + "\t\t价格=" + price;
    }
}

四、ArrayList 的底层结构和源码分析（建议多看看）

1.ArrayList的细节

1)permits all elements, including null，ArrayList可以加入null,并且多个

2) ArrayList是由数组来实现数据存储的

3) ArrayList基本等同于Vector，除了ArrayList是线程不安全(执行效率高)看源码.，
在多线程情况下，不建议使用ArrayList


public class ArrayListDetail {
    public static void main(String[] args) {
 
        //ArrayList 是线程不安全的, 可以看源码 没有 synchronized
        /*
            public boolean add(E e) {
                ensureCapacityInternal(size + 1);  // Increments modCount!!
                elementData[size++] = e;
                return true;
            }
         */
        ArrayList arrayList = new ArrayList();
        arrayList.add(null);
        arrayList.add("jack");
        arrayList.add(null);
        arrayList.add("hsp");
        System.out.println(arrayList);
    }
}

2.ArrayList的源码分析（重点难点）

1) ArrayList中维护了一个Object类型的数组elementData.

transient Object[] elementData;//tansient表示瞬间，将来这个被修饰的对象不会被序列化

2)当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0，第1次添加，则扩容elementData为10, 如需要再次扩容，则扩容elementData为1.5倍。//每次都会检测扩容

3)如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容，则直接扩容elementData为1.5倍。

用下列源码debug看


public class ArrayListSource {
    public static void main(String[] args) {
        //注意，注意，注意，Idea 默认情况下，Debug 显示的数据是简化后的，如果希望看到完整的数据
        //需要做设置.
        //使用无参构造器创建ArrayList对象
        ArrayList list = new ArrayList();
        // ArrayList list = new ArrayList(8);
        //使用for给list集合添加 1-10数据
        for (int i = 1; i <= 10; i++) {
            list.add(i);
        }
        //使用for给list集合添加 11-15数据
        for (int i = 11; i <= 15; i++) {
            list.add(i);
        }
        list.add(100);
        list.add(200);
        list.add(null);
    }
}

源码流程图

IDEA在debug的时候会出现省略null空数据，可以设置显示

省略null数据可以设置显示

五、Vector类的底层结构和源码分析（建议多看看）

1.Vector的基本介绍

1) Vector类的定义说明

public class Vector<E>

extends AbstractList<E>

implements List<E>, RandomAccess, Cloneable, Serializable

2) Vector底层也是一个对象数组， protected Object[] elementData;

3) Vector是线程同步的，即线程安全，Vector类的操作方法带有synchronized

public synchronized E get(int index) {

if (index > = elementCount)

throw new ArrayIndexOutOfBoundsException(index);

return elementData(index);

4)在开发中，需要线程同步安全时，考虑使用Vector


public class Vector_ {
    public static void main(String[] args) {
        //无参构造器
        //有参数的构造
        Vector vector = new Vector(8);
        for (int i = 0; i < 10; i++) {
            vector.add(i);
        }
        vector.add(100);
        System.out.println("vector=" + vector);
        //1. new Vector() 底层
        /*
            public Vector() {
                this(10);
            }
         补充：如果是  Vector vector = new Vector(8);
            走的方法:
            public Vector(int initialCapacity) {
                this(initialCapacity, 0);
            }
         2. vector.add(i)
         2.1  //下面这个方法就添加数据到vector集合
            public synchronized boolean add(E e) {
                modCount++;
                ensureCapacityHelper(elementCount + 1);
                elementData[elementCount++] = e;
                return true;
            }
          2.2  //确定是否需要扩容 条件 ： minCapacity - elementData.length>0
            private void ensureCapacityHelper(int minCapacity) {
                // overflow-conscious code
                if (minCapacity - elementData.length > 0)
                    grow(minCapacity);
            }
          2.3 //如果 需要的数组大小 不够用，就扩容 , 扩容的算法
              //newCapacity = oldCapacity + ((capacityIncrement > 0) ?
              //                             capacityIncrement : oldCapacity);
              //就是扩容两倍.
            private void grow(int minCapacity) {
                // overflow-conscious code
                int oldCapacity = elementData.length;
                int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                                 capacityIncrement : oldCapacity);
                if (newCapacity - minCapacity < 0)
                    newCapacity = minCapacity;
                if (newCapacity - MAX_ARRAY_SIZE > 0)
                    newCapacity = hugeCapacity(minCapacity);
                elementData = Arrays.copyOf(elementData, newCapacity);
            }
         */
 
    }
}

2.Vector和ArrayList的比较

六、LinkedList的底层结构和源码分析

1.LinkedList的说明

1) LinkedList实现了双向链表和双端队列特点

2)可以添加任意元素(元素可以重复)，包括null

3)线程不安全，没有实现同步

2.模拟双向链表

1) LinkedList底层维护了一个双向链表

2) LinkedList中维护了两个属性first和last分别指向首节点和尾节点

3)每个节点(Node对象)，里面又维护了prev、next. item三个属性，其中通过prev指向前一个，通过next指向后一个节点。最终实现双向链表

4)所以LinkedList的元素的添加和删除，不是通过数组完成的，相对来说效率较高。

5)模拟一个简单的双向链表


public class LinkedList01 {
    public static void main(String[] args) {
 
        //模拟一个简单的双向链表
        Node jack = new Node("jack");
        Node tom = new Node("tom");
        Node hsp = new Node("老韩");
 
        //连接三个结点，形成双向链表(结点也叫对象
        //jack -> tom -> hsp
        jack.next = tom;
        tom.next = hsp;
        //hsp -> tom -> jack
        hsp.pre = tom;
        tom.pre = jack;
 
        Node first = jack;//让first引用指向jack,就是双向链表的头结点
        Node last = hsp; //让last引用指向hsp,就是双向链表的尾结点
 
 
        //演示，从头到尾进行遍历
        System.out.println("===从头到尾进行遍历===");
        while (true) {
            if(first == null) {
                break;
            }
            //输出first 信息
            System.out.println(first);
            first = first.next;
        }
 
        //演示，从尾到头的遍历
        System.out.println("====从尾到头的遍历====");
        while (true) {
            if(last == null) {
                break;
            }
            //输出last 信息
            System.out.println(last);
            last = last.pre;
        }
 
        //演示链表的添加对象/数据，是多么的方便
        //要求，是在 tom --------- 老韩直接，插入一个对象 smith
        //1. 先创建一个 Node 结点，name 就是 smith
        Node smith = new Node("smith");
        //下面就把 smith 加入到双向链表了
        smith.next = hsp;
        smith.pre = tom;
        hsp.pre = smith;
        tom.next = smith;
 
        //让first 再次指向jack
        first = jack;//让first引用指向jack,就是双向链表的头结点
 
        System.out.println("===从头到尾进行遍历===");
        while (true) {
            if(first == null) {
                break;
            }
            //输出first 信息
            System.out.println(first);
            first = first.next;
        }
 
        last = hsp; //让last 重新指向最后一个结点
        //演示，从尾到头的遍历
        System.out.println("====从尾到头的遍历====");
        while (true) {
            if(last == null) {
                break;
            }
            //输出last 信息
            System.out.println(last);
            last = last.pre;
        }
    }
}
 
//定义一个Node 类，Node对象,表示双向链表的一个结点
class Node {
    public Object item; //真正存放数据
    public Node next; //指向后一个结点(下一个
    public Node pre; //指向前一个结点(上一个
    public Node(Object name) {
        this.item = name;
    }
    public String toString() {
        return "Node name=" + item;
    }
}

3.LinkedListCURD分析

增加

删除


 
               public boolean add(E e) {
                    linkLast(e);
                    return true;
                }
            4.将新的结点，加入到双向链表的最后
             void linkLast(E e) {
                final Node<E> l = last;
                final Node<E> newNode = new Node<>(l, e, null);
                last = newNode;
                if (l == null)
                    first = newNode;
                else
                    l.next = newNode;
                size++;
                modCount++;
            }
 
         */
 
 
        //演示一个删除结点的
        linkedList.remove(); // 这里默认删除的是第一个结点
        //linkedList.remove(2);
        System.out.println("linkedList=" + linkedList);
         /*
          老韩读源码 linkedList.remove(); // 这里默认删除的是第一个结点
          1. 执行 removeFirst
            public E remove() {
                return removeFirst();
            }
         2. 执行
            public E removeFirst() {
                final Node<E> f = first;
                if (f == null)
                    throw new NoSuchElementException();
                return unlinkFirst(f);
            }
            /*
          3. 执行 unlinkFirst, 将 f 指向的双向链表的第一个结点拿掉
            private E unlinkFirst(Node<E> f) {
                // assert f == first && f != null;
                final E element = f.item;
                final Node<E> next = f.next;
                f.item = null;
                f.next = null; // help GC
                first = next;
                if (next == null)
                    last = null;
                else
                    next.prev = null;
                size--;
                modCount++;
                return element;
            }
        */
        
        //修改某个结点对象
        linkedList.set(1, 999);
        System.out.println("linkedList=" + linkedList);
 
        //得到某个结点对象
        //get(1) 是得到双向链表的第二个对象
        Object o = linkedList.get(1);
        System.out.println(o);//999
 
        //因为LinkedList 是 实现了List接口, 遍历方式
        System.out.println("===LinkeList遍历迭代器====");
        Iterator iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            Object next =  iterator.next();
            System.out.println("next=" + next);
 
        }
 
        System.out.println("===LinkeList遍历增强for====");
        for (Object o1 : linkedList) {
            System.out.println("o1=" + o1);
        }
        System.out.println("===LinkeList遍历普通for====");
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.get(i));
        }
    }
}

4.ArrayList和inkedList的比较

如何选择ArrayList和LinkedList:

两个都是线程不安全的

1)如果我们改查的操作多，选择ArrayList

2)如果我们增删的操作多，选择LinkedList

3)一般来说，在程序中，80%-90%都是查询，因此大部分情况下会选择ArrayList

4)在一个项目中，根据业务灵活选择，也可能这样，一个模块使用的是ArrayList,另外一个模块是LinkedList.

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/77338