【Java数据结构】LinkedList

认识LinkedList

        LinkedList就是一个链表，它也是实现List接口的一个类。LinkedList就是通过next引用将所有的结点链接起来，所以不需要数组。LinkedList也是以泛型的方法实现的，所以使用这个类都需要实例化对象。

        链表分为很多种，比较常用的就两种：单链表（单向、不带头、非循环）和双链表（双向、不带头、非循环），后面会模拟实现。下面是顺序表和链表的区别：

模拟实现LinkedList

单链表

        首先需要创建结点，但是它比顺序表多了一个next引用，可以通过next引用来访问下一个结点，不再需要通过连续地址访问，首先先创建结点这个类， 然后再实现增删查改等这些方法：

链表长度、遍历链表、头插法、尾插法、任意位置插入、查找关键字key是否在链表中 、删除第一次出现关键字为key的节点、删除所有值为key的节点、清空。

public class MySingle {
    static class ListNode{
        private int val;
        private ListNode next;
         public ListNode(int val){
             this.val = val;
         }
    }
    private ListNode head;
    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }
    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if (head == null){
            head = node;
        }else {
            ListNode cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }
    //任意位置插入
    public void addIndex(int index,int data){
        if (index < 0 || index > size()){
            throw new IndexOutOfException("位置不合法！");
        }
        if (index == 0){
            addFirst(data);
            return;
        }
        ListNode node = new ListNode(data);
        ListNode cur = head;
        while (index - 1 != 0){
            cur = cur.next;
            index--;
        }
        //将index位置前后两个节点和新结点联系起来
        node.next = cur.next;
        cur.next = node;
     }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = head;
        while (cur != null){
            if (cur.val == key){
                return true;
            }
        }
        return false;
    }
    public ListNode keyPre(int key){
        ListNode cur = head;
        while (cur.next != null){
            if (cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if (head == null){
            return;
        }
        if (head.val == key){
            head = head.next;
            return;
        }
        //找到key结点的前一个结点
        ListNode pre = keyPre(key);
        ListNode del = pre.next;
        pre.next = del.next;
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        ListNode pre = head;
        ListNode cur = head.next;
        while (cur != null){
            if (cur.val == key){
                pre.next = cur.next;
                cur = cur.next;
            }else{
                pre = pre.next;
                cur = cur.next;
            }
        }
        if (head.val == key){
            head = head.next;
        }
     }
    //得到单链表的长度
    public int size(){
        int count = 0;
        ListNode cur = head;
        while (cur != null){
           count++;
            cur = cur.next;
        }
        return count;
     }
    public void display(){
        ListNode cur = head;
        while (cur != null){
            System.out.print(cur.val+"  ");
            cur = cur.next;
        }
        System.out.println();
    }
}

双链表（LinkedList）

        LinkedList其实就是一个双链表， 它既可以访问前驱又可以访问后继，所以可以快速插入和删除。下面是LinkedList模拟实现，比较难的就是插入和删除：

public class MyLinkedList {
    static class ListNode{
        private int val;
        private ListNode prev;
        private ListNode next;

        public ListNode(int val){
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode tail;
    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        if (head == null){
            head = node;
            tail = node;
        }else {
            head.prev = node;
            node.next = head;
            head = node;
        }
    }
    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if (tail == null){
            head = node;
            tail = node;
        }else{
            tail.next = node;
            node.prev = tail;
            tail = node;
            //tail = tail.next;
        }
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        if (index < 0 || index > size()){
            throw new IndexOutofBoundException(index+"位置不合理！");
        }
        ListNode node = new ListNode(data);
        ListNode cur = head;
        while (index > 0){
            cur = cur.next;
            index--;
        }
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;

    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = head;
        while (cur != null){
            if (cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if (head == null){
            return ;
        }
        ListNode cur = head;
        while(cur != null ) {
            if (cur.val == key){
                if (cur.next == null && cur.prev == null){
                    head = null;
                    tail = null;
                    return;
                }
                if (cur.prev == null) {
                    head = cur.next;
                    cur.next.prev = null;
                    return;
                }
                if(cur.next == null){
                    tail = cur.prev;
                    cur.prev.next = null;
                    return;
                }
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
                return;
            }else{
                cur = cur.next;
            }
        }
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        if (head == null){
            return ;
        }
        ListNode cur = head;
        while(cur != null ) {
            if (cur.val == key){
                if (cur.next == null && cur.prev == null){
                    head = null;
                    tail = null;
                }else if (cur.prev == null) {
                    head = cur.next;
                    cur.next.prev = null;
                }else if(cur.next == null){
                    tail = cur.prev;
                    cur.prev.next = null;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
                cur = cur.next;
            }else{
                cur = cur.next;
            }
        }
    }
    //得到单链表的长度
    public int size(){
        ListNode cur = head;
        int size = 0;
        while (cur != null){
            size++;
            cur = cur.next;
        }
        return size;
    }
    //清空
    public void clear(){
        ListNode cur = head;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curNext;
        }
        head = null;
        tail = null;
    }
    //遍历
    public void display(){
        ListNode cur = head;
        while (cur != null){
            System.out.print(cur.val+"   ");
            cur = cur.next;
        }
        System.out.println();
    }
}

LinkedList的创建

构造一个对象，可以无参构造（较为常用，在其里初始化一个数组）。 

LinkedList的遍历

        遍历的方法和ArrayList里一样，三种：for循环、增强for循环、迭代器。这两个遍历方法都是一样的，就不重复叙述。https://blog.csdn.net/2402_84815218/article/details/144038207?spm=1001.2014.3001.5502

LinkedList常用方法

 这些方法和ArrayList中的方法差不多都一样，只是实现的过程不一样。这里我就举几个例子：

    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(12);//尾插进入
        list.add(23);
        System.out.println(list);//【12，23】
//        list.add(3, 100);//插入到第index位置，但是该list中没有第三个位置
//        System.out.println(list);
        System.out.println(list.get(1));//得到1位置元素  23
        list.set(1,100);//更新1位置的元素
        System.out.println(list.get(1));// 100
        list.remove(1);//删除1位置元素
        list.clear();//清空链表
        System.out.println(list);//【】
    }

ArrayList与LinkedList的区别

        简而言之就是LinkedList的插入和删除的复杂度高，而ArrayList的可能需要移动n次数据，所以应用根据应用场景来判断使用哪一种。