java双向链表解析实现双向链表的创建含代码

🕗 发布于 2024-11-12 03:13 java 链表 开发语言

双向链表

一.双向链表
二.创建MyListCode类实现双向链表创建
接口类
MyListNode整体代码
Test测试类代码

一.双向链表

单向链表从头部开始我们的每一个节点指向后驱的节点。
此处为单向链表
单向链表

双向链表是相互指向前驱以及后驱的链表
前驱链表我们需要在我们的MyListCode内部类中在定义一个previous来接收每一个前驱的地址
在这里插入图片描述想要删除任意节点可以直接通过访问下一个节点使其prev获取想要删除的上一个节点，然后将想要删除的上一个节点.next获取到被删除对象下一个节点的指向

这里我们可以模拟实现MyListCode类中的一些方法，入头插法、尾叉法、任意位置插入节点、指定元素删除含有该元素的第一个节点、指定元素删除含有该元素的所有节点等…

二.创建MyListCode类实现双向链表创建

public class MyListNode implements IList {
  static class Node{
      public int val;
      //获取的后一个节点
      public Node next;
      //获取的前一个节点
      public Node prev;

      public Node(int val) {
          this.val = val;
      }
  }
  //始终在第一个节点
  public Node head;
  //指向最后一个节点
  public Node last;
  }

一.AddFirst创建（头插法）

这里当头部为null，没有头部和尾巴，我们将新节点作为头和尾，如果不为null，将每次产生的新节点对象放到头部，头部的pre与新节点相连，头部更新最新节点

  @Override
    public void addFirst(int data) {
        Node node=new Node(data);
        if(this.head==null){
        //head指向头部，last指向尾巴
            this.head=node;
            this.last=node;
        }else{
        //不为空将新节点插入头部并将头部的pre置为新节点，最后更新头部位置
          node.next=this.head;
          this.head.prev=node;
          this.head=node;
        }
    }

二.AddLast创建（尾叉法）

这里考虑的是当head为空时，我们的头和尾巴都将获取新的节点，如果不为空，我们只需要移动last，将last的下一个节点获取到新的节点，新的节点pre指向last，最后last走向新节点，得到尾巴

 @Override
    public void addLast(int data) {
        Node node=new Node(data);
        if(this.head==null){
            this.head=node;
            this.last=node;
        }else {
            this.last.next = node;
            node.prev = last;
            last=node;
        }
    }

三.size

从头部开始遍历或者尾部开始遍历

 @Override
    public int size() {
        if(this.head==null){
            return 0;
        }
        Node cur=this.head;
        int count=0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
       return count;
    }
     @Override
    public void display() {
        Node cur=this.head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }

四.remove(指定任意节点的首位删除)

首先判断如果头部值为空，说明没有节点，头部的下一个节点如果为key值则直接返回key（因为这里只是删除一个，所以不考虑多个带key的节点），然后遍历如果最后一个节点为key，它的下一个节点为null，则将双向节点置为null，如果不为null，就删除这个节点

  @Override
    public void remove(int key) {
        if (this.head == null) {
            return;
        }
        if(this.head.val==key){
            //头节点为key将其更换为后驱节点，将后驱节点的prev置空
           this.head=this.head.next;
           this.head.prev=null;
           return;
        }
        Node cur=this.head.next;
        while(cur!=null){
            if(cur.val==key){
                //最后一个节点为key将前驱的下一项置空并将cur的pre置空
               if(cur.next==null){
                   cur.prev.next=null;
                   cur.prev=null;
                   return;
               }else{
                   //不是最后一个节点将前驱节的下一节点为当前节点下一项
                   //当前节点的下一项的前驱为当前项的前驱
                   cur.prev.next=cur.next;
                   cur.next.prev=cur.prev;
                   return;
               }
            }
            cur=cur.next;
        }
    }

五.removeAll(包含任意属性值的所有删除)

首先判断是否头部为空
判断最后一个last值是否时key，是key将双节点置空
然后判断key值，将key值在节点中删除
最后判断头节点是否为key，并将头节点置空

