【Java】ArrayList与LinkedList详解！！！

一🌞、List

1🍅.什么是List？

在集合框架中，List就是一个接口，继承于Collection接口。

在数据结构的角度，List就是一个线性表，即n个具有相同类型元素的有限序列，在该序列上可以执行增删查改以及变量等操作。

**什么是线性表？ **

线性表是由n个具有相同类型元素组成的有限序列。线性表是一种常见的数据结构。在逻辑上，线性表是一种线性结构，就是连续的一条直线，在物理结构上，不一定是连续的，在物理存储是，通常是以数组和链式的结构形式存储。常见的线性比表有顺序表、链表、栈、队列.......

2🍅.List中的常用方法

增boolean add（E e）插入元素e在末尾void add（int index，E element）插入元素e在index位置boolean addAll（Collection？extends？E>c）尾插c中的元素删E remove（int index）删除index位置的元素boolean remove（Object o）删除第一次出现的o元素void clear（）清空查E get（int index）获取index下标位置元素int indexOf（Object o）获取第一个o元素所在的下标int lastindexOf（Object o）获取最后一个o元素所在的下标boolean contains（Object o）查看是否包含o元素改E set（int index，E Element）将index下标的元素改为e截取List<E>subList（int formIndex,int toIndex）截取部分list
List是一个接口，所以不能直接实例化。如果想要使用list接口，必须实例化list的实现类。

在集合框架中，ArrayList和LinkedList都实现了这个接口。

二🌞、ArrayList

1🍍.什么是ArrayList?

ArrayList是一个普通的类，是顺序表的一种，实现了list接口，是一种可动态调整大小的数组，能够储存不同类型的对象。

什么是顺序表？

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

2🍍.ArrayList的实例化

        //接口的实例化：
        List<Integer> list1=new ArrayList<>();
       //ArrayList的实例化：
        ArrayList<Integer> list=new ArrayList<>();
      

两者区别：

• 接口的实例化：只能使用接口中定义类的方法；
• ArrayList实例化：可以使用ArrayList中独有的方法，更具有灵活性

3🍍.ArrayList的使用

ArrayList常见方法：
增：void add（int data）在数组最后添加元素void add（int pos，int data）在数组某下标插入元素删：void remove（int toRemove）删除第一次出现的元素void clear（）；清空所有元素查:
boolean contains（int toFind）
查看是否包含该元素int get（int pos）获取该下标元素int indexOf（int toFind ）获取该元素下标改：void set（int pos，int value）将下标元素进行更改
ArrayList方法的使用：

 public static void main(String[] args) {
        List<Integer> list1=new ArrayList<>();
        //增：
        //add：尾插
        list1.add(1);
        list1.add(2);
        list1.add(3);
        list1.add(4);
        list1.add(5);
        System.out.println(list1);//[1, 2, 3, 4, 5]
        //add：任意位置插入
        list1.add(3,100);
        System.out.println(list1);//[1, 2, 3, 100, 4, 5]
        //查：
        //contains:是否包含该元素
        System.out.println(list1.contains(11));//false
        //get:获取下标元素
        int ret=list1.get(3);
        System.out.println(ret);//100
        //indexOf:获取元素下标
        int ret2=list1.indexOf(4);
        System.out.println(ret2);//4
        //改
        //set:将某下标的元素进行更改
        list1.set(1,13);
        System.out.println(list1);//[1, 13, 3, 100, 4, 5]
        //删：
        // remove：删除第一次出现的元素
        list1.remove(2);
        list1.remove(3);
        //list1.remove(6);//超出范围，报错
        System.out.println(list1);//[1, 13, 100, 5]
        //清空
        list1.clear();
        System.out.println(list1);//无
        //大小的获取：
        System.out.println(list1.size());
    }

4🍍.ArrayList的遍历

ArrayList的遍历可以使用三种方法：for循环、foreach、使用迭代器

示例：

 public static void main(String[] args) {
        List<Integer> list1=new ArrayList<>();
        list1.add(1);
        list1.add(2);
        list1.add(3);
        list1.add(4);
        list1.add(5);
    }

for循环：

