集合框架List笔记

Java集合

Java集合分为List、Set、Map和Queue。

List代表有序，可重复的集合。

Set代表无序，不可重复的集合。

Map代表具有映射关系的集合。

ArrayList

ArrayList是List的子类，底层就是用数组保存数据以及对数据进行操作。

常用构造方法

public ArrayList()：无参构造，默认创建一个空数组，当添加第一个数据时，需要扩容，默认长度为10，当添加第十一个数据时，再次扩容，长度为原长度的1.5倍，以此类推。
public ArrayList(int initialCapacity)：默认的长度为传入的参数，超出长度添加时，需要扩容，长度为原长度的1.5倍。

ArrayList的长度最小为0，最大为Integer的最大值（2^31-1）。

常用API

方法	描述
add(Object o)	添加数据
add(int index,Object o)	在制定索引处添加元素
size()	获取元素个数
get(int index)	获取索引处的元素
isEmpty()	判断集合是否为空
indexOf(Object o)	判断某个元素第一次出现的位置
E remove(int index)	移除索引处元素，并返回该元素
boolean remove(Object o)	移除元素
clear()	清空元素
set(int index ,E e)	修改索引处的元素
iterator()	获取迭代器
toArray()	将集合转换为数组

手动实现ArrayList

public class Ary {
    
    int[] ary;
    int num;//数组内的内容的个数
    
    
    
    public Ary() {//初始化
        this.ary = new int[10];
        this.num = 0;
    }

    

    @Override
    public String toString() {
        return Arrays.toString(ary);
    }



    public void add(int e) {
        if(num<10) {//如果数组中的内容小于10
            //添加元素值
            ary[num]=e;
            //添加一个，内容加一
            num++;
        }else {//数组内容等于10
            System.out.println("数组已满");
        }
    }
    
    public void add(int index,int e) {
        if(num<10) {
            if(index>=0 && index<=num-1) {//索引只能大于等于0，小于等于数组中内容数减一
                for(int i=num;i>index;i--) {//先将包括索引位置的值向后移一位
                    ary[i]=ary[i-1];
                }
                ary[index]=e;//将索引位置的值设置为传入的e
            }else {
                System.out.println("索引错误");
            }
        }else {
            System.out.println("数组已满");
        }
    }
    
    public void remove(int index) {
        if(num<10) {
            if(index>=0 && index<=num-1) {
                for(int i=index;i<num;i++) {//索引位置开始，通过赋值将元素值向前移动一位
                    ary[i]=ary[i+1];
                }
                num--;//数组内容数减一
            }else {
                System.out.println("索引错误");
            }
        }else {
            System.out.println("数组已满");
        }
    }
    
    public int get(int index) {
        int get=0;
        if(index>=0 && index<=num-1) {
            get=ary[index];//获取索引处的元素值
            return get;
        }else {
            System.out.println("索引错误");
            return -1;
        }
    }
    
    public void set(int index,int e){
        if(index>=0 && index<=num-1) {
            ary[index]=e;//将索引处内容重新赋值
        }else {
            System.out.println("索引错误");
        }
    }
    
    
    
    
    
    public static void main(String[] args) {
        Ary ary=new Ary();
        ary.add(1);
        ary.add(6);
        ary.add(8);
        ary.add(2);
        ary.add(4);
//        System.out.println(ary.toString());
//        ary.add(2, 7);
//        System.out.println(ary.toString());
//        ary.remove(3);
//        ary.set(0, 9);
        System.out.println(ary.toString());
//        System.out.println("获取的元素值为"+ary.get(2));
    }
}

ArrayList和Vector

Vector与ArrayList基本类似

Vector的扩容为原长度的2倍，ArrayList则是原长度的1.5倍。
Vector是线程安全的。
Vector调用无参构造时，直接创建初始化长度为10的数组，而ArrayList调用无参构造是创建一个长度为0的空数组，添加第一个元素时，数组长度扩容为10。

LinkedList

手动实现LinkedList链表

单链表

/**
 * 单链表的增删查改实现
 *
 * @author xigua
 * @date 2022/8/116:51
 */
public class MyLinkedList {
    /** 内部类 */
    private class Node{
        /** 节点中存的数据 */
        public Object date;

