前言

上一篇文章中，介绍了List接口以及ArrayList的使用，并且进行了简单的模拟实现，通过源码知道，ArrayList底层使用数组元素来存储元素。但是由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，且频繁的扩容会导致不必要的内存空间浪费，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构。

一、链表概念及结构

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

链表的结构非常多样，单向双向、带头或不带头、循环或非循环。这几种情况组合起来就有八种链表结构：

1.单向或者双向

2.带头或不带头

3.循环或非循环

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多

无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

二、LinkedList与链表

1.什么是LinkedList

LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。但是当需要查询时，就需要按图索骥按部就班的一个一个查，查询效率不高，这个后面总结对比时再详细说明。

说明：

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

2.LinkedList的常用方法

3.链表的遍历

遍历链表的几种方式：

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

三.实现自己的LinkedList

首先需要定义自己的MyList接口，接口中声明一系列方法后在MyLinkedList中实现，我们还需要定义一个结点类，这里我们实现的是带有前驱和后继的双向结点，以实现双向链表。具体实现如下：

MyList接口：

public interface MyList {
    /**
     * 返回链表中元素个数
     * @return
     */
    int size();

    /**
     * 尾插
     * @param e  将元素e尾插到线性表
     * @return  返回true
     */
    boolean add(Long e);

    /**
     * 将元素e插入到指定节点处
     * @param index
     * @param e
     */
    void add (int index,Long e);

    Long remove(int index);

    /**
     * 删除值为e的元素
     * @param e 需要删除的元素
     * @return 成功返回true  失败返回false
     */
    boolean remove(Long e);

    /**
     * 获取index处元素的值
     * @param index 数组下标
     * @return 该下标处的元素值
     */
    Long get(int index);

    /**
     * 修改元素
     * @param index [0,size)
     * @param e  修改后的元素
     * @return 原来index处的元素
     */
    Long set(int index,Long e);


    /**
     * 从前往后，返回第一次遇到e的下标
     * @param e 目标元素
     * @return 返回在第几个
     */
    int indexOf(Long e);

    /**
     * 从后向前
     * @param e
     * @return
     */
    int lastIndexOf(Long e);

    /**
     * 线性表中是否包含e
     * @param e
     * @return
     */
    boolean contains(Long e);

    /**
     * 打印顺序表
     */
    void display();


    /**
     * 判空
     * @return
     */
    boolean isEmpty();

    /**
     * 清空
     */
    void clear();

}

定义结点类

public class MyNode {
    Long val;
    MyNode next;  //指向后继节点，尾节点的后继是null

    MyNode prev;  //指向前驱节点，头节点的前驱是null

    public MyNode() {
        //无参构造方法
    }
    public MyNode(Long val) {
        //需传入值的有参构造
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}

MyLinkedList实现类：

public class MyLinkedList implements MyList {
    //需要维护三个属性：链表的头节点、链表的尾节点、链表中元素个数
    private MyNode head;
    private MyNode last;
    private int size;

