【Java数据结构】通过Java理解和实现——无头双向链表

//打印双链表
   public void display() {
       //和单链表的打印方式是一样的
       ListNode cur = this.head;//利用临时变量cur代替头结点遍历
       while (cur != null){
           System.out.print(cur.val+" ");
           cur = cur.next;//依次往后走
       }
       System.out.println();
   }

//头插法
   public void addFirst(int data) {
       ListNode node = new ListNode(data);//创建一个新节点，储存要插入的数据
       if (this.head==null){//判断头结点是否为空，头结点空说明链表为空
           //头结点null属于第一次插入，直接将头结点尾节点都指向插入节点即可
           this.head=node;
           this.last=node;
       }else{//如果不是第一次插入
           node.next=this.head;//将原头结点变成新插入节点的后驱，实现头插
           head.prev=node;//再将新插入节点变成原头结点的前驱
           this.head=node;//最后将新插入的节点设置成头结点
       }
   }

//尾插法
   public void addLast(int data){
       ListNode node = new ListNode(data);//创建一个新节点，储存要插入的数据
       if (this.head==null){//判断头结点是否为空，头结点空说明链表为空
           //头结点null属于第一次插入，直接将头结点尾节点都指向插入节点即可
           this.head=node;
           this.last=node;
       }else{//如果不是第一次插入
           this.last.next=node;//将新结点变成原尾节点的后驱，实现尾插
           node.prev=last;//再将原尾节点变成新插入节点的前驱
           this.last=node;//最后将新插入节点设置成尾节点
       }
   }

//查找是否包含关键字key是否在单链表当中
   public boolean contains(int key){
       ListNode cur = this.head;//引入局部变量cur遍历链表
       while(cur != null){
           if(cur.val==key){//如果当前节点的val等于关键字
               return true;//返回true
           }
           cur = cur.next;//否则继续往后遍历
       }
       return false;//遍历完成都没有找到key值，返回false
   }

//得到双链表的长度
   public int size() {
       int size=0;//设置一个计数变量用于计数
       ListNode cur = this.head;//利用cur代替头结点遍历链表
       while (cur != null){//遍历链表，节点不为空
           size++;//计数器+1
           cur = cur.next;//往后走一步
       }
       return size;//遍历完链表返回计数器的值，就是链表长度了
   }

//任意位置插入,第一个数据节点为0号下标
   public void addIndex(int index,int data){
       ListNode node = new ListNode(data);//创建一个新节点储存要插入的数据
       ListNode cur = this.head;//临时变量cur代替头结点遍历链表
       if (index > 0 && index <size()) {//插入位置不是头也不是尾
           for (int i = 0; i < index; i++){//先让cur走到要插入的位置处
               cur = cur.next;
           }
           cur.prev.next=node;//将插入位置前一节点的后驱指向新节点
           node.prev=cur.prev;//将新节点的前驱指向插入位置的前一节点即 cur.prev
           node.next=cur;//将新节点后驱指向当前cur，也就实现了插入，插到cur和cur前一节点的中间，替代了cur的原位置
       }
       if (index ==size()){//插入位置在尾部
           addLast(data);//直接尾插法
       }
       if (index==0){//插入位置在头部
           addFirst(data);//直接头插法
      }
       display();//打印增加后的链表
   }

//删除第一次出现关键字为key的节点
   public void remove(int key){
       ListNode cur = this.head;//设置cur代替头节点遍历链表
       while(cur != null){
           if(cur.val==key){//如果找到了要删除的点，分以下三种情况
               if(cur==head){//在头部
                   head=head.next;//将要删除的节点的下一节点设为新头节点
                   if (head==null) {//如果这个双链表只有一个元素，要检查
                       break;
                   }
                   head.prev=null;//如果不止一个元素，则将头结点的前驱指向置空
                   break;
               }
               if (cur==last){//在尾部
                   last=last.prev;//要删除节点的上一节点设为新尾节点
                   last.next=null;//将新尾节点后驱置空
                   break;
               } >               if (cur.prev!=null && cur.next!=null){//在中间
                   cur.prev.next=cur.next;//将key节点前一节点的后驱指向key节点的后一节点
                   cur.next.prev=cur.prev;//将key节点后一节点的前驱指向key节点的前一节点
                   break;
               }
           }
           cur=cur.next;//如果没找到目标点则往后走一步
       }
       display();//打印删除后的双链表
   }

//删除所有值为key的节点
   public void removeAllKey(int key){
       ListNode cur = this.head;
       while(cur != null){
           if(cur.val==key){
               if(cur==head){//在头部
                   head=head.next;
                   if (head==null) {//只有一个元素，要检查
                       break;
                   }
                   head.prev=null;
               }
               if (cur==last){//在尾部
                   last=last.prev;
                   last.next=null;
               }
               if (cur.prev!=null && cur.next!=null){//在中间
                   cur.prev.next=cur.next;
                   cur.next.prev=cur.prev;
               }
           }
           cur=cur.next;
       }
       display();
   }

//清空链表
   public void clear() {
       head=null;
       last=null;
   }