@Override
    public void removeAll(int key) {
        if(this.head==null){
            return;
        }
        if(this.last.val==key) {
            //如果最后一项的值为key,将last前一项保留下来，最后赋值给last使其尾部更新
            Node pre=this.last.prev;
            this.last.prev.next = null;
            this.last.prev = null;
            this.last=pre;
        }
        Node cur=this.head.next;
        while(cur!=null){
            //cur的值如果为key清理该节点指向
            if(cur.val==key){
                cur.prev.next=cur.next;
                cur.next.prev=cur.prev;
            }
            cur=cur.next;
        }
        //最后判断head的值是否是key
        if(this.head.val==key){
            this.head=this.head.next;
        }
        //如果head有数据将head头的前节点置空
        if(this.head!=null){
            this.head.prev=null;
        }
    }

六.AddIndex(给任意位置添加一个节点)

首先判断头部是否为空
判断该坐标是否合法，如果该坐标在0或者在尾巴，则头插法和尾叉法
将给的坐标作为循环条件节点开始走，跳出循环后改节点位置就是要添加的位置
首先要把改节点的坐标向后移动一位，插入其中间
单链表的话将cur先指向后一个节点在指向前一个节点

 @Override
    public void addIndex(int index,int data)throws RuntimeException {
        if(this.head==null){
            return;
        }
          try {
            if(index<0||index>size()){
                throw new RuntimeException("错误范围"+size());
            }
        }catch (RuntimeException e){
            e.printStackTrace();
        }
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
        Node node=new Node(data);
        Node cur=this.head;
        while(index>0){
            //出来后就是要插入的范围
            cur=cur.next;
            index--;
        }
        //在任意位置新增一个节点
        node.next=cur;
        node.prev=cur.prev;
        cur.prev=node;
        node.prev.next=node;
        return ;
    }

