【校招VIP】Java 实现双向链表- 校招VIP

转载声明：文章来源https://blog.csdn.net/m0_52066789/article/details/122342307

1.双链表

1.1 双链表的基本框架

1.2 节点实体类（ListNode）

在这个类中需要有三个属性：

①int val : 存放节点的值

②ListNode prev：存放前一个节点的地址

③ListNode next：存放下一个节点的地址

还有一个有参构造方法用来进行初始化：

public ListNode(int val) {

this.val = val;

}

具体代码：

package DoubleLinkedListTwo;
/**
 * 双链表的节点
 */
public class ListNode {
    public int val;        //当前节点中的数值
    public ListNode prev;  //前节点的地址
    public ListNode next;  //后节点的地址
    //有参构造
    public ListNode(int val){
        this.val = val;
    }
}

1.3 双向链表实体类（DoubleLinkedList）

首先也是要有一个用来存放头节点的属性：head

然后加上一些公开的功能接口：

// 双向链表实体类基本组成框架
public class DoubleLinkedList {
    //存放头节点
    private ListNode head;
    //头插法
    public void addFirst(int data);
    //尾插法
    public void addLast(int data);
    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data);
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key);
    //删除第一次出现关键字为key的节点
    public void remove(int key);
    //删除所有值为key的节点
    public void removeAllKey(int key);
    //得到双链表的长度
    public int size();
    //打印双链表
    public void display();
    //销毁双链表
    public void clear();
}

1.3.1 头插法 — addFirst（int data）

思考：

在写这一部分代码时，我们可以类比于单链表的头插法，也是分为两部分：

①为空链表的情况下怎么去做

②其他情况下的做法，这时我们不仅要关注next的值，还要关注prev的值

具体代码：

//头插法
    public void addFirst(int data){
        //创建新节点
        ListNode node = new ListNode(data);
        //处理是空链表时的情况
        if(this.head == null){
            this.head = node;
        }else{
            //正常情况，next和prev都要进行处理
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }
    }

1.3.2 尾插法 — addLast（int data）

思考：

与头插法的思路大致相同，分为两部分：

① 空链表情况下

②其他情况下，同样要关注 next 和 prev 的值

具体代码：

//尾插法
    public void addLast(int data){
        //创建一个新节点
        ListNode node = new ListNode(data);
        //处理空链表的情况
        if(this.head == null){
            this.head = node;
        }else{
            //正常情况
            ListNode cur = this.head;
            //遍历找到最后一个节点
            while(cur.next != null){
                cur = cur.next;
            }
            //真正进行处理
            cur.next = node;
            node.prev = cur;
        }
    }

1.3.3 根据下标插入新的节点 — addIndex（int index，int data）

思考：

代码的逻辑顺序应满足以下要求：

①先判是否为空链表

②然后判断index(下标)的值是否合法，合法范围：0<= index<= size()(链表当前的节点个数)

③先处理在 index == 0 的情况下插入数据，直接使用头插法（addFirst）

④再处理在 index == size（）的情况下插入数据，使用尾插法（addLast）

⑤最后处理正常情况（在双链表中只要找到了index指向的那个节点就可以直接插入新节点）

具体代码：

//任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
        //判断是否是空链表
        if(this.head == null){
            return false;
        }
        //判断坐标是否合法
        if(index > size() || index < 0){
            System.out.println("下标不合法!");
            return false;
        }
        //在0位置插入
        if(index == 0){
            //头插法
            addFirst(data);
            return true;
        }
        //在末尾插入
        if(index == size()){
            //尾插法
            addLast(data);
            return true;
        }
        //创建节点
        ListNode node = new ListNode(data);
        //循环遍历找到index指向的节点
        ListNode cur = this.head;
        while(index > 0){
            cur = cur.next;
            index--;
        }
        //插入新节点
        node.next = cur;
        node.prev = cur.prev;
        cur.prev.next = node;
        cur.prev = node;
        return true;
    }

1.3.4 查找val的值为key的节点是否在链表中 — contains(int key)

思考：

这个方法比较简单，就是循环遍历链表就可以了。只需要注意遍历时不要直接使用head。

具体代码：

//查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        //不使用head来直接遍历
        ListNode cur = this.head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            //往后走
            cur = cur.next;
        }
        return false;
    }

