【目标】

        1.手写MyLinkedList，体会LinkedList的底层逻辑

        2.掌握LinkedList中的一些方法等

        3.章节测试

【引言】

        关于数据结构，我们按照逻辑关系进行划分，可以分为以下部分：

        所谓数据结构，就是对数据的整合与存储，没有数据结构，程序就没办法高效地处理复杂数据。

        而java相较于c的不同是其内置了部分经典、常用的数据结构，我们在开发的过程中，不能只会用内置数据结构的方法等，还要明白底层是怎么实现的。因此我们本节的学习顺序就是从自己实现链表——MyLinkedList{MysinglyLinkdeList（单向链表的实现） 和 MyDoublyLinkedList（双向链表的实现）}，在此之后认识并掌握内置链表——LinkedList（双向链表的实现）。

        提醒：本章我们用基本数据类型进行演示，如果要顺序表中存储的元素是引用类型，还需要具体的根据需求进行操作

1.ArrayList的弊端

        1. ArrayList底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为O(N)——>进行增删时，时间复杂度大

        2. 增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。——>时间消耗 和 空间消耗。

         3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继 续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。——>空间浪费

        为了解决上述问题，我们引入了链表。

2.MyLinkedList

2.1 链表的类型

        链表的修饰是这样的： 单向/双向、带头/不带头、循环/非循环

        我们先来解释一下分别都是什么含义：

2.1.1 单向/双向

        链表的方向分为单向和双向，其中具体的示例图如下：

        单向：

        双向：

2.1.2 带头/不带头

        所谓头，指的就是头节点。先提醒：第一个数据元素所在的节点 叫做 首元节点（首元节点是会发生变化的）；头节点就是 数据域不存储数据元素、指针域指向首元节点 的节点，这个头节点是链表的一部分（对于整个链表的 任何操作 都会操作到头结点），是固定不变的（不像首元结点可以进行变化）。

        我们再说头指针，头指针就是这个 head ，是一个引用，恒指向链表的第一个节点（有头时指向头结点，无头时指向首元节点）

        不带头：

        带头：

        在这里提醒一句：有些初学者在学到链表的时候，对于这个头指针会有模糊的认识（似懂非懂），我们这里就进行说明白。

2.1.3 循环/非循环

        所谓循环，就是链表的 尾节点 指向 头节点 。

        非循环：

        循环：

2.1.4 总结与介绍        

        所以说总共有八种链表形式，本章节我们主要进行实现常用的两种—— 单向不带头非循环链表 和 双向不带头非循环链表

2.2 MySinglyLinkedLIst（单向不带头非循环链表）

2.2.1 基本结构

        单向链表是通过一组物理地址不连续的存储单元（节点）来存储数据元素的线性结构。

        每个节点由数据域（存储元素值）和指针域（存储下一个节点的地址）组成，节点之间的逻辑顺序（逻辑上是连续的）通过指针链接实现。整个链表通过头指针（指向第一个节点）来标识，最后一个节点的指针指向 NULL（空），表示链表的结束。

2.2.2 单向链表的增（Create）、删（Delete）、查（Read）、改（Update）——CRUD

1.打印链表
    @Override
    public void display() {
        ListNode cur = this.head;
        while(cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

    public static void main(String[] args) {
        //我们进行打印
        System.out.print("目前的链表元素是：");
        mySinglyLinkedList.display();
    }
2.增加/插入节点

        2.1 头插法

    //头插法
    @Override
    public void addFirst(int data) {
        ListNode node = new ListNode(data);

        node.next = this.head;

        this.head = node;
    }

    public static void main(String[] args) {
        //1.头插
        System.out.print("请输入你要添加的元素（头插）：");
        int data1 = scanner.nextInt();

        mySinglyLinkedList.addFirst(data1);

        System.out.print("目前的链表元素是：");
        mySinglyLinkedList.display();
    }

        2.2 尾插法

    //尾插法
    @Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);

        if (this.head == null) {
            this.head = node;
            return;
        }

        //这里我们需要先进行遍历
        ListNode cur = this.head;
        while(cur.next != null) {
            cur = cur.next;
        }
        //说明这个时候走到了最后一个元素位置
        cur.next = node;
    }
    
    public static void main(String[] args) {
         //2.尾插
        System.out.print("请输入你要添加的元素（尾插）：");
        int data2 = scanner.nextInt();
    
        mySinglyLinkedList.addLast(data2);

        System.out.print("目前的链表元素是：");
        mySinglyLinkedList.display();
    }

        2.3 指定位置插入

