1. ArrayList

1.1 ArrayList简介

在集合框架中，ArrayList是一个普通的类，实现了List接口
说明：

1. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
2. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
3. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
4. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者
   CopyOnWriteArrayList
5. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

1.2 ArrayList常见操作

1.3 ArrayList的遍历

ArrayList 可以使用三种方式遍历：for循环+下标、foreach、使用迭代器

public static void main(String[] args) {
    
 List<Integer> list = new ArrayList<>();
 list.add(1);
 list.add(2);
 list.add(3);
 list.add(4);
 list.add(5);
 // 1.使用下标+for遍历
 for (int i = 0; i < list.size(); i++) {
    
 System.out.print(list.get(i) + " ");
 }
 System.out.println();
 // 2.借助foreach遍历
 for (Integer integer : list) {
    
 System.out.print(integer + " ");
 }
 System.out.println();
 //3.使用迭代器
 Iterator<Integer> it = list.listIterator();
 while(it.hasNext()){
    
 System.out.print(it.next() + " ");
 }
 System.out.println();
}

1.4 ArrayList 的扩容机制

1. 检测是否真正需要扩容，如果是调用grow准备扩容
2. 预估需要库容的大小
   初步预估按照1.5倍大小扩容
   如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
   真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
3. 使用copyOf进行扩容

1.5 ArrayList的模拟实现

import java.util.Arrays;

public class ArrayList<E>{
    
    //ArrayList的模拟实现
    private Object[] array;
    private int size;
    //构造方法
    public ArrayList(){
    

    }
    public ArrayList(int initCapacity){
    
        if(initCapacity>0){
    
            array = new Object[initCapacity];

        }else if(initCapacity ==0){
    
            array = new Object[0];
        }else{
    
            throw new IllegalArgumentException("初始容量为负数");
        }
    }
    public int size(){
    
        return size;
    }
    public boolean isEmpty(){
    
        return  0 == size;
    }
    //尾插
    public  boolean add(E e){
    
        ensureCapacity(size+1);
        array[size++] = e;
        return  true;
    }
    //在指定位置插入元素e
    public void add(int index,E e){
    
        rangeCheckForAdd(index);
        ensureCapacity(size+1);
        //将index及其后面的元素统一往后搬移一个位置
        for(int i =size-1;i>=index;i--){
    
            array[i+1] = array[i];
        }
        array[index] = e;
        size++;
    }

    //删除index位置上的元素
    public E remove(int index){
    
        rangeCheck(index);

         E e = (E)array[index];
         //将index之后的元素统一往前搬移一个位置
        for(int i =index+1;i<size;i++){
    
            array[i-1] = array[i];
        }
        size--;
        return e;
    }
    //如果o存在，则删除
    public boolean remove(Object o){
    
        int index = indexOf(o);
        if(index == -1){
    
            return false;
        }
        remove(index);
        return true;
    }
    //检测下标是否异常
    private void rangeCheck(int index){
    
        if(index <0 ||index>=size){
    
            throw new IndexOutOfBoundsException("下标越界");
        }
    }

    //检测插入时下标是否异常
    private void rangeCheckForAdd(int index){
    
        if(index>size){
    
            throw new IllegalArgumentException("add下标越界");
        }
    }
    //获取index位置上的元素
    public E get(int index){
    
        rangeCheck(index);
        return (E)array[index];
    }

    //将index位置上的元素设置为e
    public E set(int index,E e){
    
        rangeCheck(index);
        array[index] = e;
        return e;
    }
    //清空
    public void clear(){
    
        for(int i =0;i<size;i++){
    
            array[i] =null;
        }
        size =0 ;
    }
    //获取o第一次出现的位置
    public int indexOf(Object o){
    
        if(null == o){
    
            for(int i =0;i<size;i++){
    
                if(array[i] == null){
    
                    return i;
                }
            }
        }else{
    
            for(int i =0;i<size;i++){
    
                if(array[i].equals(o)){
    
                    return i;
                }
            }
        }
        return -1;
    }