        /** 下一个节点的引用地址  */
        public Node next;

        public Node(Object date, Node next) {
            this.date = date;
            this.next = next;
        }
    }

    /** 首节点 */
    private Node first;
    /** 尾节点 */
    private Node last;
    /** 元素个数 */
    private int size=0;
    /** 初始化链表*/
    public MyLinkedList() {
        first=null;
        last=null;
    }
    /** 判断索引是否越界*/
    public void checkIndex(int index){
        if(index<0 || index>size-1){
            throw new IndexOutOfBoundsException("索引越界");
        }
    }

    /** 获取存储的节点个数*/
    public int size(){
        return size;
    }

    /** 获取索引处对象存放的数据*/
    public Object get(int index){
        return getNode(index).date;
    }
    /** 获取索引处的节点*/
    public Node getNode(int index){
        checkIndex(index);
        Node current=first;
        for (int i = 0; i < index; i++) {
            current=current.next;
        }
        return current;
    }

    /** 末尾添加元素*/
    public boolean add(Object o){
        /** 链表为空*/
        if (size==0){
            /** 只有一个节点，首节点，尾节点都是它*/
            Node node=new Node(o,null);
            first=node;
            last=node;
        }else {
            /** 链表不为空*/
            Node node=new Node(o,null);
            last.next=node;
            last=node;
        }
        size++;
        return true;
    }

    /** index处添加元素*/
    public boolean add(int index,Object o){
        checkIndex(index);
        /** 末尾添加*/
        if (index==size-1){
            return add(o);
        }
        /** 头部添加*/
        else if (index==0){
            Node node=new Node(o,first);
            first=node;
        }
        /** 中间添加*/
        /**
         * 获取索引处的节点
         * 和索引前的节点
         * 创建新节点
         * */
        else {
            Node indexNode=getNode(index);
            Node preNode=getNode(index-1);
            Node node=new Node(o,indexNode);
            preNode.next=node;
        }
        size++;
        return true;
    }

    /** 删除索引处的节点*/
    public Object remove(int index){
        checkIndex(index);
        Object o=null;
        /** 只有一个节点时
         * 只有索引处一个节点
         * 节点赋空值
         * */
        if (size==1){
            Node node=getNode(index);
            node.date=null;
            first=null;
            last=null;
        }
        /**
         * 删除首节点
         * */
        else if (index==0){
            Node firstNode=getNode(index);
            first=firstNode.next;
            o=firstNode.date;
            firstNode.next=null;
            firstNode.date=null;
        }
        /** 删除尾节点
         *  倒数第二个节点的next赋null
         * */
        else if(index==size-1){
            Node lastNode=getNode(index);
            o=lastNode.date;
            last=getNode(index-1);
            getNode(index-1).next=null;
        }
        /** 删除中间节点
         *  获取要删除的节点，以及它的前节点和后节点
         *  前节点的next指向后节点
         *  删除的节点next赋null
         * */
        else{
            Node indexNode=getNode(index);
            o= indexNode.date;
            Node preNode=getNode(index-1);
            Node nextNode=indexNode.next;
            preNode.next=nextNode;
            indexNode.next=null;
        }
        size--;
        return o;
    }

    /** 修改节点的值
     *  获取要修改的节点
     *  修改节点的date
     * */
    public Object set(int index,Object o){
        checkIndex(index);
        Node node=getNode(index);
        Object oldValue=node.date;
        node.date=o;
        return oldValue;
    }

}

双链表

/**
 *双向链表的增删查改实现
 *
 * @author xigua
 * @date 2022/8/119:38
 */
public class TwoLinkedList {
    /**
     * 内部类
     * */
    private class Node{
        /** 储存的数据*/
        private Object date;
        /** 前节点的地址*/
        private Node previous;
        /** 后节点的地址*/
        private Node next;
        /** 每个节点都包含的三个属性*/
        public Node(Object date, Node previous, Node next) {
            this.date = date;
            this.previous = previous;
            this.next = next;
        }
    }

    /** 首节点*/
    private Node first;
    /** 尾节点*/
    private Node last;
    /** 节点数*/
    private int size=0;

    public TwoLinkedList() {
        this.first = null;
        this.last = null;
    }