//for循环语句：
        //list1.size（）：list1长度
        for (int i = 0; i < list1.size(); i++) {
            //get（i）：获取i下标的元素
            System.out.print(list1.get(i)+" ");//1 2 3 4 5 
        }
    

foreach语句：

//foreach:
        //每次循环时，取出list中的一个元素，将该元素赋值给变量num中
        for (Integer num:list1) {
            System.out.print(num+" ");//1 2 3 4 5
        }

迭代器：Iterator和ListIterator

 //迭代器:
        //从前往后打印
        // Iterator
        System.out.println("=====Iterator=====");
        Iterator<Integer> a=list1.iterator();
        //a.hasNext():用于判断集合a中是否还有下一个元素，如果有返回true，没有返回false
        while(a.hasNext()){
            //a.next:返回迭代器当前所指向的元素，然后指向下一个元素未被遍历的元素并打印
            System.out.print(a.next()+" ");
        }
        System.out.println();
        //listIterator
        System.out.println("=====listIterator=====");
        ListIterator<Integer> b=list1.listIterator();
        while(b.hasNext()){
            System.out.print(b.next()+" ");//1 2 3 4 5 
        }
        System.out.println();
        System.out.println("=====listIterator=====");
        //从后往前打印
        ListIterator<Integer> c=list1.listIterator(list1.size());
        //b.hasPrevious():用于判断集合a中是否有上一个元素，如果有返回true，没有返回false
        while(b.hasPrevious()){
            //b.previous:返回迭代器当前所指向的元素，然后指向上一个元素未被遍历的元素并打印
            System.out.print(b.previous()+" ");//5 4 3 2 1 
        }

• ArrayList适合使用for循环语句遍历；

Iterator和Listiterator的区别：

• Iterator是Java中的一个接口，通过hasNext（）和next（）方法实现顺序遍历；
• Listiterator是Iterator的子接口，除了拥有Iterator的方法外，还有其他功能，所以其还有双向遍历的功能，通过hasPrevious（）和previous（）来实现反向遍历。

5🍍.ArrayList特点

• 动态数组结构：基于数组实现。可以像普通数组一样快速访问元素；
• 动态调整大小：与普通数组不同，当添加的元素个数大于ArrayList容量，ArrayList会自动扩容1.5倍；
• 元素储存有序：元素按照先后添加的顺序在排序中，在插入或者删除元素的时候，会相应改变元素位置；
• 允许元素重复：可以添加多个重复相同的元素；
• 通用性好:可以储存各类对象。

6🍍.ArrayList优缺点

1.🍋ArrayList的优点：

• 快速访问元素：基于数组实现，可以快速访问元素，时间复杂度为O（1）；
• 内存利用相对高效：内存布局相对规整，主要是数组占用空间和少量额外空间用于记录数组大小等信息。在不用频繁的插入和删除中间元素的情况下，内存利用高效；
• 支持随机访问：可以随机访问任意位置的元素，在很多算法和操作中非常有用，如二分查找。

2.🍋ArrayList的缺点：

• 扩容开销：当元素数量大于数组容量的时候，会进行扩容。在扩容时会创建一个新的容量更大的数组并复制旧元素，这会消耗较多的时间和资源；
• 插入和删除的效率较低（中间元素）：在频繁的插入和删除中间元素的时候，需要不断地移动元素，时间复杂度为O（n）。

由于ArrayList不适合进行频繁的插入和删除元素，所以在Java集合中引入了LinkedList，即链表结构。

三🌞、LinkedList

1🍰.什么是LinkedList？

LinkedList的底层是双向链表结构，是链表的一种。

什么是链表？

链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据域和指针域。链表逻辑顺序是连续的，在物理存储结构是非连续的。

链表的分类:

有头链表或者无头链表：

• 有头链表：有一个的头节点，其指针指向第一个数据节点；
• 无头链表：没有专门的头节点，第一个节点直接存储数据；

以下分类都有分为是否是有头链表还是无头链表：

• 单链表：每个节点包含数据和下一个接节点的指针，最后一个节点的指针指向空

• 双链表：每个节点都有包含数据，以及指向前一个节点的指针和指向后一个节点的指针

• 循环链表：循环链表分为单循环链表和双循环链表，其就是最后一个节点的下一个节点的指针指向其头结点。