    //获取o最后一次出现的位置
    int lastIndexOf(Object o){
    
        if(o==null){
    
            for(int i =size-1;i>=0;i--){
    
                if(array[i] == null){
    
                    return i;
                }
            }
        }else{
    
            for(int i =size-1;i>=0;i--){
    
                if(array[i].equals(o)){
    
                    return i;
                }
            }
        }
        return -1;
    }
    //检测o是否存在
    public boolean contains(Object o){
    
        return indexOf(o)>0;
    }
    //获取[from,to)的一个子序列
    ArrayList<E> subList(int fromIndex,int toIndex){
    
        if(toIndex-fromIndex<0){
    
            throw new IllegalArgumentException("参数非法");
        }

    ArrayList<E> list = new ArrayList<>(toIndex-fromIndex);
        for(int i =fromIndex;i<toIndex;i++){
    
            list.add((E)array[i]);
        }
        return list;
    }
    //扩容
    private  static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE-8;
    private void ensureCapacity(int initCapacity){
    
        int oldCapacity = array.length;
        int newCapacity = oldCapacity+(oldCapacity>>1);
        if(newCapacity<initCapacity){
    
            newCapacity = initCapacity;
        }
        if(newCapacity >MAX_ARRAY_SIZE){
    
            newCapacity = MAX_ARRAY_SIZE;
        }
        array = Arrays.copyOf(array,newCapacity);
    }

    @Override
    public String toString() {
    
        String s ="[";
        if(size>0){
    
            for(int i =0;i<size-1;i++){
    
                s+= array[i];
                s+= ",";
            }
            s += array[size-1];
        }
        s+="]";
        return s;
    }
}

2.LinkedList

2.1 LinkedList简介

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

1. LinkedList实现了List接口
2. LinkedList的底层使用了双向链表
3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)

2.2 LinkedList常用方法

2.3 LinkedList的遍历

使用foreach遍历或者迭代器

public static void main(String[] args) {
    
 LinkedList<Integer> list = new LinkedList<>();
 list.add(1); // add(elem): 表示尾插
 list.add(2);
 list.add(3);
 list.add(4);
 list.add(5);
 list.add(6);
 list.add(7);
 System.out.println(list.size());
 // foreach遍历
 for (int e:list) {
    
 System.out.print(e + " ");
 }
 System.out.println();
 // 使用迭代器遍历---正向遍历
 ListIterator<Integer> it = list.listIterator();
 while(it.hasNext()){
    
 System.out.print(it.next()+ " ");
 }
 System.out.println();
 // 使用反向迭代器---反向遍历
 ListIterator<Integer> rit = list.listIterator(list.size());
 while (rit.hasPrevious()){
    
 System.out.print(rit.previous() +" ");
 }
 System.out.println();
}

2.4 LinkedList的模拟实现

import java.util.List;

public class LinkedList <E>{
    
    //双向链表结点的结构
    public static class ListNode<E>{
    
        E elem;
        ListNode<E> next;
        ListNode<E> prev;
        public ListNode(E e){
    
            elem = e;
        }
    }
    ListNode<E> first;
    ListNode<E> last;
    int size = 0;
    public LinkedList(){
    

    }
    //头插法
    public void addFirst(E e){
    
        ListNode<E> newNode = new ListNode<>(e);
        if(null == first){
    
            //1.为空
            last = newNode;

        }else{
    
            //2.不为空
            first.prev = newNode;
            newNode.next = first;
        }
        first = newNode;
        size++;
    }
    //尾插
    public void addLast(E e){
    
        ListNode<E> newNode = new ListNode<>(e);
        if(null == first){
    
            //1.为空
            first = newNode;
        }else{
    
            //2.不为空
            last.next = newNode;
            newNode.prev = last;
        }
        last = newNode;
        size++;
    }
    //头删
    public void removeFirst(){
    
        if(null == first){
    
            return;
        }else if(first == last){
    
            //链表中只有一个结点
            first = null;
            last = null;

        }else{
    
            //链表中至少有两个结点
            first = first.next;
            first.prev =null;
        }
        size--;
    }

