数据结构_实现双向链表

发布于：2024-12-22 ⋅ 阅读:(125) ⋅ 点赞:(0)

B站java实现双向链表

image-20241217112746496

学习调试

OK，又不会调试了，直接B站搜索来看看

有点傻了，直接右键就有调试，但是为什么前面没有出现变量的值喃，

image-20241216152833230

因为我没有断点啊，呜呜呜，好菜

image-20241216152604412

断点(直接点击行数)

image-20241216152320363

执行到下一个断点(如果没有断点的话就直接执行到程序结束)

image-20241216152750589

执行一行代码和进入方法中

image-20241216153001955

继续实现代码
00_实现空表

image-20241216153214747

01_现在实现插入

(创建一个新节点，将前指针指向head，head的后指针指向新节点)

image-20241216153540374

image-20241216153659386

开启调试

能看到现在为

image-20241216153343377

image-20241216153300481

在快结束的那个地方下一个断点

，查看能不能插入下一个地址

image-20241216153514043

图解

image-20241216153826814

OK，按照这个要求在添加一个节点，为后面的删除节点作准备

image-20241216154219871

图解

image-20241216154243108

02_顺序输出
    System.out.println("****顺序输出*************");
    System.out.println(head.val);
    System.out.println(head.next.val);
    System.out.println(head.next.next.val);

image-20241216154644061

03_逆序输出

(直接将从最后一个值遍历着来)

    //逆序输出
    DoubleListNode cur=head.next.next;
    System.out.println("****逆序输出*************");
    System.out.println(cur.val);
    System.out.println(cur.prev.val);
    System.out.println(cur.prev.prev.val);
04_现在实现删除操作

直接将待删除的值前一个值的next赋值为待删除的下一个值，

然后再键下一个值的prev赋值为待删除的值

image-20241216155202680

调试得到，2已经被删除了

image-20241216155411267

全部代码
package YX;

public class Main {

    //01——定义双向链表————空表
    static class DoubleListNode{
        private int val;
        private DoubleListNode prev;
        private DoubleListNode next;

        public DoubleListNode(int val){
            this.val=val;
            this.next=null;
            this.prev=null;
        }
    }

//测试集
public static void main(String[] args) {
        DoubleListNode head=new DoubleListNode(1);
        DoubleListNode text=new DoubleListNode(2);
        DoubleListNode text1=new DoubleListNode(3);//再添加一个节点

        //02插入
        head.next=text;
        text.prev=head;  //添加第二个节点

        head.next.next=text1;
        text1.prev=head.next;  //添加第三个节点

        //03顺序输出
    System.out.println("****顺序输出*************");
    System.out.println(head.val);
    System.out.println(head.next.val);
    System.out.println(head.next.next.val);

    //04逆序输出
    DoubleListNode cur=head.next.next;
    System.out.println("****逆序输出*************");
    System.out.println(cur.val);
    System.out.println(cur.prev.val);
    System.out.println(cur.prev.prev.val);

    //05删除节点
    head.next=head.next.next;
    head.next.prev=head;

}
}

ok了，现在的代码有点呆，但是也是基础，先学会这里，再封装

05_封装插入节点函数

思路:

若链表没有节点(也就是头节点，尾节点都是空的)
就将节点添加为头结点，同样它也是尾节点

否则直接将节点添加到尾部
最后更新尾部节点

image-20241216160836140

image-20241216160459993

断点调试

image-20241216160940083

image-20241216161003332

直接操作

    //06封装函数
    //创建头尾节点
    static class DoubleList{
        private DoubleListNode head;
        private DoubleListNode tail;

    public void insetAtEnd(int val){
        DoubleListNode text=new DoubleListNode(val);
        //如果链表没有节点，那么头尾节点都是新添加的节点

        if(this.head==null&& this.tail==null){
            this.head=text;
            this.tail=text;
            return;

        }
        //新节点添加到尾部
        this.tail.next=text;
        text.prev=this.tail;
        this.tail=text;
    }
    }

