数组和链表

数组和链表—-《算法图解》
https://blog.csdn.net/qq_25806863/article/details/70607204

数组

特性

• 线性表
• 连续的内存空间和相同类型
  • 下标查找的时间复杂度是O(1)
• 低效的插入和删除
  • 尾部的插入时间复杂度是O(1)
  • 删除可以使用标记删除的方式优化

容器和数组

ArrayList
优点：
ArrayList 最大的优势就是可以将很多数组操作的细节封装起来。比如前面提到的数组插入、删除数据时需要搬移其他数据等。另外，它还有一个优势，就是支持动态扩容。
缺点：
Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。

链表

特性

• 不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用
• O(1)的插入和删除

• O(n)的查找操作

  链表分类

• 单向链表

• 循环链表
  • 用来解决特殊问题，如约瑟夫问题
• 双向链表
  • 让每一个节点持有一个指向他在表中的前驱节点的链
  • 相比于单向链表，指定节点的插入删除，及一些遍历操作更高效，使用也更广泛
  • 可以实现LRU，jdk相对较优的LRU实现可以用LinkedHashMap。

Java Collections API 中的表

Collection接口

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Collection.html
Collection接口扩展了Iterable接口

Iterator接口

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Iterator.html

why Iterator的remove方法，而不是Collection的remove?

1. Collection的remove方法需要先找到要被删除的项。如果知道所要删除的项的准确位置，那么删除它的开销很可能小很多，如果像是在集合中每隔一项删除一项，用迭代器（iterator）很容易编写，而且有更高的效率。

2. 当直接使用Iterator（而不是通过一个增强的for间接使用）时，一个基本法则就是：如果正在被迭代的集合进行结构上的改变（即对该集合使用add,remove,clear），那么迭代器就不再合法。所以，只有在需要立即使用一个迭代器的时候，我们才应该获取迭代器，但是如果迭代器调用自己的remove方法，那么这个迭代器仍然是合法的。

   List接口

   https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/List.html
   List接口继承了Collection接口
   

   List ADT 的实现方式——ArrayList

   优点

   对get和set的调用花费常数时间

   缺点

   新项的插入和现有项的删除代价昂贵

   List ADT 的实现方式——LinkedList

   https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/LinkedList.html

   class LeetCodeTest {
    //创建一个链表的类
    static class ListNode {
        int val;    //数值 data
        ListNode next;    // 结点 node
        ListNode(int x) {    //可以定义一个有参构造方法，也可以定义一个无参构造方法
            val = x;
        }
        public ListNode() {
        }
        // 添加新的结点
        public void add(int newVal) {
            ListNode newNode = new ListNode(newVal);
            if (this.next == null)
                this.next = newNode;
            else
                this.next.add(newVal);
        }
        // 打印链表
        public void print() {
            System.out.print(this.val);
            if (this.next != null) {
                System.out.print("-->");
                this.next.print();
            }
        }
    }
    public static void main(String[] args) {
        ListNode l1 = new ListNode();    //创建链表对象 l1 （对应有参 和 无参 构造方法）
        ListNode l2 = new ListNode();
        l1.add(2);                //插入结点，打印
        l1.add(3);
        l2.val = 3;
        l1.print();
        System.out.println();
        l2.print();
    }
   }

   

   优点

   新项的插入和现有项的删除均开销很小（假设变动项的位置是已知的）

   缺点

   不容易作索引，对get的调用昂贵

   LinkedList实现

ArrayList与LinkedList的比较

| |

ArrayList

|

LinkedList

| | —- | —- | —- | | 搜索（对于Collection的contains和remove两个方法） | 低效：线性时间 | 低效：线性时间 | | | | |

例子：remove 删除表中偶数项

1、暴力法

| |

ArrayList

|

LinkedList

| | —- | —- | —- | | 遍历，删除。get+remove | remove效率不高：O（n²） | get效率不高：O（n²）。对remove同样低效，达到位置i的代价十分昂贵 |

public static void removeEvensVer1(List<Integer> lst){
    int i = 0;
    while(i < lst.size()){
        if(lst.get(i) % 2 == 0){
            lst.remove(i);
        }else{
            i++;
        }
    }
}

2、抛弃低效的get，使用迭代器遍历表

迭代器是高效的，但是使用Collection的remove方法来删除不是高效操作，因为remove必须再次搜索该项，花费线性时间。更糟糕的情况是，当一个项被删除时，增强for所使用的基础迭代器是非法的。

public static void removeEvensVer2(List<Integer> lst){
    for(Integer x : lst){
        if( x%2 == 0){
            lst.remove(x);
        }
    }
}

3、与2相同，但是使用迭代器来删除它刚看到的值

public static void removeEvensVer3(List<Integer> lst){
    Iterator<Integer> itr = lst.iterator();
    while(itr.hasNext()){
        if(itr.next() % 2 == 0){
            itr.remove();
        }
    }
}

ListIterator接口

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/ListIterator.html

方法previous和hasPrevious使得对表从后向前的遍历得以完成。

特性

1. 从 Java 1.2 开始，可以使用ListIterator。
2. ListIterator扩展了Iterator接口。
3. ListIterator仅适用于List实现的类。
4. 与Iterator不同，ListIterator支持在元素列表上的所有 CRUD 操作（创建，读取，更新和删除啊）。
5. 与Iterator不同，ListIterator是双向。 它支持正向和反向迭代。
6. 它没有当前元素； 它的光标位置始终位于通过调用previous()返回的元素和通过调用next()返回的元素之间。

   ListIterator<T> listIterator = list.listIterator();