一. 自定义LinkedList

LinkedList 位于 java.util 包下，内部封装的是链接，用于快速添加，删除元素，也支持查询元素。

由于是内部封装链表，数据结构需要多看一下。

LinkedList 的源码非常好，建议多读一下。

老蝴蝶简单自定义一个 LinkedList, 实现相应的基础功能。

一.一自定义 MyLinkedList, 实现 LinkedList 功能

package com.yjl.collection;
/**
 * package: com.yjl.collection
 * className: MyLinkedList
 * Description: 请输入相应的描述
 *
 * @author : yuezl
 * @Date :2020/6/11 11:35
 */
public class MyLinkedList<E>{
    /*内部定义一个Node. 静态的*/
    private static class Node<E>{
        /**
         * @param previous 上一节点
         * @param next 下一节点
         * @param e 当前元素
         *
         */
        private Node<E> previous;
        private Node<E> next;
        private E e;
        public Node(){
        }
        public Node(Node previous,E e,Node next){
            this.previous=previous;
            this.e=e;
            this.next=next;
        }
    }
    /*需要定义三个属性， 根节点，尾节点，和长度size*/
    /**
     * @param first 根节点
     * @param last 尾节点
     * @param size 当前长度
     *
     * 如果没有元素的话， first=last=null,
     *  如果只有一个元素的话， first=last=唯一的那个元素值构成的Node
     *  如果有两个或者两个以上的话， first指向第一个,last指向最后一个
     */
    private Node<E> first;
    private Node<E> last;
    private int size;
    /*定义构造方法*/
    public MyLinkedList(){
    }
    public MyLinkedList(MyLinkedList<E> mll){
        addAll(mll);
    }
    /*关于添加的相应操作*/
    /**
     * 添加 到最后
     * @param e
     * @return
     */
    public boolean add(E e){
        addLast(e);
        return true;
    }
    /**
     * 有索引的添加
     * @param index
     * @param e
     * @return
     */
    public boolean add(int index,E e){
        //如果是最后一个，那么就是追加
        if(index==size){
            addLast(e);
        }else{
            addBefore(e,getNodeByIndex(index));
        }
        return true;
    }
    public boolean addAll(MyLinkedList<E> mll){
        addAll(size,mll);
        return true;
    }
    public boolean addAll(int index,MyLinkedList<E> mll){
        //转换成数组，获取里面的元素。
        Object[] obj=mll.toArray();
        int length=obj.length;
        if(length==0){
            throw new NullPointerException("传入的集合为空");
        }
        //定义两个对象，一个上一个对象，一个当前对象。
        Node<E> pre,local;
        //说明是后面插入的，或者调用 addll()方法的。
        if(index==size){
            pre=last;
            //当前的为空
            local=null;
        }else{
            local=getNodeByIndex(index);
            pre=local.previous;
        }
        for(int i=0;i<obj.length;i++){
                //构建新对象
                Node<E> node=new Node(pre,obj[i],null);
                //判断一下，是否是开头插入
                if(pre==null){
                    first=node;
                }else{
                    //上一个的下一个为node
                    pre.next=node;
                }
                //新的pre
                pre=node;
        }
        //判断一下，是否是末尾插入
        if(local==null){
            last=pre;
        }else{
            pre.next=local;
            local.previous=pre;
        }
        size+=length;
        return true;
    }
    /**
     * 添加到第一个
     * @param e
     */
    public void addFirst(E e){
        // 构建Node,记录一下，以前的第一个。 以前的第一个，将会变成新Node 的next
        Node<E> f=first;
        Node<E> node=new Node(null,e,f);
        first=node;
        //看以前是否有内容，来判断是否有下一个。
        if(f==null){
            //以前没有值的话， last为现在的node
            last=node;
        }else{
            //设置 以前的previous 为node， 以前previous为null
            f.previous=node;
        }
        size++;
    }
    /**
     * 添加到最后一个
     * @param e
     */
    public void addLast(E e){
        //先构建 Node,记录一下，以前的最后一个。 以前的最后一个，将变成新的前。
        Node<E> l=last;
        //新Node
        Node node=new Node(l,e,null);
        //最后一个，last 指向新的 node
        last=node;
        //判断一下 l, 由此确定一下 first
        if(l==null){
            //根节点为  node.
            first=node;
        }else{
            //以前的下一个为 last, 以前是null
            l.next=last;
        }
        size++;
    }
    /**
     * 在以前的任意结点上添加元素，不适用末尾添加。
     * @param e
     * @param node
     */
    private void addBefore(E e,Node<E> node){
        //获取该节点的上一个节点。 下一个接点，是不变的。
        final Node prev=node.previous;
        //构建新的Node 新结点的上一个结点为prev,下一个接点为当前结点。
        Node newNode=new Node(prev,e,node);
        //将上一个结点变成新结点。
        node.previous=newNode;
        if(prev==null){
            first=newNode;
        }else{
            prev.next=newNode;
        }
        size++;
    }
    /**
     * 放置元素， 放置在最前面
     * @param e
     */
    public void push(E e){
       addFirst(e);
    }
    /**
     *  移除元素， 移除第一个。
     * @return
     */
    public E pop(){
        return unLinkFirst(first);
    }
    /** 移除的操作*/
    /**
     * 移除第一个
     * @return
     */
    public E remove(){
      return removeFirst();
    }
    /**
     * 移除固定索引的元素
     * @param index
     * @return
     */
    public E remove(int index){
        return unLink(getNodeByIndex(index));
    }
    /**
     * 按照对象移除
     * @param obj
     * @return
     */
    public E remove(Object obj){
        int index=indexOf(obj);
        if(index>=0){
            return remove(index);
        }
        return null;
    }
    /**
     * 移除第一个
     * @return
     */
    public E removeFirst(){
       return  unLinkFirst(first);
    }
    /**
     * 移除最后一个
     * @return
     */
    public E removeLast(){
        return unLinkLast(last);
    }
    /**
     * 移除中间的元素
     * @param node
     * @return
     */
    private E unLink(Node<E> node){
        //获取上一个，获取下一个。 上一个和下一个，均是有值的。
        Node<E> pre=node.previous;
        Node<E> next=node.next;
        E element=node.e;
        node.e=null;
        //前面为空，说明只有一个元素
        if(pre==null){
            first=null;
        }else{
            pre.next=next;
            //当前元素断开
            node.previous=null;
        }
        //最后一个时
        if(next==null){
            last=pre;
        }else{
            pre.next=next;
            node.next=null;
        }
        size--;
        return element;
    }
    /**
     * 移除头部
     * @param node
     * @return
     */
    private E unLinkFirst(Node<E> node){
        //获取下一个元素
        Node next=node.next;
        E element=node.e;
        //GC
        node.e=null;
        node.next=null;
        //first 就指向下一个元素了
        first=next;
        if(next==null){
            last=null;
        }else{
            //令下一个元素的上一个元素为null,下一个元素不变
            next.previous=null;
        }
        size--;
        return element;
    }
    /**
     * 移除最后一个
     * @param node
     * @return
     */
    private E unLinkLast(Node<E> node){
        //获取前面的元素
        Node pre=node.previous;
        E element=node.e;
        node.previous=null;
        node.e=null;
        last=pre;
        //看是否是第一个
        if(pre==null){
            first=null;
        }else{
            pre.next=null;
        }
        size--;
        return element;
    }
    /*设置和获取*/
    /**
     * 获取长度
     * @return
     */
    public int size(){
        return size;
    }
    /**
     * 判断是否为空
     * @return
     */
    public boolean isEmpty(){
        return size==0?true:false;
    }
    /**
     * 是否包含某个对象
     * @param obj
     * @return
     */
    public boolean contains(Object obj){
        return indexOf(obj)>=0?true:false;
    }
    /**
     * 索引位置
     * @param obj
     * @return
     */
    public int indexOf(Object obj){
        int index=-1;
        //对象为null
        if(obj==null){
            for(Node<E> node=first;node!=null;){
                index++;
                if(node.e==obj){
                    return index;
                }
                node=node.next;
            }
        }else{
            for(Node<E> node=first;node!=null;){
                index++;
                if(obj.equals(node.e)){
                    return index;
                }
                node=node.next;
            }
        }
        return -1;
    }
    /**
     * 倒序的索引位置
     * @param obj
     * @return
     */
    public int lastIndexOf(Object obj){
        int index=-1;
        //对象为null
        if(obj==null){
            for(Node<E> node=last;node!=null;){
                index++;
                if(node.e==obj){
                    return index;
                }
                node=node.previous;
            }
        }else{
            for(Node<E> node=last;node!=null;){
                index++;
                if(obj.equals(node.e)){
                    return index;
                }
                node=node.previous;
            }
        }
        return -1;
    }
    /**
     * 设置值
     * @param index
     * @param e
     * @return
     */
    public E set(int index,E e){
        Node old=getNodeByIndex(index);
        old.e=e;
        return (E)old.e;
    }
    /**
     * 获取值
     * @param index
     * @return
     */
    public E get(int index){
        Node node=getNodeByIndex(index);
        return (E)node.e;
    }
    /**
     * 得到头部
     * @return
     */
    public E getFirst(){
        if(first==null){
            return null;
        }
        return first.e;
    }
    /**
     * 得到尾部
     * @return
     */
    public E getLast(){
        if(last==null){
            return null;
        }
        return last.e;
    }
    /**
     * 根据索引编号获取相应的节点
     * @param index
     * @return
     */
    private Node<E> getNodeByIndex(int index){
        //判断一下，当前的index 是在左半部分，还是在右半部分
        if(index<=(size>>2)){
            Node node=first;
            for(int i=0;i<index;i++){
                node=node.next;
            }
            return node;
        }else{
            Node node=last;
            for(int i=size-1;i>index;i--){
                node=last.previous;
            }
            return node;
        }
    }
    /**
     * 清空
     */
    public void clear(){
        //需要将以前的那些链接清空，方便GC 收集
        for(Node<E> node=first;node!=null;){
            Node<E> next=node.next;
            node.previous=null;
            node.e=null;
            node.next=null;
            node=next;
        }
        first=null;
        last=null;
        size=0;
        //
    }
    /**
     * 转换成数组
     * @return
     */
    public Object[] toArray(){
        Object[] result=new Object[size];
        int i=0;
        for(Node<E>node=first;node!=null;node=node.next){
            result[i++]=node.e;
        }
        return result;
    }
    /**
     * 打印输出
     * @return
     */
    public String toString(){
        if(size==0){
            return "[]";
        }
        StringBuilder sb=new StringBuilder();
        sb.append("[");
        for(Node<E> node=first;node!=null;node=node.next){
           String temp= node.e.toString();
           sb.append(temp+",");
        }
        sb.replace(sb.length()-1,sb.length(),"]");
        return sb.toString();
    }
}

