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

如烟花般绚烂却又稍纵即逝

发布于 2024-11-26 08:39:17

25700

代码可运行

文章被收录于专栏：javajava

运行总次数：0

代码可运行

一.双向链表

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

双向链表是相互指向前驱以及后驱的链表 前驱链表我们需要在我们的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，则需要将头部指向下一个节点，将头部的上一个节点置空（这里还要考虑头部如果该链表只有一个节点的情况下，下一个节点一定为空，这里将last也置空）当下一个节点head不为空后在将上一个节点置空 如果尾部为key则需要last跳到上一个节点，因为key的上一个节点已经指向了非空值或者空置，这里只需要在后面加一个判断条件，cur==last说明为最后一个节点，又因为该节点需要删除的key，空值没有前驱，这里直接将last改为上一个节点的值然后在if判断条件下返回

  @Override
  public void remove(int key) {
   Node cur=this.head;
        while(cur!=null) {   //判断cur是否与key想等
            if(cur.val==key){
                if(cur==head){//说明key值在第一个节点
                    this.head=head.next;
                    if(this.head==null){//head节点为空的话
                        this.last=null;
                    }else{//走到这里将头部的前驱置为null
                        head.prev=null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if (cur == last) {
                        last=last.prev;
                    } else {
                        cur.next.prev = cur.prev;
                    }
                }
                return;
            }else{
                cur=cur.next;
            }
        }
    }

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

与remove不同的只有return返回的条件和最后的cur=cur.next cur如果是要删除的值就不需要走else了如果是连续删除需要将else去除

  public void removeAll(int key) {
        Node cur=this.head;
        while(cur!=null){
            if(cur.val==key) {
                if (this.head == cur) {//说明为第一个节点
                    this.head = head.next;
                    if (this.head == null) {//说明head的新节点为空
                        this.last = null;
                    } else {//head不为空将上一个节点置空
                        head.prev = null;
                    }
                }
                 else{
                        cur.prev.next = cur.next;//将上一个节点的下一个节点指向cur的下一个节点
                        if (cur == last) {//看是否是最后一个节点
                            this.last=cur.prev;
                        }else {//不是最后一个节点，直接将下一个节点的前一个节点指向cur的前一个节点
                            cur.next.prev = cur.prev;
                        }
                    }
                }
                cur = cur.next;
            }
    }

六.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();
    }

十.clean(释放链表所有节点)

  @Override
    public void clean() {
        //释放所有节点，最后将头部和尾部置空
        Node cur=this.head;
        while(cur!=null){
            Node curNext=cur.next;//接收cur.next来遍历每一个节点的前后驱
            cur.next=null;
            cur.prev=null;
            cur=curNext;
        }
        this.head=null;
        this.last=null;
    }

接口类

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);//指定一个值，将数值小的放在前，将数值大的放在后
    public void clean();//释放链表中的所有节点
}

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) {
        //遍历脸变
        Node cur=this.head;
        while(cur!=null) {   //判断cur是否与key想等
            if(cur.val==key){
                if(cur==head){//说明key值在第一个节点
                    this.head=head.next;
                    if(this.head==null){//head节点为空的话
                        this.last=null;
                    }else{//走到这里将头部的前驱置为null
                        head.prev=null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if (cur == last) {
                        last=last.prev;
                    } else {
                        cur.next.prev = cur.prev;
                    }
                }
                return;
            }else{
                cur=cur.next;
            }
        }
    }

    @Override
    public void removeAll(int key) {
        Node cur=this.head;
        while(cur!=null) {
            if (cur.val == key) {
                if (this.head == cur) {//说明为第一个节点
                    this.head = head.next;
                    if (this.head == null) {//说明head的新节点为空
                        this.last = null;
                    } else {//head不为空将上一个节点置空
                        head.prev = null;
                    }
                } else {
                    cur.prev.next = cur.next;//将上一个节点的下一个节点指向cur的下一个节点
                    if (cur == last) {//看是否是最后一个节点
                        this.last = cur.prev;
                    } else {//不是最后一个节点，直接将下一个节点的前一个节点指向cur的前一个节点
                        cur.next.prev = cur.prev;
                    }
                }
            }
                cur = cur.next;
        }
    }

    @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;
    }

    @Override
    public void clean() {
        //释放所有节点，最后将头部和尾部置空
        Node cur=this.head;
        while(cur!=null){
            Node curNext=cur.next;//接收cur.next来遍历每一个节点的前后驱
            cur.next=null;
            cur.prev=null;
            cur=curNext;
        }
        this.head=null;
        this.last=null;
    }
}

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-11-12，如有侵权请联系 cloudcommunity@tencent.com 删除

java