public class SizeException extends RuntimeException {
    public SizeException(String message) {
        super(message);
    }
}

    //得到单链表的长度
    @Override
    public int size() {
        int count = 0;

        ListNode cur = this.head;
        while(cur != null) {
            count++;
            cur = cur.next;
        }

        return count;
    }

   //指定位置插入
    @Override
    public void addIndex(int index,int data) {
        //由于不是数组，我们这里规定，第一个节点就是0号位置

        int len = size();
        //表示指定位置有错，那么我们就报错
        if(index < 0 || index > len) {
            throw new SizeException("你指定位置有误");
        }

        ListNode node = new ListNode(data);

        if (index == 0) {
            node.next = this.head;
            this.head = node;
            return;
        }

        //遍历到指定位置的前一个节点
        ListNode cur = this.head;
        for (int i = 0; i < index - 1; i++) {
            cur = cur.next;
        }

        node.next = cur.next;
        cur.next = node;
    }

    public static void main(String[] args) {
        //3.任意位置插入
        System.out.print("请输入你要添加的元素：");
        int data3 = scanner.nextInt();

        System.out.print("请输入你要添加的元素的位置：");
        int index = scanner.nextInt();

        mySinglyLinkedList.addIndex(index,data3);

        System.out.print("目前的链表元素是：");
        mySinglyLinkedList.display();
    }

        在这里有一个小的知识点，就是关于 异常——throws 的小知识点。        

        可能会有人提出疑问，为什么这里不写成：

                addIndex(int index,int data) throws SizeException

        反而写的是：

                addIndex(int index,int data)

        实际上对于非受检异常（运行期检查），我们可以写 throws ，也可以不写，在工程上我们一般是不写的。而对于受检异常（编译期检查），我们必须要写 throws 。

  • 写不写都能编译是Java语言为了区分两种异常的设计

  • 建议不写是为了保持语义清晰：让调用者明白，这是他们的代码写错了，不是运行时需要处理的外部异常（即受检异常）

3.查找指定节点的数据元素
    //数据的查找
    @Override
    public boolean contains(int key) {
        ListNode cur = head;

        //进行遍历
        while(cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }

        return false;
    }    
    
    public static void main(String[] args) {
        //查找链表中是否有指定元素，有的话就打印true
        System.out.print("请输入你要查找的元素：");
        int data4 = scanner.nextInt();
        System.out.println(mySinglyLinkedList.contains(data4));
    }
