LikedList类是List接口的实现类。他还实现了Deque接口，还是一个队列，也能当成双端队列来使用。虽然LinkedList是一个List集合，但是它的实现方式和ArrayList是完全不同的，ArrayList的底层是一个动态的Object[]数组，而LinkedList的底层是一个双向链表。

LinkedList是基于双向循环链表实现的，他还能当作队列或者栈来使用，他是线程不安全的，适合在单线程下使用

2、构造方法

构造方法	说明
LinkedList()	无参构造
LinkedList(Collection<? extends E> c)	将指定集合转换为LinkedList，底层使用addAll方法

二、实现双向非循环链表

1、准备

实现双向链表我们要先明白一个节点都有哪些字段，首先有存放数据的数据域，其次由于是双向的相对于单链表而言，增加了前驱节点


public class MyLinkedList {
    static class Node{
        public int val;     //数据域
        public Node prev;    //前驱指针
        public Node next;    //后驱指针
 
        /**
         * 构造节点
         * @param val
         */
        public Node(int val) {
            this.val = val;
        }
    }
 
    public Node head;    //作为头节点
    public Node last;    //作为尾节点
}

2、方法的实现

1.遍历


 /**
     * 遍历双向链表
     */
    public void display(){
        Node cur = head;             //代替头节点遍历，跟单链表遍历相同
 
        while(cur != null){
            System.out.print(cur.val + " ");
        }
 
        System.out.println();
 
        cur = last;                 //代替尾节点遍历，反向遍历
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.prev;
        }
        System.out.println();
    }

2.有效节点个数

通过遍历时计算进行计数


 /**
     * 计算节点个数
     * @return
     */
    public int size(){
        int size = 0;    //定义变量计数
        Node cur = head; //代替头指针遍历节点
 
        while(cur != null){
            size++;
            cur = cur.next;
        }
 
        return size;
    }

3.是否包含key

通过遍历时判断是否存在


/**
     * 是否存在key
     * @param key  关键字
     * @return
     */
    public boolean contains(int key){
        Node cur = head;         //代替头节点遍历
 
        while(cur != null){     //开始遍历
            if(cur.val == key){ //如果存在返回
                return true;
            }
            cur = cur.next;
        }
 
        return false;            //遍历完成后没有存在返回false
    }

4.清空链表

通过遍历释放每个节点的前驱与后驱指向


/**
     * 清空链表
     */
    public void clear(){
        Node cur = head;        //代替头节点进行遍历
 
        while(cur != null){
            Node next = cur.next;  //先记录下一个节点
            cur.next = null;      //释放前驱指向
            cur.prev = null;      //释放后驱指向
            cur = next;           //遍历下一个节点重复操作
        }
 
        head = null;             //释放头节点与尾节点
        last = null;
    }

5.头插法

在头插时，分两种清空，第一种是当前链表如果为空，此时插入数据是第一个只需让头指针与尾指针同时指向该节点，第二种情况是链表中已经有节点，此时插入时，分为三步：首先让新节点的next域指向头节点，然后让头节点的前驱指向新增节点，最后更新头节点的位置


/**
     * 头插法
     * @param data
     */
    public void addFirst(int data){
        Node node = new Node(data);   //构造节点
 
        if(head == null){
            //如果头节点为空，第一次插入，直接将头与尾指向新节点
            head = node;
            last = node;
        }else{
            //不是第一次插入
            node.next = head;    //此时新节点的next指向头节点
            head.prev = node;    //然后再将头节点的前驱指向新节点
            head = node;         //更新头节点的位置
        }
    }

6.尾插法

尾插时也分为两种情况，第一种是当前链表如果为空，此时插入数据是第一个只需让头指针与尾指针同时指向该节点，第二种情况是链表中已经有节点，此时插入时，分为三步：首先让新节点的前驱指向尾节点，然后让尾节点的next指向新增节点，最后更新尾节点的位置


/**
     * 尾插法
     * @param data
     */
    public void addLast(int data){
        Node node = new Node(data);  //构造节点
 
        if(head == null){
            //如果头节点为空，第一次插入，直接将两个指针指向节点
            head = node;
            last = node;
        }else{
            //不是第一次插入
            last.next = node;  //将尾节点的next指向插入节点
            node.prev = last;  //再将插入节点的前驱节点指向尾节点
            last = node;       //更新尾节点的位置
        }
    }

7.指定位置插入

单链表里我们指定位置的插入要找到前驱节点，但是在双向链表里有前驱节点这个指针，我们只需要找到要求的下标的节点cur，找到后先将新增节点node.next指向cur，然后此处不能先将cur的前驱更改为node，因为如果更改了cur.prev我们在接前面的节点时就会失去地址，所以先将前面的节点与node连接node.prev = cur.prev（前一个节点的地址） cur.prev.next （前一个节点的next）= node


/**
     * 指定位置插入元素
     * @param index 指定下标
     * @param data  元素值
     */
    public void addIndex(int index,int data){
        //1.下标合法性判断 处理特殊情况
        if(index < 0 || index > size()){
            throw new ArrayIndexOutOfBoundsException("非法下标");
        }
 
        if(index == 0){
            addFirst(data);
            return;
        }
 
        if(index ==size()){
            addLast(data);
            return;
        }
 
        //2.找到当前节点
        Node cur = searchNodeToAdd(index);
 
        //3.开始插入
        Node node = new Node(data);
        node.next = cur;                //新增节点next指向当前节点
        node.prev = cur.prev;           //新增节点的前驱指向当前节点的前驱
        cur.prev.next = node;           //当前节点的前驱节点的next指向新增节点
        cur.prev = node;                //最后更新当前节点的前驱为新增节点
    }
 
    /**
     * 查找指定下标的节点
     * @param index
     * @return
     */
    private Node searchNodeToAdd(int index) {
        Node cur = head;
 
        while(index-- != 0){
            cur = cur.next;
        }
 
        return cur;
    }

8.删除第一次出现的key

与单链表删除第一次出现的key类似，此处要处理前驱节点，核心步骤：找到节点cur，然后让cur的前面的节点的next指向cur.next，然后再让cur的后面的节点的前驱指向cur的前驱。要注意处理特殊情况：1.头节点 2.尾节点


/**
     * 删除第一次出现的key
     * @param key
     */
    public void remove(int key){
        Node 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 == last){
                        //如果是最后一个节点更新last的位置
                        last = last.prev;
                    }else{
                        //不是最后一个节点正常删除
                        cur.next.prev = cur.prev;
                    }
                }
                //删除完成后返回
                return;
            }
            cur = cur.next;
        }
    }

9.删除所有的key

上述代码删除一个后就返回，也就是只删除第一个，如果我们删除第一个后继续删除满足条件的，我们只需去掉删除完成后的哪个return


/**
     * 删除所有的key
     * @param key 待删元素
     */
    public void removeAll(int key){
        Node 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 == last){
                        //如果是最后一个节点更新last的位置
                        last = last.prev;
                    }else{
                        //不是最后一个节点正常删除
                        cur.next.prev = cur.prev;
                    }
                }
                //删除完成后不返回，继续执行
            }
            cur = cur.next;
        }
    }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/456539