    //构造方法，构造一个空的链表
    public MyLinkedList() {
        this.head = this.last = null;
        this.size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    //链表的尾插
    public boolean add(Long e) {
        MyNode node = new MyNode(e);  //将元素e放入节点中
        node.next = null;
        //分情况讨论
        if (size > 0) {
            this.last.next = node;  //这一步将尾节点的后继指向新节点    （链接）
            node.prev = this.last;  //这一步让新节点的前驱指向之前的尾节点尾    （链接完成）
            this.last = node;    //这一步让新节点成为新的尾节点   （善后）
        } else {
            node.prev = null;
            this.last = this.head = node;
        }
        this.size++;    //涉及的增删的操作必须修改size！
        return true;
    }

    //链表的头插
    private boolean addFirst(Long e) {
        MyNode node = new MyNode(e);  //将元素e放入节点中
        node.next = null;
        if (size > 0) {
            this.head.prev = node;
            node.next = this.head;
            this.head = node;
        } else {
            this.head = this.last = node;
        }

        return true;
    }

    @Override
    public void add(int index, Long e) {
        if (index < 0 || index > size) {
            throw new ArrayIndexOutOfBoundsException("下标越界");
        }
        if (size == 0) {
            add(e);
            return;
        }
        if (size == 1) {
            if (index == 0) {
                addFirst(e);
            } else {
                add(e);
            }
            return;
        }
        if (index == 0) {
            addFirst(e);
            return;
        } else if (index == size) {
            add(e);
            return;
        }
        MyNode prevNode = this.head;
        for (int i = 0; i < index - 1; i++) {
            prevNode = prevNode.next;
        }
        MyNode curnode = prevNode.next;

        MyNode node = new MyNode(e);
        prevNode.next = node;
        curnode.prev = node;
        node.prev = prevNode;
        node.next = curnode;

        size++;
    }

    @Override
    public Long remove(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException("下标异常");
        }
        if (size == 1) {
            Long e = this.head.val;
            this.head = this.last = null;
            this.size = 0;
            return e;
        }
        if (index == 0) {
            Long e = this.head.val;
            this.head = this.head.next;
            this.head.prev = null;
            size--;
            return e;
        }
        if (index == size - 1) {
            Long e = this.head.val;
            this.last = this.last.prev;
            this.last.next = null;
            size--;
            return e;
        }
        //走到这儿  说明链表中至少有两个元素
        MyNode curNode = this.head;
        for (int i = 0; i < index; i++) {
            curNode = curNode.next;
        }
        Long e = curNode.val;
//        MyNode prevNode = curNode.prev;
//        MyNode nextNode = curNode.next;
//
//        // 修改引用关系，删除 curNode
//        prevNode.next = nextNode;
//        nextNode.prev = prevNode;
        curNode.prev.next = curNode.next;
        curNode.next.prev = curNode.prev;

        size--;
        return e;

    }


    @Override
    public boolean remove(Long e) {
        MyNode curNode = this.head;
        for (int i = 0; i < size; i++) {
            if (curNode.val.equals(e)) {
                //找到元素e后判断其所在位置
                if (i == 0) {
                    this.head = this.head.next;
                    if (this.head != null) {
                        this.head.prev = null;
                    } else {
                        this.last = null;
                    }

                    size--;
                    return true;
                }
                if (i == size - 1) {
                    this.last = this.last.prev;
                    this.last.next = null;
                    size--;
                    return true;
                }

                //走到这儿说明在中间位置，既不是头删，也不是尾删
                MyNode prevNode = curNode.prev;
                MyNode nextNode = curNode.next;
                prevNode.next = nextNode;
                nextNode.prev = prevNode;
                size--;
                return true;
            }

            curNode = curNode.next;
        }
        return false;
    }

    @Override
    public Long get(int index) {
        if(index<0||index>size-1){
            throw new ArrayIndexOutOfBoundsException("下标有误");
        }
        MyNode cur=this.head;
        for (int i = 0; i <index ; i++) {
            cur=cur.next;
        }

        return cur.val;
    }

    @Override
    public Long set(int index, Long e) {
        if(index<0||index>size-1){
            throw new ArrayIndexOutOfBoundsException("下标有误");
        }
        MyNode cur=this.head;
        for (int i = 0; i <index ; i++) {
            cur=cur.next;
        }
        Long olde=cur.val;
        cur.val=e;
        return olde;
    }

    @Override
    public int indexOf(Long e) {
        int i = 0;
        MyNode cur = this.head;
        while (cur != null) {
            if (cur.val.equals(e)) {
                return i;
            }

            i++;
            cur = cur.next;
        }

        return -1;
    }

    @Override
    public int lastIndexOf(Long e) {
        int i = size-1;
        MyNode cur = this.last;
        while (cur != null) {
            if (cur.val.equals(e)) {
                return i;
            }

            i--;
            cur = cur.prev;
        }

        return -1;
    }

    @Override
    public boolean contains(Long e) {
//        MyNode cur=this.head;
//        for (int i = 0; i < size; i++) {
//            if(cur.val.equals(e)){
//                return true;
//            }
//            cur=cur.next;
//        }
//        return false;
        return indexOf(e)!=-1;
    }

    @Override
    //打印链表
    public void display() {
        MyNode cur=this.head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }

    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public void clear() {
        this.head=this.last=null;
        this.size=0;
    }

四.ArrayList和LinkedList的区别与优缺点

总结

以上两篇内容将ArrayList以及LinkedList通过自己的代码实现了简单的实现，也将其中常用的方法进行了罗列以及讲解，并对两者进行了归纳总结，总的来说就是增删频繁用链表，改查频繁用顺序表两者各有优缺点。后续将会更新与其相关的力扣题。