一.二测试自定义 MyLinkedList

package com.yjl.collection;
/**
 * package: com.yjl.collection
 * className: MyLinkedListTest
 * Description: 请输入相应的描述
 *
 * @author : yuezl
 * @Date :2020/6/11 15:18
 */
public class MyLinkedListTest {
    public static void main(String[] args) {
        MyLinkedList<Integer> mal = new MyLinkedList<Integer>();
        System.out.println("长度:" + mal.size() + ",是否为空:" + mal.isEmpty());
        //添加元素
        mal.add(3);
        mal.add(4);
        //索引时添加
        mal.add(0, 1);
       mal.addFirst(0);
       mal.addLast(100);
        //打印
        System.out.println("mal:" + mal.toString());
        //集合构建
        MyLinkedList<Integer> mal2 = new MyLinkedList<Integer>(mal);
        System.out.println("mal2:" + mal2.toString());
        //添加所有
        mal2.addAll(mal);
        System.out.println("新的mal2:" + mal2.toString());
        //获取值
        Integer val = mal2.get(3);
        System.out.println("输出值为:" + val);
        //索引长度构造
        MyLinkedList<Integer> mal3=new MyLinkedList<Integer>();
        mal3.add(1);
        mal3.add(2);
        System.out.println("是否包含2:"+mal3.contains(2));
        System.out.println("长度1:"+mal3.toArray().length);
        //清除
        mal3.clear();
        System.out.println("长度:"+mal3.size()+",是否为空:"+mal3.isEmpty());
    }
}