Java双向链表的增删改查怎么实现

这篇文章主要介绍“Java双向链表的增删改查怎么实现”,在日常操作中,相信很多人在Java双向链表的增删改查怎么实现问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Java双向链表的增删改查

这篇文章主要介绍“Java双向链表的增删改查怎么实现”,在日常操作中,相信很多人在Java双向链表的增删改查怎么实现问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Java双向链表的增删改查怎么实现”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!

一、认识双向链表

单向链表不仅保存了当前的结点值,还保存了下一个结点的地址

Java双向链表的增删改查怎么实现

双向链表不仅保存了当前节点的值,还保存了上一个结点的地址和下一个结点的地址

Java双向链表的增删改查怎么实现

定义一个双向链表的结点类:

结点中既要保存当前节点的值,还要保存此节点的前驱节点的地址和此节点的后继节点的地址

class DoubleNode{
    public DoubleNode next;
    DoubleNode prev;
    int val;
    DoubleNode tail;

    public DoubleNode() {}

    public DoubleNode(int val) {
        this.val = val;
    }

    public DoubleNode(DoubleNode prev, int val, DoubleNode tail) {
        this.prev = prev;
        this.val = val;
        this.tail = tail;
    }
}

定义一个双向链表类:

既可以从前向后,也可以从后向前,所以在这个类中,即保存一下头结点,也保存一下尾结点的值

public class DoubleLinkedList {
    private int size;
    private DoubleNode head;
    private DoubleNode tail;
}

二、双向链表的增删改查

1.插入

头插

在当前链表的头部插入一个节点,让当前链表的头结点head前驱指向要插入的节点node,然后让node的后继指向head,然后让head = node,让node成为链表的头结点

Java双向链表的增删改查怎么实现

代码如下:

/**
     * 头插
     */
    public void addFirst(int val){
        DoubleNode node = new DoubleNode(val);
        if (head == null){
            head = tail = node;
        }else{
            node.next = head;
            head.prev = node;
            head = node;
        }
        size++;
    }
尾插

和头插一样,只不过在链表的尾部插入

Java双向链表的增删改查怎么实现

