【Java数据结构】实现双链表

蔚落 2024-04-03 09:08 81阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：渴望力量的土狗
> 
> 博客主页：[渴望力量的土狗的博客主页][Link 1]
> 
> 专栏：[数据结构与算法][Link 2]
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击免费注册和我一起刷题吧][Link 3]

![d27c4f6e224600894205a5a4ed1316a0.png][]

MyLinkedList.java

public class MyLinkedList {
    
        static  class ListNode{
    
            private int data;
            private ListNode next;
            private ListNode pre;
            public ListNode(){
    
            }
    
           public ListNode(int data) {
               this.data = data;
    
           }
       }
    
        ListNode head;
        ListNode tail;
    
        // 2、无头双向链表实现
    
            //头插法
            public  void addFirst(int data){
    
            ListNode node=new ListNode(data);
    
            if(this.head==null){
               this.head=node;
                this.tail=node;
            }else{
               node.next=this.head;
                head.pre=node;
                this.head=node;
            }
    
            }
            //尾插法
            public void addLast(int data){
                ListNode node=new ListNode(data);
                ListNode cur=this.tail;
                if(this.head==null){
                    this.head=node;
                    this.tail=node;
                }else{
    
                    cur.next=node;
                    node.pre=cur;
                    this.tail=node;
                }
    
    
    
            }
            //任意位置插入,第一个数据节点为0号下标
            public boolean addIndex(int index,int data){
                ListNode node =new ListNode(data);
    
                if(index<0||index>size()){
                    return false;
                }
                if(index==0){
                    addFirst(data);
                    return true;
                }
                if(index==size()){
                    addLast(data);
                    return true;
                }
                ListNode cur=this.head;
                if(index!=0){
                    cur=cur.next;
                    index--;
                }
                node.next=cur;
                cur.pre.next=node;
                node.pre=cur.pre;
                cur.pre=node;
    
                return true;
    
            }
            //查找是否包含关键字key是否在单链表当中
            public boolean contains(int key){
                ListNode cur=this.head;
                while (cur!=null){
                    if(cur.data==key){
                        return true;
                    }else {
                        cur=cur.next;
                    }
                }
                return false;
            }
            //删除第一次出现关键字为key的节点
            public void remove(int key){
                if(this.head==null){
                    return;
                }
                ListNode cur=this.head;
                while (cur!=null){
                    if(cur.data==key){
                        if(this.head.data==key){
                            this.head=this.head.next;
                            if(head!=null){
                                head.pre=null;
                            }else{
                                this.tail=null;
                            }
                        }  else{
                            cur.pre.next=cur.next;
                            if(cur.next!=null){
                                cur.next.pre=cur.pre;
                            }else{
                                this.tail=cur.pre;
                            }
    
                        }
    
                        break;
                    }else{
                        cur=cur.next;
    
                    }
                }
    
            }
            //删除所有值为key的节点
            public void removeAllKey(int key){
                if(this.head==null){
                    return;
                }
                ListNode cur=this.head;
                while (cur!=null){
                    if(cur.data==key){
                        if(this.head.data==key){
                            this.head=this.head.next;
                            if(head!=null){
                                head.pre=null;
                            }else{
                                this.tail=null;
                            }
                        }  else{
                            cur.pre.next=cur.next;
                            if(cur.next!=null){
                                cur.next.pre=cur.pre;
                            }else{
                                this.tail=cur.pre;
                            }
                        }
                    }
                        cur=cur.next;
    
    
                }
    
    
    
            }
            //得到单链表的长度
            public int size(){
                ListNode cur=this.head;
                int count=0;
                while(cur!=null){
                    count++;
                    cur=cur.next;
                }
                return count;
    
            }
            public void display(){
    
                ListNode cur=this.head;
                while(cur!=null){
                    System.out.print(cur.data+" ");
                    cur=cur.next;
                }
                System.out.println();
    
            }
            public void clear(){
    
                ListNode cur=this.head;
                while(cur!=null){
                    ListNode curNext=cur.next;
                    cur.pre=null;
                    cur.next=null;
                    cur=curNext;
                }
    
               this.head=null;
               this.tail=null;
    
            }
    
    }

Test.java

public class Test {
        public static void main(String[] args) {
            MyLinkedList myLinkedList=new MyLinkedList();
    
            myLinkedList.addFirst(1);
            myLinkedList.addFirst(2);
            myLinkedList.addFirst(3);
            myLinkedList.display();
            System.out.println("==========================");
            myLinkedList.addLast(4);
            myLinkedList.addLast(5);
            myLinkedList.addLast(6);
            myLinkedList.display();
            System.out.println("====================");
            System.out.println(myLinkedList.size());
            System.out.println("==========================");
    //        myLinkedList.clear();
    //        myLinkedList.display();
              myLinkedList.remove(5);
              myLinkedList.display();
            System.out.println("=============================");
            System.out.println(myLinkedList.contains(6));
            System.out.println("=============================");
            myLinkedList.addLast(9);
            myLinkedList.addLast(9);
            myLinkedList.addLast(9);
            myLinkedList.display();
            System.out.println("=====================");
            myLinkedList.removeAllKey(9);
            myLinkedList.display();
            System.out.println("=======================");
            System.out.println(myLinkedList.addIndex(2, 8888));
            System.out.println(myLinkedList.addIndex(0, 6666));
            System.out.println(myLinkedList.addIndex(7, 168168));
            myLinkedList.display();
    
    
        }
    }

测试结果：

![02ec89b29a2e481b983cc9a172d57674.png][]

[ced485cbb11e458d81a746890b32cf3f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/8035d83f0f754a2486fd44a5364f0611.gif
[Link 1]: https://blog.csdn.net/m0_67995737?type=blog
[Link 2]: https://blog.csdn.net/m0_67995737/category_12000344.html
[Link 3]: https://www.nowcoder.com/link/pc_csdncpt_ylcxx_c
[d27c4f6e224600894205a5a4ed1316a0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/d98961b283bd498b8093afa9ae2da8ad.png
[02ec89b29a2e481b983cc9a172d57674.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/c2208c557e6643aab9351c64f51d9a95.png