七.contains(无)

 @Override
    public boolean contains(int key) {
        if(this.head==null){
            return false;
        }
        Node cur=this.head;
        while(cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

八.partition（区分链表的大小范围）

    @Override
    public Node partition(Node node,int x) {
        if (node == null) {
            return null;
        }
        Node cur = node;
        Node min=null;
        Node minEnd=null;
        Node max=null;
        Node maxEnd=null;
        while (cur != null) {
            if(cur.val<x){
                if(min==null){
                    min=cur;
                    minEnd=cur;
                }else{
                    minEnd.next=cur;
                    minEnd=minEnd.next;
                }
            }else{
                if(max==null){
                    max=cur;
                    maxEnd=cur;
                }else{
                    maxEnd.next=cur;
                    maxEnd=maxEnd.next;
                }
            }
            cur = cur.next;
        }
        if(min==null){
            return max;
        }
        if(maxEnd!=null){
            maxEnd.next=null;
        }
        minEnd.next=max;
        return min;
    }
}

九.display(打印)

@Override
    public void display() {
        Node cur=this.head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }

接口类

public interface IList {
    public void display();
    public int size();
    public void addFirst(int data);//新增一个节点放到头部
    public void addLast(int data);//新增一个节点放到尾部
    public void remove(int key);//删除第一个val值为key的节点
    public void removeAll(int key);//删除所有val值的节点
    public void addIndex(int index,int data);//在任意一个位置放入一个节点
    public boolean contains(int key);//是否包含key数值这个节点
    public MyListNode.Node partition(MyListNode.Node node,int x);//指定一个值，将数值小的放在前，将数值大的放在后
}

MyListNode整体代码

import java.util.List;

public class MyListNode implements IList {
  static class Node{
      public int val;
      public Node next;
      public Node prev;

      public Node(int val) {
          this.val = val;
      }
  }
  //始终在第一个节点
  public Node head;
  //指向最后一个节点
  public Node last;

    @Override
    public void addFirst(int data) {
        Node node=new Node(data);
        if(this.head==null){
            this.head=node;
            this.last=node;
        }else{
          node.next=this.head;
          this.head.prev=node;
          this.head=node;
        }
    }

    @Override
    public void addLast(int data) {
        Node node=new Node(data);
        if(this.head==null){
            this.head=node;
            this.last=node;
        }else {
            this.last.next = node;
            node.prev = last;
            last=node;
        }
    }

    @Override
    public int size() {
        if(this.head==null){
            return 0;
        }
        Node cur=this.head;
        int count=0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
       return count;
    }
    public int size2(){
        if(this.head==null){
            return 0;
        }
        Node end=this.last;
        int count=0;
        while(end!=null){
            count++;
            end=end.prev;
        }
        return count;
    }
    @Override
    public void display() {
        Node cur=this.head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    public void display2(){
        Node cur=this.last;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.prev;
        }
        System.out.println();
    }

    @Override
    public void remove(int key) {
        if (this.head == null) {
            return;
        }
        if(this.head.val==key){
            //头节点为key将其更换为后驱节点，将后驱节点的prev置空
           this.head=this.head.next;
           this.head.prev=null;
           return;
        }
        Node cur=this.head.next;
        while(cur!=null){
            if(cur.val==key){
                //最后一个节点为key将前驱的下一项置空并将cur的pre置空
               if(cur.next==null){
                   cur.prev.next=null;
                   cur.prev=null;
                   return;
               }else{
                   //不是最后一个节点将前驱节的下一节点为当前节点下一项
                   //当前节点的下一项的前驱为当前项的前驱
                   cur.prev.next=cur.next;
                   cur.next.prev=cur.prev;
                   return;
               }
            }
            cur=cur.next;
        }
    }

    @Override
    public void removeAll(int key) {
        if(this.head==null){
            return;
        }
        if(this.last.val==key) {
            //如果最后一项的值为key,将last前一项保留下来，最后赋值给last使其尾部更新
            Node pre=this.last.prev;
            this.last.prev.next = null;
            this.last.prev = null;
            this.last=pre;
        }
        Node cur=this.head.next;
        while(cur!=null){
            //cur的值如果为key清理该节点指向
            if(cur.val==key){
                cur.prev.next=cur.next;
                cur.next.prev=cur.prev;
            }
            cur=cur.next;
        }
        //最后判断head的值是否是key
        if(this.head.val==key){
            this.head=this.head.next;
        }
        //如果head有数据将head头的前节点置空
        if(this.head!=null){
            this.head.prev=null;
        }
    }

    @Override
    public void addIndex(int index,int data)throws RuntimeException {
        if(this.head==null){
            return;
        }
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
        try {
            if(index<0||index>size()){
                throw new RuntimeException("错误范围"+size());
            }
        }catch (RuntimeException e){
            e.printStackTrace();
        }
        Node node=new Node(data);
        Node cur=this.head;
        while(index>0){
            //出来后就是要插入的范围
            cur=cur.next;
            index--;
        }
        //在任意位置新增一个节点
        node.next=cur;
        node.prev=cur.prev;
        cur.prev=node;
        node.prev.next=node;
        return ;
    }

    @Override
    public boolean contains(int key) {
        if(this.head==null){
            return false;
        }
        Node cur=this.head;
        while(cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

    @Override
    public Node partition(Node node,int x) {
        if (node == null) {
            return null;
        }
        Node cur = node;
        Node min=null;
        Node minEnd=null;
        Node max=null;
        Node maxEnd=null;
        while (cur != null) {
            if(cur.val<x){
                if(min==null){
                    min=cur;
                    minEnd=cur;
                }else{
                    minEnd.next=cur;
                    minEnd=minEnd.next;
                }
            }else{
                if(max==null){
                    max=cur;
                    maxEnd=cur;
                }else{
                    maxEnd.next=cur;
                    maxEnd=maxEnd.next;
                }
            }
            cur = cur.next;
        }
        if(min==null){
            return max;
        }
        if(maxEnd!=null){
            maxEnd.next=null;
        }
        minEnd.next=max;
        return min;
    }
}

Test测试类代码

public class Test {
    public static void main(String[] args) {
        MyListNode myListNode=new MyListNode();
        myListNode.addLast(3);
        myListNode.addLast(5);
        myListNode.addLast(7);
        myListNode.removeAll(6);
//        System.out.println(myListNode.last.val);
//        myListNode.display();
        myListNode.addIndex(1,9);
        System.out.println(myListNode.contains(3));
        myListNode.display();
        int len1 =  myListNode.size();
       int len2 =  myListNode.size();
        System.out.println(len1+"size");
        System.out.println(len2+"size1");
        MyListNode myListNode1=new MyListNode();
        myListNode1.addLast(3);
        myListNode1.addLast(3);
        myListNode1.addLast(8);
        myListNode1.addLast(9);
        myListNode1.addLast(19);
        myListNode1.addLast(3);
        myListNode1.display();
        myListNode1.display2();
        myListNode1.partition(myListNode1.head,5);
        myListNode1.display();
        myListNode1.display2();

    }
}

写的也有很多不好的地方，希望大佬们多多指点，谢谢！！祝大家开心快乐

原文地址：https://blog.csdn.net/weixin_60489641/article/details/143690333

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：期货配资分账交易系统部署技术栈说明
下一篇：C++数据结构实验题目解析2

Java学习，基本数据类型
System.out.println("最小值：Double.MIN_VALUE=" + Double.MIN_VALUE);System.out.println("最小
阅读更多2024-11-17
创建第一个react项目
通过以上步骤，你已经成功创建并运行了你的第一个React项目。接下来，你可以继续探索React的更多功能，编写更复杂的组件和应用程序。希望这个教程对你有所帮助！如果有任何问题，欢迎随时提问。参考资料R
阅读更多2024-11-17
从零开始的c++之旅——二叉搜索树
这与之前实现的二叉树类似，只不过用上了模板跟构造函数，因为构造函数我们在后面需要用来生成节点。K _key;:_key(key){}//这里也能体现封装思想，不管我们如何实现的类此处我们只需定义成No
阅读更多2024-11-17
c/c++内存管理
int main()// new/delete 和 malloc/free最大区别是 new/delete对于【自定义类型】除了开空间还会调用构造函数和析构函数free(p1);delete p2;/
阅读更多2024-11-17
1、PyTorch介绍与张量的创建
【代码】1、PyTorch介绍与张量的创建。
阅读更多2024-11-17
‌REST风格（Representational State Transfer）
REST风格的核心思想是将Web应用程序的功能作为资源来表示，使用统一的标识符（URI）来对这些资源进行操作，并通过HTTP协议（如GET、POST、PUT、DELETE等）来定义对这些资源的操作。‌
阅读更多2024-11-17
软件测试 —— 自动化基础
自动化是指自动的代替人的行为完成操作，自动化在生活中可以说是随处可见，如：自动洒水机、自动洗手液等，这些生活中的自动案例有效的减少了我们人力的消耗，同时也提高了我们的生活质量，在我们软件中的自动化测试
阅读更多2024-11-17
Python爬虫下载新闻，Flask展现新闻（2）
Python爬虫下载新闻和Flask展现新闻的主要技术
阅读更多2024-11-17
【CSS in Depth 2 精译_057】第九章 CSS 的模块化与作用域 + 9.1 CSS 模块的定义（上）
本篇为《CSS in Depth》全新第2版9.1小节内容的上篇，主要介绍了 CSS 模块化的产生背景及相关概念，并结合上一节层叠图层（cascade layer）的知识，通过一个简单的 messag
阅读更多2024-11-17
分布式事务seata基于docker安装和项目集成seata
分布式系统节点通过网络连接，一定会出现分区问题（P）当分区出现时,系统的一致性和可用性就无法同时满足cp-->不同节点的角色不同ap-->不同节点的角色相同。
阅读更多2024-11-17