    //尾删
    public void removeLast(){
    
        if(first == null){
    
            return;
        }else if(first == last){
    
            first = null;
            last = null;
        }else{
    
            last = last.prev;
            last.next=null;
        }
        size--;
    }
    //将e尾插到链表中
    public void add(E e){
    
        addLast(e);
    }
    //任意位置插入，第一个数据结点为0号下标
    public boolean addIndex(int index,E e){
    
        //参数进行检测
        if(!(index>=0) && index<= size){
    
            throw new IndexOutOfBoundsException("addIndex:下标越界");
        }
        if(index == size){
    
            addLast(e);
        }else {
    
            ListNode<E> cur = null;
            //标准库中大佬的实现
            if(index<((size)>>1)){
    
                //index表示的结点在前一半当中--从前往后找
                cur = first;
                for(int i =0;i<index;i++){
    
                    cur = cur.next;
                }
            }else{
    
                //index表示的结点在后一半当中
                cur = last;
                for(int i =size-1;i>index;i--){
    
                    cur = cur.prev;
                }
            }
            if(cur == first){
    
                addFirst(e);
            }else {
    
                ListNode<E> newNode = new ListNode<>(e);
                //2.在插入新节点
                //a.在不断开原链表的情况下，先将新结点链接到链表中
                newNode.prev = cur.prev;
                newNode.next = cur;
                //b.再将链表断开，将newNode链接进来
                newNode.prev.next = newNode;
                cur.prev = newNode;
                size++;
            }
        }
        return true;
    }
    //查找关键字e是否在链表中
    public boolean contains(E e){
    
        return indexOf(e) !=-1;
    }
    public int indexOf(E e){
    
        ListNode<E> cur = first;
        int index =0;
        while (cur!=null){
    
            if(e.equals(cur.elem)){
    
                return index;
            }
            index++;
            cur = cur.next;
        }
        return -1;
    }
    //从后往前找第一个只出现一次的e的位置
    public int lastIndexOf(E e){
    
        ListNode<E> cur = last;
        int index = size -1;
        while (cur!=null){
    
            if(e.equals(cur.elem)){
    
                return index;
            }
            cur = cur.prev;
            index--;
        }
        return  -1;
    }
    // 删除链表中值为e的元素---从前往后找，找到第一个为e的元素将其删除
    public boolean remove(E e){
    
        // 1. 找e对应的节点
        ListNode<E> cur = first;
        while(cur != null){
    
            if(e.equals(cur.elem)){
    
                break;
            }

            cur = cur.next;
        }

        if(cur == null){
    
            return false;
        }
        // 2. 删除该节点
        if(cur == first){
    
            // 头删
            removeFirst();
        }else if(cur == last){
    
            // 尾删
            removeLast();
        }else{
    
            // 任意位置的删除
            cur.prev.next = cur.next;
            cur.next.prev = cur.prev;
            size--;
        }

        return true;
    }

    public int size(){
    
        return size;
    }

    public boolean isEmpty(){
    
        // return 0 == size;
        return first == null;
    }
    @Override
    public String toString() {
    
        String s = "[";
        if(first == null){
    
            s += "]";
            return s;
        }

        ListNode<E> cur = first;
        while(cur.next != null){
    
            s += cur.elem;
            s += ",";
            cur = cur.next;
        }

        // 拼接最后一个节点中的值域
        s += cur.elem;
        s += "]";
        return s;
    }

}

3. 链表

3.1链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

注意：

1. 链式结构在逻辑上是连续的，但是在物理上不一定连续
2. 现实中的结点一般都是从堆上申请出来的
3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

链表的结构有非常多情况，下面的情况组合起来有8种链表结构
1.单向或者双向
2.带头或者不带头
3.循环或者非循环

重点掌握两种：

• 无头单向非循环链表：结构简单，一般不会单独用来存数据，实际中更多的是作为其他数据结构的子结构，如哈希桶、图的邻接表等等
• 无头双向链表，在java的集合框架中LinkedList底层实现就是无头双向循环链表。