    /** 判断索引是否越界*/
    public void checkIndex(int index){
        if (index<0 || index>size-1){
            throw new IndexOutOfBoundsException("索引越界！");
        }
    }
    /** 获取节点个数*/
    public int size(){
        return size;
    }
    /** 获取索引处节点
     *  第n个节点，就是首节点next n次
     * */
    public Node getNode(int index){
        checkIndex(index);
        Node current=first;
        for (int i = 0; i < index; i++) {
            current=current.next;
        }
        return current;
    }
    /**
     * 获取节点中存的数据
     * */
    public Object get(int index){
        return getNode(index).date;
    }
    /** 末尾处添加节点*/
    public boolean add(Object o){
        /** 链表为空时
         *  只有添加的这一个节点，无前后节点
         * */
        if (size==0){
            Node node=new Node(o,null,null);
            first=node;
            last=node;
        }else {
            /** 链表不为空，创建新节点，last的next指向它，它的previous指向last，最后last变成新加的节点*/
            Node node=new Node(o,last,null);
            last.next=node;
            last=node;
        }
        size++;
        return true;
    }
    /** 索引处添加节点*/
    public boolean add(int index,Object o){
        checkIndex(index);
        /** 在首节点前添加
         *  创建需要添加的节点
         *  新节点的previous为null，next指向first
         *  first的previous指向新节点，first变为新节点
         * */
        if(index==0){
            Node node=new Node(o,null,first);
            first.previous=node;
            first=node;
        }
        /** 在尾节点处添加
         *  调用add(Object o)方法
         * */
        else if (index==size-1){
            return add(o);
        }
        /** 在中间添加
         *  创建新节点，找出索引处的节点和该节点的前节点
         *  前节点的的next指向新节点，新节点的previous指向前节点，next指向索引节点，索引节点的previous指向新节点
         * */
        else{
            Node indexNode=getNode(index);
            Node preNode=getNode(index-1);
            Node node=new Node(o,preNode,indexNode);
            preNode.next=node;
            indexNode.previous=node;
        }
        size++;
        return true;
    }

    /** 删除索引处的节点*/
    public Object remove(int index){
        checkIndex(index);
        Object o=null;
        /** 只有一个节点值*/
        if (size==1){
            Node node=getNode(index);
            node.date=null;
            first=null;
            last=null;
        }
        /** 删除首节点
         *  first变为index+1的节点
         *  index的节点的next赋空
         *  index+1的节点的previous赋空
         * */
        else if (index==0){
            Node indexNode=getNode(index);
            Node nextNode=getNode(index+1);
            nextNode.previous=null;
            indexNode.next=null;
            o=indexNode.date;
            indexNode.date=null;
            first=nextNode;
        }
        /** 删除尾节点
         *  index-1的节点的next赋空
         *  index节点的previous赋空
         *  last变为index-1的节点
         *  index节点的值赋空
         * */
        else if(index==size-1){
            Node indexNode=getNode(index);
            Node preNode=getNode(index-1);
            preNode.next=null;
            indexNode.previous=null;
            o=indexNode.date;
            indexNode.date=null;
            last=preNode;
        }
        /** 删除中间节点
         *  获取要删除的节点，以及它的前节点后节点
         *  前节点的next指向后节点
         *  后节点的previous指向前节点
         *  索引节点的previous和next以及data赋空
         * */
        else{
            Node indexNode=getNode(index);
            Node preNode=getNode(index-1);
            Node nextNode=getNode(index+1);
            preNode.next=nextNode;
            nextNode.previous=preNode;
            o=indexNode.date;
            indexNode.previous=null;
            indexNode.next=null;
            indexNode.date=null;
        }
        size--;
        return o;
    }

    /** 修改索引处的值
     *  获取索引的节点
     *  修改节点的值
     * */
    public void set(int index,Object o){
        Node node=getNode(index);
        node.date=o;
    }
}

测试

public class Test {
    public static void main(String[] args) {
        MyLinkedList list=new MyLinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(1,66);
        list.remove(0);
        list.set(2,8);
        for (int i = 0; i < list.size() ; i++) {
            System.out.println(list.get(i));
        }

//        TwoLinkedList list=new TwoLinkedList();
//        list.add(1);
//        list.add(2);
//        list.add(3);
////        list.add(2,8);
////        list.remove(1);
//        list.set(2,8);
//        for (int i = 0; i < list.size(); i++) {
//            System.out.println(list.get(i));
//        }
    }
}

