9_Java集合

链表概述

• 单链表

• 双链表

链表的四种操作（单链表为例）

• 访问 Access 时间复杂度 O(N)
  遍历从前往后一个个找，从而进行访问
• 搜索 Search 时间复杂度 O(N)
  需要对链表进行遍历查找
• 插入 Insert 时间复杂度 O(1)

前元素指向插入元素，插入元素指向后一个元素

• 删除 Delete 时间复杂度 O(1)
  前元素指向后元素，跳过要删除的元素即可

链表特点

• 不适合读，读很慢
• 适合频繁做增删操作
• 场景：读少写多

链表实际的常用操作（Java）

• 创建链表

        //Create a LinkedList 
        LinkedList<Integer> list = new LinkedList<>();

• 添加元素

        //Add element 尾端添加
        //Time Complexity:O(1)
        list.add(1);
        list.add(2);
        list.add(3);
        //[1,2,3]
        System.out.println(list.toString());
        //Insert element 先找后插入
        //Time Complexity:O(N)
        list.add(2, 99);
        //[1,2,99,3]
        System.out.println(list.toString());

• 访问元素

        //Access Element
        //Time Complexity:O(N)
        int element = list.get(2);
        //99
        System.out.println(element);

• 搜索元素

        //Search element
        //Time complexity:O(N)
        int index = list.indexOf(99);
        //2
        System.out.println(index);

• 更新元素

        //Update element
        //Time Complexity:O(N)
        list.set(2, 88);
        //[1,2,88,3]
        System.out.println(list.toString());

• 删除元素

        //Remove element 先找再删除
        //Time Complexity:O(N)
        list.remove(2);
        //[1,2,3]
        System.out.println(list.toString());

• 长度

        //Length
        //Time Complexity:O(1)
        int length = list.size();
        //3
        System.out.println(length);

LeetCode练习

#203

#206

参考：https://www.bilibili.com/read/cv8585621?spm_id_from=333.788.b_636f6d6d656e74.18