测试集

//创建一个新对象
DoubleList TEXT=new DoubleList();

TEXT.insetAtEnd(111);
TEXT.insetAtEnd(222);
TEXT.insetAtEnd(333);

image-20241217101105616

06_从头部添加节点

同样也是三步

image-20241216161243882

image-20241216161341814

自己操作

image-20241217101737134

image-20241217101712182

07_从前往后开始遍历

输出头结点，然后开始通过循环遍历

image-20241216162141178

image-20241216162229365

运行程序

08_从后往前开始遍历
        public void hoprint(){
        DoubleListNode text=this.tail;
        while (text!=null){
            System.out.print(text.val+"\t");
            text=text.prev;
        }
            System.out.println();

        }

测试集

    System.out.println("****逆序输出*************");
    TEXT.hoprint();

image-20241217102857698

09_删除节点函数

三种情况

删头节点

[第一步:更新头结点往后

第二步:将原来的头结点的后项指针域断开

第三部:将更新后的头结点的前项指针域为空]

删尾节点

[第一步:更新尾结点往前

第二步:将原来的尾结点的前项指针域断开

第三部:将更新后的尾结点的后项指针域为空]

删中间节点

[第一步:将待删除节点的前节点的后项指针域值向待删除节点的后节点

第二步：在将待删除节点的后节点的前项指针域值向待删除节点的前节点

]

       //10删除节点函数
        public void delete(int val){
        DoubleListNode text=this.head;//为遍历左准备
            while(text!=null) {

                if(text.val==val){//找到删除的值
                    //删除节点为头结点
                    if(text.prev==null){
                        this.head=text.next;
                        text.next=null;
                        this.head.next=null;
                        return;
                    }

                    //删除节点为尾节点
                    if(text.next==null){
                        this.tail=tail.prev;
                        text.prev=null;
                        this.tail.next=null;
                        return;
                    }

                    //删除节点为中间节点
                    text.prev.next=text.next;
                    text.next.prev=text.prev;
                    return;




                }

测试集

    System.out.println("****删除222之后输出*************");
    TEXT.delete(222);
    TEXT.qianprint();

image-20241217105056653

10_全部代码

package YX;

public class Main {

    //01——定义双向链表————空表
    static class DoubleListNode{
        private int val;
        private DoubleListNode prev;
        private DoubleListNode next;

        public DoubleListNode(int val){
            this.val=val;
            this.next=null;
            this.prev=null;
        }
    }



    //06封装函数
    //创建头尾节点
    static class DoubleList{
        private DoubleListNode head;
        private DoubleListNode tail;

    public void insetAtEnd(int val){
        DoubleListNode text=new DoubleListNode(val);
        //如果链表没有节点，那么头尾节点都是新添加的节点

        if(this.head==null&& this.tail==null){
            this.head=text;
            this.tail=text;
            return;

        }
        //新节点添加到尾部
        this.tail.next=text;
        text.prev=this.tail;
        this.tail=text;
    }


    //07头部添加节点
        public void insetAtStart(int val){
        DoubleListNode text=new DoubleListNode(val);
        if(this.head==null&&this.tail==null){
            this.head=text;
            this.tail=text;
            return;
        }
        //新节点添加到头部(三步)
            text.next=this.head;
            this.head.prev=text;
            this.head=text;
        }

        //08完成链表遍历(从前往后遍历)
        public void qianprint(){
        DoubleListNode text =this.head;
        while (text!=null){
            System.out.print(text.val+"\t");
            text=text.next;
        }
        System.out.println();

        }
        //09从后往前遍历
        public void hoprint(){
        DoubleListNode text=this.tail;
        while (text!=null){
            System.out.print(text.val+"\t");
            text=text.prev;
        }
            System.out.println();

        }
        //10删除节点函数
        public void delete(int val){
        DoubleListNode text=this.head;//为遍历左准备
            while(text!=null) {

                if(text.val==val){//找到删除的值
                    //删除节点为头结点
                    if(text.prev==null){
                        this.head=text.next;
                        text.next=null;
                        this.head.prev=null;
                        return;
                    }

                    //删除节点为尾节点
                    if(text.next==null){
                        this.tail=tail.prev;
                        text.prev=null;
                        this.tail.next=null;
                        return;
                    }

                    //删除节点为中间节点
                    text.prev.next=text.next;
                    text.next.prev=text.prev;
                    return;




                }


                text=text.next;

            }
        }







    }





//测试集
public static void main(String[] args) {
        DoubleListNode head=new DoubleListNode(1);
        DoubleListNode text=new DoubleListNode(2);
        DoubleListNode text1=new DoubleListNode(3);//再添加一个节点

        //02插入
        head.next=text;
        text.prev=head;  //添加第二个节点

        head.next.next=text1;
        text1.prev=head.next;  //添加第三个节点

        //03顺序输出
    System.out.println("****顺序输出*************");
    System.out.println(head.val);
    System.out.println(head.next.val);
    System.out.println(head.next.next.val);

    //04逆序输出
    DoubleListNode cur=head.next.next;
    System.out.println("****逆序输出*************");
    System.out.println(cur.val);
    System.out.println(cur.prev.val);
    System.out.println(cur.prev.prev.val);

    //05删除节点
    head.next=head.next.next;
    head.next.prev=head;



    //创建一个新对象
    DoubleList TEXT=new DoubleList();

    TEXT.insetAtEnd(111);
    TEXT.insetAtEnd(222);
    TEXT.insetAtEnd(333);
    //测试头部添加节点
    TEXT.insetAtStart(444);
    TEXT.insetAtStart(444);
    TEXT.insetAtStart(123);

    //测试从前往后输出
    System.out.println("****顺序输出*************");
    TEXT.qianprint();
    System.out.println("****逆序输出*************");
    TEXT.hoprint();
    System.out.println("****删除222之后输出*************");
    TEXT.delete(222);
    TEXT.qianprint();

    System.out.println("****删除尾节点333之后输出*************");
    TEXT.delete(333);
    TEXT.qianprint();


    System.out.println("****删除头节点123之后输出*************");
    TEXT.delete(123);
    TEXT.qianprint();

}
}

还有三个任务没有完成，现在来完成一下

11_ 取第 i 个位置上的元素

//11_取元素
// 取第 i 个位置上的元素
public int getElementAt(int index) {
    DoubleListNode current = this.head;
    int count = 0;
    while (current != null) {
        if (count == index) {
            return current.val; // 找到第 i 个节点，返回其值
        }
        count++;
        current = current.next;
    }
    throw new IndexOutOfBoundsException("Index out of range"); // 如果超出范围，抛出异常
}

测试集

// 测试取第 i 个位置上的元素
System.out.println("****取第 2 个位置上的元素*************");
System.out.println(TEXT.getElementAt(2));

12_返回元素 x 第一次出现在双向循环链表中的位置号

// 求双向循环链表的长度，即元素个数
public int getLength() {
    DoubleListNode current = this.head;
    int count = 0;
    while (current != null) {
        count++;
        current = current.next;
    }
    return count;
}

13_3. 求双向循环链表的长度，即元素个数

// 求双向循环链表的长度，即元素个数
public int getLength() {
    DoubleListNode current = this.head;
    int count = 0;
    while (current != null) {
        count++;
        current = current.next;
    }
    return count;
}

测试集


        // 测试取第 i 个位置上的元素
        System.out.println("****取第 2 个位置上的元素*************");
        System.out.println(TEXT.getElementAt(2));

        // 测试返回元素 x 第一次出现在双向循环链表中的位置号
        System.out.println("****返回元素 222 第一次出现的位置号*************");
        System.out.println(TEXT.findFirstOccurrence(222));

        // 测试求双向循环链表的长度
        System.out.println("****求双向循环链表的长度*************");
        System.out.println(TEXT.getLength());

结束下班

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布