ArrayList和LinkedList的区别

ArrayList和LinkedList虽然都是List接口的子类，但是在底层实现以及效率上存在以下区别

ArrayList和LinkedList都实现了List接口
ArrayList和LinkedList都是非线程安全的，因此在多线程环境下可能会出现出现不同步的情况
ArrayList底层实现是数组，LinkedList底层实现是双向链表
ArrayList因为底层实现是数组，并且支持随机访问因此查找效率高，但是ArrayList在新增元素时会扩容以及复制数组元素，并且删除时也会进行数组复制，所以增删效率低。而LinkedList不支持随机访问，获取元素时必须从首节点开始从前往后遍历查找，因此查找效率低。但是增加和删除时最多涉及到两个节点的操作，因此增删效率高。

ArrayList和LinkedList的遍历方式

        /**
         * for循环遍历
         * */
        System.out.println("for循环遍历：");
        for (int i = 0;i < list.size();i++){
            System.out.println(list.get(i));
        }

        /**
         * foreach循环遍历
         * */
        System.out.println("foreach循环遍历：");
        for (String s : list) {
            System.out.println(s);
        }

        /**
         * 迭代器遍历
         *
         * 相当于指针从第一个前开始（空值），通过hasNext判断
         * 当前指向的后面是否有值，有为true,通过next（）输出
         * 该值。
         *
         * 不能连续两次使用同一个while遍历，因为第一次遍历完后
         * 指针在最后一位上，无法向后遍历
         * */
        System.out.println("迭代器遍历：");
        Iterator<String> iterator=list.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }

        /**
         * List迭代器遍历
         * */
        System.out.println("List迭代器遍历：");

        /**
         * 从前往后遍历
         * */
        ListIterator<String> listIterator=list.listIterator();
        while(listIterator.hasNext()){
            System.out.println(listIterator.next());
        }

        /**
         * 从后往前遍历
         * */
        while(listIterator.hasPrevious()){
            System.out.println(listIterator.previous());
        }

        /**
         * Lambda表达式
         * */
        System.out.println("Lambda表达式：");
        list.forEach(s -> System.out.println(s));
    }

Queue

Queue用于模拟队列这类数据结构，队列采用FIFO（先进先出）原则。

Queue定义的方法：

public interface Queue<E> extends Collection<E> {
    //队列末尾添加元素
    boolean add(E e);
    //将指定的元素添加到队列尾部，当使用有容量限制的队列时，此方法通常比 add(Object e)方法更好。
    boolean offer(E e);
    //移除队列头部的元素，但不删除
    E remove();
    //获取队列头部的元素，并删除该元素
    E poll();
    //获取队列头部的元素
    E element();
    //获取队列头部的元素，但是不删除
    E peek();
}

LinkedList实现类

LinkedList类是List接口的实现类，也就是说LinkedList可以根据索引来随机访问放入其中的元素，除此以外LinkedList也可以被当做栈和队列使用。

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<String>();
        //将字符串加入队列末尾
        linkedList.offer("Java");
        //将一个字符串加入栈的顶部
        linkedList.push("Spring");
        //将字符串添加到队列头部（相当于栈的顶部）
        linkedList.offerFirst("HTML");
        //当做list遍历
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.get(i));
        }
        //访问并不删除栈顶的元素
        System.out.println(linkedList.peekFirst());
        //访问并不删除队列的最后一个元素
        System.out.println(linkedList.peekLast());
        //将栈顶的元素弹出栈
        System.out.println(linkedList.pop());
        //输出[Spring, Java]
        System.out.println(linkedList);
        //访问并删除队列中的最后一个元素
        System.out.println(linkedList.pollLast());
        //输出[[Spring]]
        System.out.println(linkedList);
    }
}

上面的代码分别演示了LinkedList作为List，双端队列及栈的使用，所以LinkedList是一个功能非常强大的类，但是需要注意的是，虽然LinkedList功能强大，开发中如果要当做队列使用，就不要调用栈和list相关的方法，这样做会引起不必要的麻烦以及代码难以维护。