上篇博客，我们已经认识了链表：链表讲解博客
现在我们来熟悉集合类LinkedList：

一、LinkedList的使用

1.1 什么是LinkedList

LinkedList 的官方文档

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

在集合框架中，LinkedList也实现了List接口，具体如下：

【说明】

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

1.2 LinkedList的使用

1.2.1 LinkedList的构造

1.2.2 LinkedList的其他常用方法介绍

1.2.3 LinkedList的遍历

二、LinkedList的模拟实现

LinkedList底层就是一个无头双向链表，我们来实现一个双向链表。

public class MyLinkedList {
    // 内部类 ListNode:
    static class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;   // 标记双向链表的头部
    public ListNode tail;   // 标记双向链表的尾部

    public void display(){
        ListNode cur = this.head;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

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

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = this.head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        if(this.head == null){
            this.head = node;
            this.tail = node;
        }else{
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }
    }

    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if(this.head == null){
            this.head = node;
            this.tail = node;
        }else{
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
        }
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        // 1.判断index的合法性
        if(index < 0 || index > this.size()){
            throw new IndexWrongfulException("index位置不合法!!!");
        }
        // 2.特殊位置插入
        if(index == 0){
            this.addFirst(data);
            return;
        }
        if(index == this.size()){
            this.addLast(data);
            return;
        }
        // 3.找到index位置节点的地址
        ListNode cur = this.findIndexListNode(index);
        // 4.修改4个指向（多种方式！）
        // 以下代码是先修改插入节点node的两个指向
        ListNode node = new ListNode(data);
        node.next = cur;
        node.prev = cur.prev;
        cur.prev.next = node;
        cur.prev = node;
    }

    private ListNode findIndexListNode(int index){
        ListNode cur = this.head;
        while(index != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key){
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                // 两端要单独考虑！
                if(cur == head){
                    // 只有一个节点的情况要单独考虑！
                    if(cur.next == null){
                        head = null;
                        tail = null;
                        return;
                    }else {
                        head = head.next;
                        head.prev = null;
                        return;
                    }
                } else if (cur == tail) {
                    tail = tail.prev;
                    tail.next = null;
                    return;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                    return;
                }
            }else{
                cur = cur.next;
            }
        }
    }

    //删除所有值为key的节点
    public void removeAllKey(int key){

        // remove删完之后不return，就会继续往后删!!!

        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                // 两端要单独考虑！
                if(cur == head){
                    // 只有一个节点的情况要单独考虑！
                    if(cur.next == null){
                        head = null;
                        tail = null;
                    }else {
                        head = head.next;
                        head.prev = null;
                    }
                } else if (cur == tail) {
                    tail = tail.prev;
                    tail.next = null;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
            }
            cur = cur.next;
        }
    }

    public void clear(){
        // 双向链表：不能只head和tail置空（中间的节点在互相指向）
        ListNode cur = head;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curNext;
        }
        // 还要修改head和tail的引用指向！！！
        head = null;
        tail = null;
    }

}

public class IndexWrongfulException extends RuntimeException{
    public IndexWrongfulException() {
    }

    public IndexWrongfulException(String message) {
        super(message);
    }
}

public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addFirst(3);
        myLinkedList.addFirst(2);
        myLinkedList.addLast(4);
        myLinkedList.addLast(5);
        myLinkedList.addFirst(1);
        myLinkedList.addIndex(2,6);
        myLinkedList.remove(4);
        myLinkedList.display();
        System.out.println(myLinkedList.size());
        System.out.println("=================================================");
        myLinkedList.clear();
        myLinkedList.display();
    }
}

三、ArrayList和LinkedList的区别

提示：
XXXX和XXXX的区别？从共性出发去回答这个问题！！！

1. 增删查改
   插入元素的时候：
   顺序表：比如往0下标位置插入，时间复杂度O(N)……【随机访问】；
   链表：O(1)：修改指向就可以了。
   总结：顺序表适合随机访问的情况；链表适合插入和删除比较频繁的情况。
2. 存储上来说
   顺序表：数组->连续的内存->扩容可能会浪费空间；
   链表：随用随取。