4.删除节点

        4.1 删除第一次出现关键字为key的节点

    //节点的删除
    private ListNode find(ListNode listNode, int key) {
        //调用这个方法的前提是已经确定了有这个元素了

        ListNode cur1 = listNode;
        ListNode cur2 = listNode;
        //找到指定位置的前一个
        int flag = 0;
        while(cur1 != null) {
            if(key == cur1.val) {
                   break;//表示到了指定位置
            }
            flag++;
            cur1 = cur1.next;
        }

        //这时候flag所代表的数就是该指定位置的位置（默认初始位置是0）
        //走到这里表示知道了这个指定位置的前一个的位置了，那么我们进行遍历
        for (int i = 0; i < flag - 1; i++) {
            cur2 = cur2.next;
        }

        return cur2;
        //这一个方法是这样的：
        //如果删除的元素是第一个，那么返回值就是第一个节点
        //如果删除的元素不是第一个，那么返回值就是该节点的上一个节点

    }
    //1.删除第一次出现关键字为key的节点
    @Override
    public void remove(int key) {
        ListNode cur = this.head;

        //进行遍历
        while(cur != null) {
            if(cur.val == key) {
                ListNode ret = find(this.head, key);

                if(ret == this.head) {
                    //表示的是第一个节点
                    this.head = this.head.next;//删除头节点
                }else {
                    //表示的是非第一个节点
                    ret.next = cur.next;
                }

                //cur = null;置空
                //这一步是没有必要的，因为java不同于c，没有被指向的内存空间会被jvm的GC自动回收

                System.out.println("删除成功");
                return;
            }
            cur = cur.next;
        }
        System.out.println("单链表中没有你要删除的内容");
    }

    public static void main(String[] args) {
        //删除第一次出现为key的节点
        System.out.print("请输入你要删除的元素(删除第一个)：");
        int data5 = scanner.nextInt();

        mySinglyLinkedList.remove(data5);

        System.out.print("目前的链表元素是：");
        mySinglyLinkedList.display();
    }

        4.2 删除全部出现关键字为key的节点

    //2.删除全部出现关键字为key的节点
    @Override
    public void removeAllKey(int key) {
        while (this.head != null && this.head.val == key) {
            this.head = this.head.next;
            //连续去掉匹配的头节点，保证头节点不是指定删除的节点，比如
            //key == 13
            //而链表是：13、13、13、15、85
        }
        if(this.head == null){
            return;
        }

        ListNode cur = this.head.next;
        ListNode prev = this.head;
        while(cur != null) {
            if(cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
    }

    public static void main(String[] args) {//删除全部出现为key的节点
        System.out.print("请输入你要删除的元素（删除所有）：");
        int data6 = scanner.nextInt();

        mySinglyLinkedList.removeAllKey(data6);

        System.out.print("目前的链表元素是：");
        mySinglyLinkedList.display();
    }

        4.3 清空链表

    //删除整个链表
    @Override
    public void clear() {
        while(this.head != null) {
            ListNode cur = this.head.next;
            this.head = cur;
            if(this.head != null) {
                //表示未走到最后一个位置
                cur = this.head.next;
            }
        }
    }
    
    public static void main(String[] args) {
        //清空链表
        System.out.print("接下来是清空后的链表:");
        mySinglyLinkedList.clear();
    }
5.修改节点的元素

       

public class SizeException extends RuntimeException {
    public SizeException(String message) {
        super(message);
    }
}

    //指定位置数据元素的修改
    @Override
    public void exchange(int index, int data) {
        //指定第一个数据节点所在的位置为0
        
        int len = size();
        //表示指定位置有错，那么我们就报错
        if(index < 0 || index > len) {
            throw new SizeException("你指定位置有误");
        }

        ListNode cur = this.head;

        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        //这里说明到了指定的位置了
        cur.val = data;
    }

    public static void main(String[] args) {
        //修改指定位置的元素
        System.out.print("请输入你要修改的元素：");
        int data_e = scanner.nextInt();

        System.out.print("请输入你要修改的元素的位置：");
        int index_e = scanner.nextInt();

        mySinglyLinkedList.exchange(index_e, data_e);

        System.out.print("目前的链表元素是：");
        mySinglyLinkedList.display();
    }

2.2.3 总结

        针对单链表，我们需要记住的是：单链表是用一段物理地址不连续的存储单元依次存储数据元素的线性结构。也就是说我们需要记住的是单链表的结构，至于具体的方法，要根据存储的数据元素的类型来进行改写，对存储不同类型数据元素的单链表的操作并不相同。

2.3 MyDoublyLinkedList（双向不带头非循环链表）

        单链表是“向前看”的简洁设计，当你需要“回头”时，就会付出遍历的代价。而双链表为“回头看”这个能力，多花了一点内存（每个节点需要额外存储一个prev指针）和操作时间（执行具体操作步骤时，需要多做几次指针赋值），换来了更高的灵活性。

        在学习双向链表时，我们不需要有过多压力、认为双向链表很难，其实双向链表的操作在逻辑上和单向链表无异，只是在实操过程中需要多处理一个指针。

2.3.1 基本结构

        双向链表是通过一组物理地址不连续的存储单元（节点）来存储数据元素的线性结构。

        每个节点由数据域（存储元素值）、指针域（存储下一个节点的地址）和另一个指针域（存储上一个节点的地址）组成，节点之间的逻辑顺序通过双向的指针链接实现。整个链表通过头指针（指向第一个节点）来标识，通常也会保留尾指针（指向最后一个节点）以便从尾部操作。第一个节点的“上一个节点”指针指向 NULL，最后一个节点的“下一个节点”指针也指向 NULL，表示链表的边界。

2.3.2 双向链表的增（Create）、删（Delete）、查（Read）、改（Update）——CRUD

1.打印链表
    @Override
    public void display() {
        ListNode cur = this.head;
        while(cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

    public static void main(String[] args) {
        //我们进行打印
        System.out.print("目前的链表元素是：");
        mySinglyLinkedList.display();
    }
2.增加/插入节点

        2.1 头插法

        

    //1.头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);

        if(this.head == null) {
            this.head = this.tail = node;
        }else {
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }
    }

    public static void main(String[] args) {
        //1.头插
        System.out.print("请输入你要添加的元素（头插）：");
        int data1 = scanner.nextInt();

        myDoublyLinkedList.addFirst(data1);

        System.out.print("目前的链表元素是：");
        myDoublyLinkedList.display();
    }

        2.2 尾插法

    //2.尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);

        if(this.head == null) {
            this.head = this.tail = node;
        }else {
            node.prev = this.tail;
            this.tail.next = node;
            this.tail = node;
        }
    }

    public static void main(String[] args) {
        //2.尾插
        System.out.print("请输入你要添加的元素（尾插）：");
        int data2 = scanner.nextInt();

        myDoublyLinkedList.addLast(data2);

        System.out.print("目前的链表元素是：");
        myDoublyLinkedList.display();
    }

        2.3 指定位置插入

    @Override
    public int size() {
        ListNode cur = this.head;
        int flag = 0;
        while(cur != null) {
            flag++;
            cur = cur.next;
        }
        return flag;
    }    

    //3.任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data) {
        int len = this.size();

        if(index < 0 || index > len) {
            throw new SizeException("你指定的位置有错误");
        }

        ListNode node = new ListNode(data);

        if(this.head == null) {
            this.head = this.tail = node;
        }

        ListNode cur = this.head;

        if(index == 0) {
            this.addFirst(data);
            return;
        }else if(index == len){
            this.addLast(data);
            return;
        }else {
            int count = 0;
            while(cur != null) {
                if(count == index) {
                    break;
                }
                count++;
                cur = cur.next;
            }
            //走到这里表示 cur 为指定位置原来的节点
            cur.prev.next = node;
            node.prev = node.prev;
            cur.prev = node;
            node.next = cur;
        }  
    }

    public static void main(String[] args) {
        //3.任意位置插入
        System.out.print("请输入你要添加的元素：");
        int data3 = scanner.nextInt();
        System.out.print("请输入你要添加的元素的位置：");
        int index = scanner.nextInt();

        myDoublyLinkedList.addIndex(index,data3);

        System.out.print("目前的链表元素是：");
        myDoublyLinkedList.display();
    }
3.查找指定节点的数据元素
    //数据的查找
    @Override
    public boolean contains(int key) {
        ListNode cur = head;

        //进行遍历
        while(cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }

        return false;
    }    

    public static void main(String[] args) {
        //查找链表中是否有指定元素，有的话就打印true
        System.out.print("请输入你要查找的元素：");
        int data4 = scanner.nextInt();
        System.out.println(myDoublyLinkedList.contains(data4));
    }
4.删除节点

        4.1 删除第一次出现关键字为key的节点

     //删除第一次出现为key的节点
    @Override
    public void remove(int key) {
        if (this.head == null) {
            System.out.println("当前是空链表，不能进行删除");
        }

        ListNode cur = this.head;

        while(cur.next != null) {
            if(cur.val == key) {
                //走到这里了表示cur就是要删除的节点
                System.out.println("链表中有你要删除的节点,已删除一个");

                if(cur == this.head) {
                    this.head = this.head.next;
                }else if(cur == this.tail) {
                    this.tail = this.tail.prev;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
                break;
            }
            cur = cur.next;
        }

        if(cur == null) {
            //表示遍历到了最后了，但是还是没有找到
            System.out.println("当前链表中没有你要删除的节点");
            return;
        }
    }

    public static void main(String[] args) {
        //删除第一次出现为key的节点
        System.out.print("请输入你要删除的元素（删除第一个）：");
        int data5 = scanner.nextInt();
    
        myDoublyLinkedList.removeAllKey(data5);

        System.out.print("目前的链表元素是：");
        myDoublyLinkedList.display();
    }

        4.2 删除全部出现关键字为key的节点

    //删除全部出现为key的节点
    @Override
    public void removeAllKey(int key) {
        if (this.head == null) {
            System.out.println("当前是空链表，不能进行删除");
        }

        ListNode cur = this.head;

        boolean flag = false;//用来判断链表中是否有指定删除的节点

        while(cur.next != null) {
            if(cur.val == key) {
                //表示找到了
                flag = true;

                if(cur == this.head) {
                    this.head = this.head.next;
                }else if(cur == this.tail) {
                    this.tail = this.tail.prev;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
            }
            cur = cur.next;
        }

        if(flag) {
            System.out.println("链表中有你要删除的节点，已删除所有");
        }
    }
    
    public static void main(String[] args) {
        System.out.print("请输入你要删除的元素（删除所有）：");
        int data6 = scanner.nextInt();
    
        myDoublyLinkedList.removeAllKey(data6);

        System.out.print("目前的链表元素是：");
        myDoublyLinkedList.display();
    }
        4.3 清空链表（需注意）
    //清空链表
    @Override
    public void clear() {
        if(this.head == null) {
            System.out.println("当前链表已是空链表，不需要进行再次清空");
            return;
        }

        ListNode cur = this.head;
        while(cur != null) {
            ListNode curN = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curN;
        }

        this.head = null;
        this.tail = null;
    }

    public static void main(String[] args) {
        System.out.print("接下来是清空后的链表:");

        myDoublyLinkedList.clear();

        myDoublyLinkedList.display();
    }

        以上的清空链表的方法是和 LinkedList 一样原理的，其实我们还有个更简单的方法清空链表，那就是

    //清空链表
    @Override
    public void clear() {
        this.head = null;
        this.tail = null;
    }

    public static void main(String[] args) {
        System.out.print("接下来是清空后的链表:");

        myDoublyLinkedList.clear();

        myDoublyLinkedList.display();
    }

        至于为什么可以这样做，我们来进行详细讲解：

一、数据槽的概念

  1. JVM 底层没有“变量”和“引用”的语义区分：只有 数据槽 (Slot)。它是一个确定大小的存储单元（比如 32 位或 64 位），例 int a ，这个a就是数据槽。

  2. 数据槽里存的都是“值”：这个值就是一段二进制数字。

  3. 区别在于如何解释这个“值”：

    • 存基本类型：这个值就是数据本身。JVM 直接用。

    • 存引用类型：这个值是对象的地址。JVM 把它作为“线索”，去堆里找真正的对象。

  4. 多了的步骤：确实，对于引用类型，JVM 多了 “链接 (reference)” 这一步——通过地址去堆里定位对象。

二、什么在JVM栈上，什么不在JVM栈上

存在 JVM 栈上的说明例子
局部变量方法内部声明的变量ListNode node = new ListNode();
方法参数方法传进来的参数public void addFirst(ListNode newNode) 里的 newNode
操作数栈里的临时值JVM 执行字节码时的中间结果（不需要关心）i++ 过程中的临时值
不在栈上的存在哪例子
成员变量堆head、tail、next、prev
成员方法、静态变量方法区static ListNode cache
对象本身堆new ListNode(10) 创建出来的东西
类定义、方法字节码方法区LinkedList.class

三、GC Roots

        1.什么是 GC Roots？

        GC Roots 是一组必须作为“可达性分析”起点的内存对象。

        用大白话说：GC Roots 就是 JVM 认定“肯定活着”的那批对象，以及能直接找到这些对象的引用入口。

        2.GC Roots干什么的，有什么作用？

        JVM 在进行垃圾回收时，会以 GC Roots 作为根节点，顺着它们的引用链向下查找。所有能被找到的对象都标记为存活；找不到的，就标记为垃圾，等待回收。

        3.怎么判断是不是 GC Roots？

        一个数据槽（内存单元）是 GC Roots，当且仅当：

                （1）它不在堆里

                （2）它里面存的是一个有效的堆内存地址

        这两个条件缺一不可。

四、为啥令 head = tail =null ，就把这个链表回收了

        首先，myDoublyLinkedList 这个数据槽存储在 JVM栈 上，作为GC Root。

                   MyDoublyLinkedList 对象：可达 ✅（因为栈上有 myDoublyLinkedList）

        其次，接着向下找，当发现 head = tail = null 时

                   ListNode 节点们：不可达 ❌（因为head = tail = null ，不能到达 ListNode 对象）

       所以说，ListNode 节点就被一个一个的回收了

5.修改节点的元素
    //修改指定位置的元素
    @Override
    public void exchange(int index_e, int data_e) {
        int len = this.size();

        if (index_e < 0 || index_e > len - 1) {
            //注意这里是修改，不是尾插
            throw new SizeException("你指定的位置有误");
        }

        if (this.head == null) {
            System.out.println("这个表是空表，无法修改元素");
            return;
        }

        ListNode cur = this.head;

        if (index_e == 0) {
            this.head.val = data_e;
            return;
        } else if (index_e == len - 1) {
            this.tail.val = data_e;
            return;
        } else {
            int count = 0;
            while (cur != null) {
                if (count == index_e) {
                    break;
                }
                count++;
                cur = cur.next;
            }
            //cur是指定位置的节点
            cur.val = data_e;
        }
    }

    public static void main(String[] args) {
        //修改指定位置的元素
        System.out.print("请输入你要修改的元素：");
        int data_e = scanner.nextInt();
        System.out.print("请输入你要修改的元素的位置：");
        int index_e = scanner.nextInt();

        myDoublyLinkedList.exchange(index_e, data_e);

        System.out.print("目前的链表元素是：");
        myDoublyLinkedList.display();
    }

3.LinkedList

3.1 LinkedList的简介

        LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

        LinkdeList 采用单继承（extends）、多实现（implement）的结构关系

        实线 + 箭头 ：继承关系（extends）

        虚线 + 箭头 ：实现关系（implement）

3.2 LinkedList的使用

        我们对于LinkedList的使用不进行详细解释，只是对某些地方进行简单的提醒，有兴趣的可以自己去看一看。

3.2.1 LinkedList的基本结构

3.2.2 LinkedList的构造

方法解释
LinkedList()无参构造
LinkedList(Collection<? extends E> c)

使用其他集合容器中元素构造List

public class TestDemo {
    public static void main(String[] args) {
        LinkedList<Integer> li = new LinkedList<>();
        li.add(1);
        li.add(2);
        li.add(3);
        li.add(4);
        System.out.println(li);

        LinkedList<Integer> li1 = new LinkedList<>(li);
        System.out.println(li1);
    }
}

LinkedList() 的含义是：创建了一个链表，但是这个链表初始的时候是空的

LinkedList(Collection<? extends E> c)的含义是：

        1.我们先不要看<? extends E>，也就是LinkedList(Collection c)，这表明了我的参数须是一个实现了Collection接口的数据，而我们的 li 是 LinkdeList 类型的（LinkedList 实现了 Collection 接口）

        2.<? extends E>的意思是我们的链表的操作对象的类型需要是 E 或者 其子类 。我们的 li 的操作对象是 Integer 类型，li1 要求的操作对象需要是 Integer 或者 其子类

        3.这个构造方法的含义就是使用 指定集合容器中的元素 构造LinkedList

3.2.3 LinkedList的遍历

        LinkedList的遍历有三种，分别如下：

1.通过 for循环 进行遍历 

public class TestDemo {
    public static void main(String[] args) {
        LinkedList<Integer> li = new LinkedList<>();
        li.add(1);
        li.add(2);
        li.add(3);
        li.add(4);

        //通过 for循环 进行遍历
        for (int i = 0; i < li.size(); i++) {
            System.out.print(li.get(i) + " ");
        }
    }
}

2.通过 for—each循环 进行遍历    

public class TestDemo {
    public static void main(String[] args) {
        LinkedList<Integer> li = new LinkedList<>();
        li.add(1);
        li.add(2);
        li.add(3);
        li.add(4);

        //通过 for—each循环 进行遍历
        for (int x: li) {
            System.out.print( x + " ");
        }
    }
}

3.通过 迭代器（Iterator/ListIterator） 进行遍历

public class TestDemo {
    public static void main(String[] args) {
        LinkedList<Integer> li = new LinkedList<>();
        li.add(1);
        li.add(2);
        li.add(3);
        li.add(4);

        //通过 迭代器（Iterator/ListIterator）进行遍历
        ListIterator<Integer> it = li.listIterator();
        //正向遍历
        while(it.hasNext()) {
            System.out.print(it.next() + " ");// 1 2 3 4
        }
        //反向遍历
        while(it.hasPrevious()) {
            System.out.print(it.previous() + " ");// 4 3 2 1 
        }
    }
}

        提醒一句：ListIterator 继承了 Iterator ,在 LIstIterator类中多了反向遍历功能相关的方法 

3.2.4 LinkedList的常用方法

方法解释
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
E get(int index)获取下标 index 位置元素
E set(int index, E element)将下标 index 位置元素设置为 element
void clear()清空
boolean contains(Object o)判断 o 是否在线性表中
int indexOf(Object o)返回第一个 o 所在下标
int lastIndexOf(Object o)返回最后一个 o 的下标
List<E> subList(int fromIndex, int toIndex)截取部分 list

4.ArrayList 和 LinkedList

不同点ArrayListLinkedList
存储空间上物理上一定连续逻辑上连续，但物理上不一定连续
随机访问支持 O(1)不支持：O(N)
头插需要搬移元素，效率低 O(N)只需修改引用的指向，时间复杂度为 O(1)
插入需要搬移元素，效率低 O(N)只需修改引用的指向，时间复杂度为 O(1)
扩容空间不够时需要扩容没有容量的概念
应用场景元素高效存储 + 频繁访问任意位置插入和删除频繁
# 数据结构
Logo
AI编程社区

汇聚全球AI编程工具，助力开发者即刻编程。

更多推荐

cover

码道 · 寻艺——从零构建“非遗交互式对话平台“的完整实践

avatar AI编程社区

码道：用 Python + FastAPI 快速构建一个学生信息管理接口：从零到 Swagger 在线文档

在日常开发和教学中，我们经常需要一套简单、可控、能快速上手的后端接口来演示"前后端分离"、练习 Restful API 设计，或者作为前端联调的 Mock 服务。传统做法往往是搭一套完整的 Web 工程：配置数据库、编写 DAO、引入 ORM、做请求分发……一套流程下来，光环境搭建就要花去不少时间，对于想快速验证想法、或者刚入门 API 开发的同学来说，显得过于沉重。

avatar AI编程社区

码道：从零构建学生信息管理系统 API：FastAPI 内存版 CRUD 项目全解析

FastAPI 的强大，很大程度上来自 Pydantic 的校验能力。我们写下类型声明，FastAPI 在运行时自动把它变成边界检查器。name：字符串，长度限制 1 到 50；age：整数，限制在 6 到 120 之间（ge大于等于、le小于等于）；gender：字符串，用正则限定只能是"男"“女”“其他”；email：邮箱格式字符串；grade与major：可选字段，代表班级和专业方向。

avatar AI编程社区