3.2 链表的实现

public class SingleLinkedList <E> {
    
    public static class Node<E> {
    
        E value;
        Node<E> next;

        public Node(E value) {
    
            this.value = value;
        }
    }

    Node<E> head;

    //头插法
    public void addFirst(int data) {
    
        Node<E> newNode = new Node(data);
        if (null == head) {
    
            head = newNode;
        } else {
    
            newNode.next = head;
            head = newNode;
        }
    }

    //尾插法
    public void addLast(int data) {
    
        Node<E> newNode = new Node(data);
        if (head == null) {
    
            head = newNode;
        } else {
    
            //1.找最后一个结点
            Node<E> cur = head;
            while (null != cur.next) {
    
                cur = cur.next;
            }
            cur.next = newNode;
        }

    }

    //任意位置插入，第一个数据结点为0号下标
    public boolean addIndex(int position, int data) {
    
        //1.检测测试是否合法
        if (position < 0 || position >= 4) {
    
            throw new IllegalArgumentException("addIndex:position非法");
        }
        if (position == 0) {
    
            addFirst(data);
            return true;
        }
        //2.找到index位置的结点，保存其前一个
        Node<E> cur = head;
        Node<E> prev = null;
        while (position != 0) {
    
            prev = cur;
            cur = cur.next;
            position--;
        }
        //3.插入新结点
        Node<E> newNode = new Node(data);
        newNode.next = cur;
        prev.next = newNode;
        return true;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(E e) {
    
        Node<E> cur = head;
        while (cur != null) {
    
            if (e.equals(cur.value)) {
    
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //得到单链表的长度
    public int size() {
    
        Node<E> cur = head;
        int count = 0;
        while (null != cur) {
    
            count++;
            cur = cur.next;
        }
        return count;
    }

    public String toString() {
    
        Node<E> cur = head;
        String str = "[";
        while (cur != null) {
    
            str += cur.next;
            if (cur.next != null) {
    
                str += ",";
            }
            cur = cur.next;
        }
        str += "]";
        return str;
    }
    //删除第一次出现关键字为key的结点
    public void remove(E e){
    
        Node<E> cur = head;
        Node<E> prev = null;
        while (cur!= null){
    
            if(e.equals(cur.value)){
    
                //删除结点
                //注意，可能删除的是第一个结点，也可能是其他结点
                cur.value = null;
                if(prev == null){
    
                    //删除第一个结点
                    head = cur.next;
                }else{
    
                    prev.next = cur.next;
                }
                return;
            }
            prev = cur;
            cur = cur.next;
        }
    }
    //删除所有值为key的结点
    public void removeAllkey(E e){
    
        Node<E> cur = head;
        Node<E> prev = null;
        while (cur!= null) {
    
            if (e.equals(cur.value)) {
    
                //删除结点
                cur.value = null;
                if (prev == null) {
    
                    head = cur.next;
                    cur = head;
                } else {
    
                    prev.next = cur.next;
                    cur = prev.next;
                }
            } else {
    
                prev = cur;
                cur = cur.next;
            }
        }
    }
}

4. ArrayList和LinkedList的区别

1. 是否保证线程安全：ArrayList和LinkedList都是不同步的，也就是不保证线程安全；
2. 底层数据结构：ArrayList底层使用的是Object数组；LinkedList底层使用的是双向链表数据结构（JDK1.6之前使用的是循环链表，1.7取消了循环，注意双向链表和双向循环链表的区别）
3. 插入和删除是否受元素位置的影响：
   （1）ArrayList任意位置插入和删除元素时，就需要将后续元素整体搬移，时间复杂度为O（N），效率较低
   （2）LinkedList任意位置插入和删除元素时，不受元素位置的影响，效率比较高，时间复杂度为O（1）；
4. 是否支持随机访问：LinkedList不支持高效的随机访问，而ArrayList支持。快速随机访问就是通过元素的序号快速获取元素对象。
5. ArrayList需要扩容，LinkedList没有扩容的概念
6. ArrayList缓存利用率高