Java 无头双向循环链表操作方法

无头双向循环链表

结点对象具有三个域 data next prev，其中data放数值，next指向下一个结点对象，prev指向前一个结点对象。

双向链表示意图

class ListNode{
    private int val;
    private ListNode next;
    private ListNode prev;

    //结点创建方法
    public ListNode(int val) {
        this.val = val;
    }

    public int getVal() {
        return val;
    }


    public void setVal(int val) {
        this.val = val;
    }

    public ListNode getNext() {
        return next;
    }

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

    public ListNode getPrev() {
        return prev;
    }

    public void setPrev(ListNode prev) {
        this.prev = prev;
    }
}
           

public class DoubleLinkedList {
    //    LinkedList
    public ListNode head;
    public ListNode last;


    //头插法
    public void addFirst(int data){
        ListNode node1 = new ListNode(data);
        if(head == null){
            head = node1;
            last = node1;
        }else{
            node1.setNext(head);
            head.setPrev(node1);
            head = node1;
        }
    }


    //尾插法
    public void addLast(int data){
        ListNode node2 = new ListNode(data);
        if(head == null){
            head = node2;
            last = node2;
        }else{
            last.setNext(node2);
            node2.setPrev(last);
            last = node2;
        }
    }


    //获取双向链表长度
    public int getLength(){
        ListNode cur = head;
        int count = 0;
        while(cur != null){
            cur = cur.getNext();
            count++;
        }
        return count;
    }


    //任意位置插入，第一个数据结点为0号下标
    public void addIndex(int index,int data){
        if(index < 0 || index > getLength()){
            return ;
        }
        if(index == 0){
            addFirst(data);
            return ;
        }
        if(index == getLength()){
            addLast(data);
            return ;
        }
        //定义cur为插入结点的后继
        ListNode cur = head;
        while(index != 0){         //走index步
            cur = cur.getNext();
            index--;
        }

        ListNode node3 = new ListNode(data);
        cur.getPrev().setNext(node3);
        node3.setNext(cur);
        node3.setPrev(cur.getPrev());
        cur.setPrev(node3);
    }


    //判断双向链表是否包含关键字key
    public boolean contains(int key){
        if(head == null){
            return false;
        }
        ListNode cur = head;
        while(cur != null){
            if(cur.getVal() == key){
                return true;
            }
            cur = cur.getNext();
        }
        return false;
    }


    //返回双向链表关键字为key的结点
    public ListNode findNode(int key){
        if(head == null){
            return null;
        }
        ListNode cur = head;
        while(cur != null){
            if(cur.getVal() == key){
                return cur;
            }
            cur = cur.getNext();
        }
        return null;
    }


    //删除第一次出现关键字为key的结点
    public void remove(int key){

        ListNode cur = findNode(key);  //寻找关键字为key的结点
        //表明删除的结点为空，没有值关键字为key的结点
        if(cur == null){
            return ;
        }
        //表明删除的结点为头结点
        if(cur == head){
            head.getNext().setPrev(null);
            head = head.getNext();
            return ;
        }
        //表明删除的结点为尾结点
        if(cur == last){
            last.getPrev().setNext(null);
            last = last.getPrev();
            return ;
        }
        cur.getPrev().setNext(cur.getNext());
        cur.getNext().setPrev(cur.getPrev());
    }


    //第二种删除方法   无需定义额外的方法
    public void remove2(int key){
        ListNode cur = head;
        while(cur != null){
            //表头的值就是我们要删除的关键字
            if(cur.getVal() == key){
                if(cur == head) {
                    head.getNext().setPrev(null);
                    head = head.getNext();
                    return ;
                }else{
                    cur.getPrev().setNext(cur.getNext());
                    //此时判断cur是不是倒数第二结点和尾结点
                    if(cur.getNext() != null){
                        cur.getNext().setPrev(cur.getPrev());
                        //
                    }else{
                        last = last.getPrev();
                    }
                    return ;
                }
                //只放一个return ;在这里也是没问题的
                // 这里的else可不要
            }else{
                cur = cur.getNext();
            }
            //刚开始return错放在这里 导致走一次就return出去 不能再继续下去
        }
        return ;
    }


    //删除关键字为key的所有的结点
    public void remove3(int key){
        ListNode cur = head;
        while(cur != null){
            //表头的值就是我们要删除的关键字
            if(cur.getVal() == key){
                if(cur == head) {
                    head.getNext().setPrev(null);
                    head = head.getNext();
                }else if(cur == last){
                    cur.getPrev().setNext(null);
                    last = last.getPrev();
                }else{
                    cur.getPrev().setNext(cur.getNext());
                    cur.getNext().setPrev(cur.getPrev());
                }
            }
            cur = cur.getNext();
            //刚开始return错放在这里 导致走一次就return出去 不能再继续下去
        }
        return ;
    }


    //清空链表
   
    //暴力方式
    public void clear(){
        head = null;
        last = null;
    }
	
	//温柔方式
    public void clear1(){
        ListNode cur = head;
        while(cur != null){
            //定义当前结点的下一个结点
            ListNode curNext = cur.getNext();
            cur.setNext(null);
            cur.setPrev(null);
            cur = curNext;
        }
        head = null;
        last = null;
    }