源代码：https://gitee.com/AgentXiao/Collection

一、LinkedList底层实现

LinkedList的底层是双向链表。该链表由多个节点组成。

package pri.xiaowd.demo02;

/**
 * @ClassName Node
 * @Description 节点
 * @Author xwd
 * @Date 2018/10/7 11:07
 */
public class Node {
    private Node previous;//上一个节点
    private Object obj;//存储的对象
    private Node next;//下一个节点

    public Node() {

    }

    public Node(Node previous, Object obj, Node next) {
        this.previous = previous;
        this.obj = obj;
        this.next = next;
    }

    public Node getPrevious() {
        return previous;
    }

    public void setPrevious(Node previous) {
        this.previous = previous;
    }

    public Object getObj() {
        return obj;
    }

    public void setObj(Object obj) {
        this.obj = obj;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

2、自己实现一个LinkedList
（1）在链表中，比较重要的是第一个节点和最后一个节点。

    private Node first;//第一个节点
    private Node last;//最后一个节点

（2）add(Object obj)方法

add(Object obj)

    /**
     * @MethodName add
     * @Descrition 添加一个节点
     * @Param [object]
     * @return void
     */
    public void add(Object object){
        Node node = new Node();
        //如果第一个链表都是空的，说明添加的是第一个节点
        if(first == null){
            node.setPrevious(null);  //第一个节点的上一个节点是null
            node.setObj(object);  //第一个节点的内容
            node.setNext(null);  //第一个节点的下一个节点也暂时是空的

            first = node;  //添加了第一个节点之后第一个和最后一个都是新添加的
            last = node;
        }else{  //直接在最后一个节点的后面添加
            node.setPrevious(last);   //新添加的节点的上一个节点是之前的最后一个
            node.setObj(object);  //新添对象
            node.setNext(null);  //新添加的节点的下一个节点是null

            last.setNext(node);  //形成链表，原先的最后一个的下一个节点设置为新增的节点
            last = node;  //将最后一个节点设置为新增的节点
        }
        size++;  //长度+1
    }

（3）我们来测试一下

public static void main(String[] args) {
        MyLinkedList mll = new MyLinkedList();
        mll.add("aaa");
        mll.add("bbb");
        System.out.println(mll.size);
    }

得到如果示意图：

debug示意图

（4）get(int index)：因为链表是没有下标的，所以只能从头开始一个一个遍历。
首先需要进行索引值越界判断

    /**
     * @MethodName rangeCheck
     * @Descrition 索引检测
     * @Param [index]
     * @return void
     */
    private void rangeCheck(int index){
        if(index < 0 || index >= size){
            throw new RuntimeException("你输入的索引值不在范围之内！");
        }
    }

获取一个对象，特别需要注意循环遍历的时候什么时候就能得到想要的对象

    /**
     * @MethodName getNode
     * @Descrition 找到指定位置的节点
     * @Param [index]
     * @return pri.xiaowd.demo02.Node
     */
    public Node getNode(int index){
        Node temp = null;
        if(first != null){
            temp = first;
            for(int i=0;i<index;i++){
                temp = temp.getNext();
            }
        }
        return temp;
    }

    /**
     * @MethodName get
     * @Descrition 获取指定位置节点的内容
     * @Param [index]
     * @return java.lang.Object
     */
    public Object get(int index){
        rangeCheck(index);
        Node temp = getNode(index);
        return temp.getObj();
    }

（5）移除指定位置的节点remove(int index)

remove.png

    /**
     * @MethodName remove
     * @Descrition 移除指定索引位置的节点
     * @Param [index]
     * @return void
     */
    public void remove(int index){
        rangeCheck(index);
        //找到索引位置的节点
        Node temp = getNode(index);
        if(temp != null){
            Node upNode = temp.getPrevious();
            Node downNode = temp.getNext();
            upNode.setNext(downNode);
            downNode.setPrevious(upNode);
            size -- ;
        }
    }

（6）add(int index,Object obj)

add(int index,Object obj) index=1的情况

    /**
     * @MethodName add
     * @Descrition 在指定位置插入对象
     * @Param [index, obj]
     * @return void
     */
    public void add(int index,Object obj){
        rangeCheck(index);
        Node temp = getNode(index);//得到索引位置的节点

        Node newNode = new Node();//创建新的节点
        newNode.setObj(obj);

        if(index == 0){ //如果想在第一个位置插入，不考虑索引位置的节点是否为空
            newNode.setPrevious(null);
            newNode.setNext(temp);
            temp.setPrevious(newNode);
            first = newNode;
        }else{
            if(temp != null) {  //实际上经过了索引检测之后，temp不会为空
                Node upNode = temp.getPrevious();//得到上一个节点
                upNode.setNext(newNode);
                newNode.setPrevious(upNode);
                newNode.setNext(temp);
                temp.setPrevious(newNode);
            }
        }
        size++;
    }

（7）set(int index,Object obj)

set(int index,Object obj)

    /**
     * @MethodName set
     * @Descrition 在指定的索引位置替换对象
     * @Param [index, obj]
     * @return void
     */
    public void set(int index,Object obj){
        rangeCheck(index);
        Node temp = getNode(index);//得到索引位置的节点

        Node newNode = new Node();//创建新的节点
        newNode.setObj(obj);

        if(index == 0){
            newNode.setPrevious(null);
            newNode.setNext(temp.getNext());
            temp.getNext().setPrevious(newNode);
            first = newNode;
        }else if(index == size-1){
            newNode.setNext(null);
            newNode.setPrevious(temp.getPrevious());
            temp.getPrevious().setNext(newNode);
            last = newNode;
        }else{
            Node upNode = temp.getPrevious();
            Node downNode = temp.getNext();
            upNode.setNext(newNode);
            newNode.setPrevious(upNode);
            newNode.setNext(downNode);
            downNode.setPrevious(newNode);
        }
    }

(8)remove(Object obj)

remove(Object obj)

    /**
     * @MethodName getNode
     * @Descrition 根据obj查找对应的节点
     * @Param [obj]
     * @return pri.xiaowd.demo02.Node
     */
    public Node getNode(Object obj){
        Node temp = first;
        if(first != null){
            for(int i=0;i<size;i++){
                if(temp.getObj().equals(obj)){
                    return temp;
                }
                temp = temp.getNext();
            }
        }
        return temp;
    }

/**
     * @MethodName remove
     * @Descrition 移除指定的节点
     * @Param [obj]
     * @return void
     */
    public void remove(Object obj){
        Node node = getNode(obj);
        Node downNode = node.getNext();
        Node upNode = node.getPrevious();
        if(node.getPrevious() == null){  //如果是第一个节点
            downNode = node.getNext();
            downNode.setPrevious(null);
            first = downNode;
        }else if(node.getNext() == null){  //如果是最后一个节点
            upNode = node.getPrevious();
            upNode.setNext(null);
            last = upNode;
        }else{  //如果是中间的节点
            upNode.setNext(downNode);
            downNode.setPrevious(upNode);
        }
        size--;
    }

三、总结

最为重要的，是能够画出链表的图示，对着图示进行代码的编写。

【补充】细节完善
对于get(int index)方法，如果始终从0开始遍历话，当index较大时，效率太低。因此可以使用二分法进行拆分，提高效率。

    /**
     * @MethodName getNode
     * @Descrition 找到指定位置的节点
     * @Param [index]
     * @return pri.xiaowd.demo02.Node
     */
    public Node getNode(int index){
        Node temp = null;
        if(first != null){
            if(index < (size >> 1)){
                temp = first;
                for(int i=0;i<index;i++){
                    temp = temp.getNext();
                }
            }else{
                temp = last;
                for(int i=size-1;i>index;i--){
                    temp = temp.getPrevious();
                }
            }
        }
        return temp;
    }