1.3.5 删除第一次出现val值为key的节点 — remove（int key）

思考：

这里需要注意的有两点，一是要首先判断 head（头节点），二是在正常情况下要判断该节点是不是最后一个节点。代码逻辑如下：

①先判断是不是空链表

②先处理 head（头节点）的 val 值等于 key 的情况

③最后处理正常情况，注意在处理这个业务逻辑的流程中需要区分找到的节点是不是最后一个节点。

具体代码：

//删除第一次出现关键字为key的节点
    public void remove(int key){
        //判断是否是空链表
        if(this.head == null){
            return;
        }
        //判断头节点的val值是否是key
        if(this.head.val == key){
            this.head = this.head.next;
            //前记录点清空
            this.head.prev = null;
            return;
        }
        ListNode cur = this.head;
        //循环遍历
        while(cur != null){
            //找到了
            if(cur.val == key){
                //判断是否是最后一个节点
                if(cur.next == null){
                    //第一次出现是最后一个节点
                    cur.prev.next = null;
                    cur.prev = null;
                    return;
                }else{
                    //第一次出现不是最后一个节点
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                    return;
                }
            }else{
                cur = cur.next;
            }
        }
    }

1.3.6 删除所有 val 值为 key 的节点 — removeAll（int key）

思考：

这个方法与删除第一次的不同在于，删除第一次出现的是删一个，而这个是删除所有。所有这个放法应该是循环删除，但要注意这个方法和上面的方法有所不同，这里的head（头节点）需要放到最后处理。具体的代码逻辑：

①还是先判断是不是空链表

②不管 head（头节点）先处理正常情况，和上面的一样也需要判断找到的那个是不是尾结点

③最后处理 head （有节点）的 val 值等于 key 的情况

具体代码：

//删除所有值为key的节点
    public void removeAll(int key){
        //判断是否为空链表
        if(this.head == null){
            return;
        }
        //先处理正常情况
        ListNode cur = this.head.next;
        //循环遍历链表
        while(cur != null){
            //找到了
            if(cur.val == key){
                //先判断是不是尾节点
                if(cur.next == null){
                    //是尾节点，进行处理
                    cur.prev.next = null;
                    cur.prev = null;
                }else{
                    //不是尾结点，就这样处理
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
            }
            cur = cur.next;   //该节点是与不是都要往后走
        }
        //处理头节点的情况
        if(this.head.val == key){
            this.head = this.head.next;
            //判断头节点处理完毕后是不是成了一个空链表
            if(this.head != null){
                this.head.prev = null;
            }
        }
    }

1.3.7 获取双链表的节点个数 — size（）

思考：

这个很简单，直接遍历就行。

具体代码：

//得到双链表的长度
    public int size(){
        int count = 0;
        ListNode cur = this.head;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

1.3.8 打印双链表 — display（）

思考：

同样是遍历。

具体代码：

//打印双链表
    public void display(){
        ListNode cur = this.head;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        //换一下行
        System.out.println();
    }

1.3.9 销毁双链表 — clear（）

思考：

这里和单链表有所不同，双向链表不能直接使用粗暴的方法，将 head 置null。还是得使用温柔的方法。

具体代码：

//销毁双链表
    public void clear(){
        ListNode cur = this.head;
        //直接使用head
        while(this.head != null) {
            //记录下一个节点的地址
            cur = cur.next;
            //将next和prev都置null
            this.head.prev = null;
            this.head.next = null;
            //更新head的指向，继续处理下一个节点
            this.head = cur;
        }
    }

2. 附上双向链表的测试类

具体代码：

package DoubleLinkedListTwo;
/**
 * 测试双链表
 */
public class TestDoubleLinkedList {
    public static void main(String[] args) {
        //创建一个双链表
        DoubleLinkedList d = new DoubleLinkedList();
        d.addLast(1);
        d.addLast(1);
        d.addLast(1);
        d.addLast(1);
        d.display();
        System.out.println("------------------------");
//        d.addIndex(4,99);
//        d.display();
//        System.out.println(d.contains(5));
//        d.remove(5);
//        d.removeAll(1);
//        d.display();
//        System.out.println(d.size());
        d.clear();
        d.display();
    }
}

运行结果：