代码如下:

 public void addLast(int val){
        DoubleNode node = new DoubleNode(val);
        if (head == null){
            head = tail =node;
        }else{
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
        size++;
    }
在index位置插入

在索引为index的位置插入值为val的节点:

插入还是要找前驱节点,但双向链表找前驱节点比单向链表找前驱节点要灵活很多,单向链表只能从头走到尾,假如此时有100个节点,要在索引为98的位置插入节点,那么双向链表就可以从尾结点开始找,会方便很多

如何判断从前向后找,还是从后向前找?

  • 1.index < size / 2 &ndash; >从前向后找,插入位置在前半部分

  • 2.index > size / 2 &ndash; >从后向前找,插入位置在后半部分

Java双向链表的增删改查怎么实现

代码如下:

/**
     * 在index位置插入
     * @param index
     * @param val
     */
    public void add(int index,int val){
        DoubleNode cur = new DoubleNode(val);
        if (index < 0 || index > size){
            System.err.println("add index illegal");
            return;
        }else{
            if (index == 0){addFirst(val);}
            else if (index == size){addLast(val);}
            else{
                DoubleNode prev = node(index-1);
                DoubleNode next = prev.next;
                cur.next = next;
                next.prev = cur;
                prev.next = cur;
                cur.prev = prev;
            }
        }
        size++;
    }
/**
     * 根据索引值找到对应的结点
     * @param index
     * @return
     */
    private DoubleNode node(int index){
        DoubleNode x = null;
        if (index < size/2){
            x = head;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
        }else{
            x = tail;
            for (int i = size - 1; i > index ; i--) {
                x = x.prev;
            }
        }
        return x;
    }

2.修改

代码如下:

/**
     * 修改双向链表index位置的结点值为newVal
     */
    public int set(int index,int newVal){
        DoubleNode dummyHead = new DoubleNode();
        dummyHead.next = head;
        DoubleNode prev = dummyHead;
        DoubleNode cur = prev.next;
        if (index < 0 || index > size - 1){
            System.err.println("set index illegal");
        }else{
            for (int i = 0; i < index; i++) {
                prev = prev.next;
                cur = cur.next;
            }
        }
        int oldVal = cur.val;
        cur.val = newVal;
        return oldVal;
    }

3.查询

代码如下:

 /**
     * 查询index位置的结点值
     */
    public int get(int index){
        DoubleNode dummyHead = new DoubleNode();
        dummyHead.next = head;
        DoubleNode prev = dummyHead;
        DoubleNode cur = prev.next;
        if (index < 0 || index > size - 1){
            System.err.println("get index illegal");
        }else{
            for (int i = 0; i < index; i++) {
                prev = prev.next;
                cur = cur.next;
            }
        }
        return cur.val;
    }

4.删除

删除index位置的节点

代码如下:

//删除链表index位置的结点
    public void removeIndex(int index){
        if (index < 0 || index > size - 1){
            System.err.println("remove index illegal");
            return;
        }
        DoubleNode cur = node(index);
        unlink(cur);
    }
 /**
     * 删除当前双向链表的node结点
     * 分治法
     * @param node
     */
    private void unlink (DoubleNode node){
        DoubleNode prev = node.prev;
        DoubleNode successor = node.next;
        //1.先处理node的前半部分
        if (prev == null){
            head = successor;
        }else{
            //前驱不为空的情况
            prev.next = successor;
            node.prev = null;
        }
        if (successor == null){
            tail = prev;
        }else{
            successor.prev = prev;
            node.next = null;
        }
        size--;
    }
头删

调用删除任意位置的节点即可

代码如下:

//头删
    public void removeFirst(){
      removeIndex(0);
    }
尾删

调用删除任意位置的节点即可

代码如下:

//尾删
    public void removeLast(){
        removeIndex(size - 1);
    }
删除第一个值为val的节点

代码如下:

//删除第一个值为val的结点
    public void removeValOnce(int val){
        if (head == null){
            return;
        }
        for (DoubleNode x = head;x != null;x = x.next){
            if (x.val == val){
                unlink(x);
                break;
            }
        }
    }

 /**
     * 删除当前双向链表的node结点
     * 分治法
     * @param node
     */
    private void unlink (DoubleNode node){
        DoubleNode prev = node.prev;
        DoubleNode successor = node.next;
        //1.先处理node的前半部分
        if (prev == null){
            head = successor;
        }else{
            //前驱不为空的情况
            prev.next = successor;
            node.prev = null;
        }
        if (successor == null){
            tail = prev;
        }else{
            successor.prev = prev;
            node.next = null;
        }
        size--;
    }
删除所有值为val的值

代码如下:

//删除链表中所有值为val的结点
    public void removeAllVal(int val){
        for (DoubleNode x = head;x != null;){
            if (x.val == val){
                //暂存一下x的下一个结点
                DoubleNode next = x.next;
                unlink(x);
                x = next;
            }else{
                //val不是待删除的元素
                x = x.next;
            }
        }
    }
 /**
     * 删除当前双向链表的node结点
     * 分治法
     * @param node
     */
    private void unlink (DoubleNode node){
        DoubleNode prev = node.prev;
        DoubleNode successor = node.next;
        //1.先处理node的前半部分
        if (prev == null){
            head = successor;
        }else{
            //前驱不为空的情况
            prev.next = successor;
            node.prev = null;
        }
        if (successor == null){
            tail = prev;
        }else{
            successor.prev = prev;
            node.next = null;
        }
        size--;
    }

到此,关于“Java双向链表的增删改查怎么实现”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注恰卡网网站,小编会继续努力为大家带来更多实用的文章!

本站部分文章来自网络或用户投稿,如无特殊说明或标注,均为本站原创发布。涉及资源下载的,本站旨在共享仅供大家学习与参考,如您想商用请获取官网版权,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。
后端

Kotlin1.6.20新功能Context Receivers怎么使用

2022-6-23 15:18:36

后端

bootstrap栅格化的概念是什么

2022-6-23 15:18:50

搜索