1 LinkedList的概念

LinkedList本质上是一个双向链表。

那么什么是链表呢？链表原先是C/C++的概念，是一种线性的存储结构，意思是将要存储的数据存在一个存储单元里面，这个存储单元里面除了存放有待存储的数据以外，还存储有其下一个存储单元的地址（下一个存储单元的地址是必要的，有些存储结构还存放有其前一个存储单元的地址），每次查找数据的时候，通过某个存储单元中的下一个存储单元的地址寻找其后面的那个存储单元。

而LinkedList是双向链表，在list中的每个元素，在存储自身元素外，还额外存储了其前一个和后一个元素的地址，所以 也就可以很方便地根据当前元素获取到其前后的元素。链表的尾部元素的后一个节点是链表的头节点；而链表的头结点前一个节点则是则是链表的尾节点。

由于LinkedList的底层是双向链表，因此其顺序访问的效率非常高，而随机访问的效率就比较低了，因为通过索引去访问的时候，首先会比较索引值和链表长度的1/2，若前者大，则从链表尾开始寻找，否则从链表头开始寻找，这样就把双向链表与索引值联系起来了。

2 LinkedList的定义

根据LinkedList的声明代码，可以看到它除了实现List接口外，还实现了Deque接口，而Deque主要是一个双端队列，因此LinkedList除了可以作为List使用外，还可以当做队列使用。 ?

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

3 LinkedList的使用

（1）LinkedList的构造

// 1.无参构造       
LinkedList()
//2.使用其他集合容器中的元素构造List      
public LinkedList(Collection<? extends E> c)

代码如下：

public static void main(String[] args) {
    // 构造一个空的LinkedList
    List<Integer> list1 = new LinkedList<>();
    List<String> list2 = new java.util.ArrayList<>();
    list2.add("JavaSE");
    list2.add("JavaWeb");
    list2.add("JavaEE");
    // 使用ArrayList构造LinkedList
    List<String> list3 = new LinkedList<>(list2);
}

（2）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

代码如下：

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());
    System.out.println(list);
    // 在起始位置插入0
    list.add(0, 0); // add(index, elem): 在index位置插入元素elem
    System.out.println(list);
    list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()
    list.removeFirst(); // removeFirst(): 删除第一个元素
    list.removeLast(); // removeLast(): 删除最后元素
    list.remove(1); // remove(index): 删除index位置的元素
    System.out.println(list);
    // contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false
    if(!list.contains(1)){
        list.add(0, 1);
    }
    list.add(1);
    System.out.println(list);
    System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
    System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
    int elem = list.get(0); // get(index): 获取指定位置元素
    list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
    System.out.println(list);
    // subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
    List<Integer> copy = list.subList(0, 3); 
    System.out.println(list);
    System.out.println(copy);
    list.clear(); // 将list中元素清空
    System.out.println(list.size());
}

（3） LinkedList的遍历

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();
}

（4）LinkedList的模拟实现

代码如下：

public class MyLinkedList {
    static class LinkedList {
        public int val;
        public LinkedList prev;
        public LinkedList next;
        public LinkedList(int val) {
            this.val = val;
        }

    }
        public LinkedList head;
        public LinkedList last;
    // 2、无头双向链表实现
        //头插法
        public void addFirst(int data){
            LinkedList node = new LinkedList(data);
            if(head==null) {
                head = node;
                last = node;
            } else {
                head.prev = node;
                node.next = head;
                head = node;
            }
        }
        //尾插法
        public void addLast(int data){
            LinkedList node = new LinkedList(data);
            if(head==null) {
                head=node;
                last=node;
            } else {
                last.next=node;
                node.prev=last;
                last = node;
            }

        }
        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index,int data){
            if(index<0 || index>size()) {
                System.out.println("位置不合法");
            }
            if(index==0) {
                addLast(data);
                return;
            }
            if(index==size()) {
                addLast(data);
                return;
            }

            LinkedList node = new LinkedList(data);
            LinkedList cur = findIndex(index);
            node.next = cur;
            cur.prev.next = node;
            node.prev = cur.prev;
            cur.prev=node;
        }

        public LinkedList findIndex(int index) {
            LinkedList cur = head;
            while (index!=0) {
                cur = cur.next;
                index--;
            }
            return cur;
        }
        //查找是否包含关键字key是否在链表当中
        public boolean contains(int key){
            LinkedList cur = head;
            while (cur!=null) {
                if(cur.val==key) {
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }
        //删除第一次出现关键字为key的节点
        public void remove(int key){
            LinkedList cur = head;
            while (cur!=null) {
                if(cur.val==key) {
                    //头节点
                    if(cur==head) {
                        head = head.next;
                        if (head!=null) {
                            head.prev = null;
                        }
                    } else {
                        //中间 节点和 尾部节点
                        cur.prev.next = cur.next;
                        if(cur.next!=null) {
                            //中间
                            cur.next.prev = cur.prev;
                        }else {
                            //尾部
                            last = last.prev;
                        }
                    }
                    return;
                }
                cur=cur.next;
            }
        }
        //删除所有值为key的节点
        public void removeAllKey(int key){
            LinkedList cur = head;
            while (cur!=null) {
                if(cur.val==key) {
                    //头节点
                    if(cur==head) {
                        head = head.next;
                        if (head!=null) {
                            head.prev = null;
                        }
                    } else {
                        //中间 节点和 尾部节点
                        cur.prev.next = cur.next;
                        if(cur.next!=null) {
                            //中间
                            cur.next.prev = cur.prev;
                        }else {
                            //尾部
                            last = last.prev;
                        }
                    }
                }
                cur=cur.next;
            }
        }
        //得到的长度
        public int size(){
            int len = 0;
            LinkedList cur = head;
            while (cur!=null) {
                len++;
                cur=cur.next;
            }
            return len;
        }
        public void display(){
            LinkedList cur = head;
            while (cur!=null) {
                System.out.print(cur.val+" ");
                cur=cur.next;
            }
            System.out.println();
        }
        public void clear(){
            LinkedList cur = head;
            while (cur!=null) {
                LinkedList curNext = cur.next;
                cur.prev = null;
                cur.next = null;
                cur = curNext;
            }
            head=null;;
            last=null;
        }

}

3 常用的方法

4 ArrayList和LinkedList的区别

• 在存储空间上，ArrayList在物理上一定连续，LinkedList在逻辑上连续，但物理上不一定连续
• ArrayList支持随机访问，时间复杂度为O(1)，但是LinkedList不支持，时间复杂度为O(N)
• ArrayList在头插时需要搬移元素，效率低O(N)，LinkedList只需要修改引用的指向，时间复杂度为O(1)
• ArrayList在插入时空间不够时需要扩容，但是LinkedList没有容量的概念
• ArrayList应用于“元素高效存储和频繁访问”，LinkedList应用于“任意位置插入和删除频繁”