2🍰.LinkedList的实例化

LinkedList<Integer> list1=new LinkedList<>();

3🍰.LinkedList的使用

其常用方法与ArrayList相差不大

  public static void main(String[] args) {
        LinkedList<Integer> list1=new LinkedList<>();
        //增：
        //add：尾插
        list1.add(1);
        list1.add(2);
        list1.add(3);
        list1.add(4);
        list1.add(5);
        System.out.println(list1);//[1, 2, 3, 4, 5]
        //add：任意位置插入
        list1.add(3,100);
        System.out.println(list1);//[1, 2, 3, 100, 4, 5]
        //查：
        //contains:是否包含该元素
        System.out.println(list1.contains(11));//false
        //get:获取下标元素
        int ret=list1.get(3);
        System.out.println(ret);//100
        //indexOf:获取元素下标
        int ret2=list1.indexOf(4);
        System.out.println(ret2);//4
        //改
        //set:将某下标的元素进行更改
        list1.set(1,13);
        System.out.println(list1);//[1, 13, 3, 100, 4, 5]
        //删：
        // remove：删除第一次出现的元素
        list1.remove(2);
        list1.remove(3);
        //list1.remove(6);//超出范围，报错
        System.out.println(list1);//[1, 13, 100, 5]
        //清空
        list1.clear();
        System.out.println(list1);//无
        //大小的获取：
        System.out.println(list1.size());//0
    }

4🍰.LinkedList的遍历

** 遍历的三种方式：for循环，foreach、迭代器**

 public static void main(String[] args) {
        LinkedList<Integer> list1=new LinkedList<>();
        list1.add(1);
        list1.add(2);
        list1.add(3);
        list1.add(4);
        list1.add(5);
        //for循环语句：
        for (int i = 0; i < list1.size(); i++) {
            int ret=list1.get(i);
            System.out.print(ret+" ");//1 2 3 4 5
        }
        System.out.println();
        //foreach
        for (Integer x:list1) {
            System.out.print(x+" ");//1 2 3 4 5
        }
        System.out.println();
        //迭代器：
        Iterator<Integer> a=list1.iterator();
        while (a.hasNext()){
            System.out.print(a.next()+" ");//1 2 3 4 5
        }
        System.out.println();
        ListIterator b=list1.listIterator();
        while (b.hasNext()){
            System.out.print(b.next()+" ");//1 2 3 4 5 
        }
        System.out.println();
        ListIterator c=list1.listIterator(list1.size());
        while(c.hasPrevious()){
            System.out.print(c.previous()+" ");//5 4 3 2 1
        }
    }

• LinkedList适合使用迭代器遍历；

5🍰.ListedList的特点

• 动态性：没有固定的大小限制，大小可动态变化；
• 插入或删除高效：在插入和删除时，只需修改相关节点即可，时间复杂度为O（1）；
• 顺序访问：只能顺序访问节点，效率较低，时间复杂度为O（n）；
• 存储结构：由一系列节点组成，每个节点包含数据域和指针域；
• 通用性：可以存储不同数据。

6🍰.LinkedList优缺点

1🍐.LinkedList优点:

• 动态性强：节点分散存储，不受连续空间的限制；
• 插入或删除高效：在插入和删除时，只需修改相关节点即可，时间复杂度为O（1）；
• 可扩性好：可方便的增加和减少节点的数量；

2🍐.LinkedList缺点:

• 随机访问效率低：只能顺序访问节点，效率较低，时间复杂度为O（n）；
• 额外空间开销大：除了存储数据本身，每个节点还要存储额外的指针信息，内存利用率低；
• 数据存储不连续：不利于有效存储，导致数据访问慢；

四🌞、ArrayList与LinkedList的区别

不同点ArrayListLinkedList数据结构逻辑上和物理上都是连续的在逻辑上连续，物理上不连续随机访问
随机访问效率快，

时间复杂度为O（1）

随机访问效率慢，

时间复杂度为O（n）
插入或删除
效率慢，

时间复杂度为O（n）

效率快，

时间复杂度为O（1）
容量空间不够需要扩容没有容量限制内存占用内存利用相对高效内存利用率低应用场景元素访问+高效存储插入和删除频繁