4.链表和递归

《算法与数据结构体系课》-liuyubobobo 课程笔记

链表和递归

上一章,我们从底层实现了一个单链表的数据结构。并且根据这个链表,实现了栈和队列两种数据结构。

但是提到链表,我们其实还有一个非常重要的话题:递归。

链表天然地拥有递归的性质,不过链表是线性的,太过简单,我们使用循环的方式也可以对其进行遍历。

但是从链表开始理解递归,对于后面学习树这种数据结构有很大的帮助,能够打好基础。

LeetCode中的链表问题

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点

示例1:
4.链表和递归
输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]

示例2:

输入:head = [], val = 1
输出:[]

示例3:

输入:head = [7,7,7,7], val = 7
输出:[]

解题模板:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {

    }
}

我们需要使用LeetCode定义好的ListNode进行解题,其结构已经在模板中通过注释描述出来了。

solution

我们再来回忆一下,我们如果要删除一个节点,那么最重要的操作就是找到待删除节点的前一个节点prev

如果我们不设计虚拟头节点,那么我们需要对头结点的操作进行特殊处理

    /**
     * 不使用虚拟头结点
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements(ListNode head, int val) {
        //判断head不为空,说明链表不为空
        //使用while循环而不是if,是为了防止删除头结点后,新的头结点的val也等于val
        while (head != null && head.val == val){
            //删除头结点操作
            ListNode delNode = head;
            head = head.next;
            delNode.next = null;
        }
        
        //如果head为空,说明链表已经为空了,则直接返回null即可
        if(head == null){
            return null;
        }

        ListNode prev = head;
        while (prev.next != null){
            //如果当前prev的下一个节点就是待删除节点,则执行删除操作
            if(prev.next.val == val){

                ListNode delNode = prev.next;
                //这一步操作prev已经向后挪了一位
                prev.next = delNode.next;
                delNode.next = null;
            }else {
                prev = prev.next;
            }
        }

        return head;
    }

为了统一头结点和其他节点的操作,我们使用虚拟节点,以下是使用虚拟头结点的解题方法:

    /**
     * 使用虚拟头结点
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements(ListNode head, int val) {

        //我们不需要关系虚拟头结点的val,随便传一个值即可
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;

        ListNode prev = dummyHead;
        while (prev.next != null){
            //如果当前prev的下一个节点就是待删除节点,则执行删除操作
            if(prev.next.val == val){

                ListNode delNode = prev.next;
                //这一步操作prev已经向后挪了一位
                prev.next = delNode.next;
                delNode.next = null;
            }else {
                prev = prev.next;
            }
        }

        return dummyHead.next;
    }

可以看到,使用虚拟头结点,我们前面那些头结点的操作都不需要了,直接统一头结点和其他节点的操作

递归

递归本质上,就是将原来的问题,转化为更小的同一个问题
4.链表和递归

前一个Sum中,要对n和元素进行求和,通过递归,只需要对n-1个数进行求和,这就是转化为更小的同一个问题。

通过不断递归,我们得到一个最基本的问题Sum([]),将这个问题解决了,再根据之前的逻辑,就能够将原本的问题进行解决。

当然,这里只是一个例子,对于数组求和来说,没有必要用递归,用循环就行,这里只是帮助大家理解一下递归的本质。

接下来我们使用递归来实现一下数组求和问题

solution

    /**
     * 计算arr[l...n]这个区间内所有数字的和
     * @param arr 数组
     * @param l 开始索引
     * @return arr[l...n]这个区间内所有数字的和
     */
    private static int sum(int[] arr,int l){
        //最基本的问题,Sum[]
        if(l == arr.length){
            return 0;
        }

        //将计算arr[l..n]这个区间的和转换为更小的问题:计算arr[l+1...n]这个区间的和
        return arr[l] + sum(arr,l +1);
    }

进行验证:

public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        System.out.println("sum:" + sum(arr,0));
    }
>>
sum:15

我们来分析一下这个递归算法。

所有递归算法都可以分为两部分的:

  1. 求解最基本的问题:最基本的问题是不能分解的,需要我们自己编写逻辑
  2. 递归算法最核心的部分--把原问题转化为更小的问题:我们需要将更小的问题的答案,构建出原问题的答案。

4.链表和递归

我们在写递归的时候,经常很出现被递归给绕晕,主要体现在一个看到递归函数,比如sum(),最后会再次调用自己,这个时候,很多人都不理解。

其实我们在写递归函数的时候,需要注意递归函数的宏观语义,不要想着这是一个递归函数,而是要理解这个函数的功能。因为递归函数也是一个函数,为的就是完成一个功能。比如这里的sum()函数,就是为了求和。在sum()函数里面调sum()函数,在本质上和在sum()函数里面调别的函数是没有区别的,就是为了满足结果而需要某一项功能。

所以不需要特别微观地陷进这个递归调用里,去纠结递归是如何调用的。我们就把这个递归函数看做一个普通函数,调用自己,只是一个子过程,为的是完成一项功能,和调用其他函数没有区别。调用这个子过程,就是为了构建自己的逻辑,来解决这一层的问题。

链表天然的递归

对于一个链表来说,我们可以将其理解为一个一个的节点连接起来的线性数据结构,也可以理解为是一个节点和一个更短的链表连接起来的结构。

4.链表和递归

这就是链表天然的递归

现在我们使用递归的思想,来解决上文中LeetCode中的问题

我们的问题是:给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点

我们编写递归函数,其宏观语义就是:删除链表中相应的元素

我们在编写递归函数时,其核心问题就是:如何将递归函数得到的解,来构建成原问题的解?

下面看思路:

4.链表和递归

  1. 我们将原链表看成一个节点 + 一个更短的链表(少了一个节点),调用删除链表中相应元素的函数(调用自己,也就是递归调用,发挥这个函数本身的作用,宏观语义),得到一个结果链表(图中的红色链表)。这里的子过程我们不需要纠结,因为我们只考虑这一层的逻辑,接下来的逻辑交给递归函数,也就是子过程去做。
  2. 这个时候我们只需要考虑这一层的逻辑判断,也就是节点e需不需要被删除,如果需要,则直接返回红色链表即可,如果不需要,则将节点e作为头结点和红色链表一起返回即可。
 /**
     * 递归解决
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements(ListNode head, int val) {

        //最基本问题的解,链表为空的情况
        if(head == null){
            return null;
        }

        //调用递归函数,目的:删除更短链表中相同的元素(宏观语义),得到红色链表
        ListNode res = removeElements(head.next,val);
        //接下来判断head需不需要删除
        if(head.val == val){
            return res;
        }
        else {
            head.next = res;
            return head;
        }
    }

以上代码如果想写得简介一点,也可以写成以下的样子,当然,可读性就差一点,逻辑是一样的

public ListNode removeElements(ListNode head, int val) {
        if(head == null){
            return null;
        }
        head.next = removeElements(head.next,val);
        return head.val == val? head.next : head;
    }

递归的机制,递归函数的微观解答

我们在写递归函数时,可以不用去微观地纠结其调用的机制。

但是我们在学习递归的时候还是需要去微观地研究其机制,更好地去理解递归。

回忆一下我们在学习栈的时候,有一个例子:程序调用的系统栈

4.链表和递归

当我们在一个函数中调用子函数时,会将调用该函数的位置压入这个系统栈,当子函数调用完成之后,根据栈顶找到父函数上次调用子函数的位置,然后继续执行父函数。

其实递归调用和这个函数的调用逻辑没有区别,只不过父函数调用的子函数还是这个函数本身而已。

4.链表和递归

其实这个图也体现了递归调用的代价:函数调用 + 系统栈空间

递归其实也有自己的优点:使用递归使逻辑的书写更为简洁。

这个优点在线性结构上面很难体现出来,但是在树形结构或者其他结构上,就能体现出来了。

下图展现了上文中的两种递归算法的调用机制

4.链表和递归

4.链表和递归

4.链表和递归

链表的其他问题

双向链表

4.链表和递归

之前我们说,带尾指针的单链表,在尾部添加的时候很简单,时间复杂度为O(1),但是删除的时候还是很复杂,得遍历链表。那么双链表在尾部进行删除的时候,时间复杂度也为O(1)。

其原理就是每一个节点都有两个指针,一个直向下一个节点,一个指向上一个节点。

双向带来的优化还有在遍历时,通过判断需要获取的节点序号和链表长度/2比较,如果index小于链表长度/2,说明节点是偏前的,因此从头结点开始一路next下去。如果大于,说明节点是偏后的,因此从尾节点开始一路prev上去。这样进一步优化了遍历的时间复杂度,从O(n) -> O(logN)

双链表带来便利的同时,也会有一些代价,就是在维护nextprev指针的时候,更为复杂一些。

实现

/**
 * 双链表
 * @author 肖晟鹏
 * @email 727901972@qq.com
 * @date 2021/4/8
 */
public class DoubleLinkedList<E> {

    /**
     * 节点
     * 用户不需要知道节点类,用户只需要使用链表类就行了,所以节点作为内部类
     * 我们需要对用户屏蔽数据结构中的实现细节
     */
    private class Node{

        public E e;

        public Node next;

        public Node prev;

        public Node(E e,Node prev,Node next){
            this.e = e;

            this.prev =prev;

            this.next = next;
        }

        public Node(E e){
            this(e,null,null);
        }

        public Node(){
            this(null,null,null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    /**
     * 虚拟节点,链表中的真正头节点的前一个节点
     * 存在意义:便于编写逻辑
     * 对用户是屏蔽的,用户是不知道这个虚拟节点的存在的
     */
    private Node dummyHead;

    /**
     * 尾节点
     */
    private Node tail;

    /**
     * 元素个数
     */
    private int size;

    public DoubleLinkedList(){
        //初始化的时候,创建虚拟节点,使其指向为空
        this.dummyHead = new Node(null,null,null);
        this.size = 0;
    }

    /**
     * 获取链表中的元素个数
     * @return 链表中的元素个数
     */
    public int getSize() {
        return size;
    }

    /**
     * 判断链表是否为空
     * @return true/false
     */
    public boolean isEmpty(){
        return this.size == 0;
    }

    /**
     * 在链表的index位置添加新的元素e
     * 注意,这不是一个常用的操作,只作为练习用
     * @param index 从0开始计数
     */
    public void add(int index, E e) {

        //检查index合法性
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed.Require index >= 0 and index <= size.");
        }

        //在尾部增加元素
        if(index == this.size){
            addLast(e);
            return;
        }

        //先将prev找到
        Node prev = this.traverse(index - 1);

        //插入新节点
        Node node = new Node(e);
        //第一步,我们需要将新节点的next属性指向前节点原先的后面一个节点,并维护后一个节点的prev指针
        node.next = prev.next;
        prev.next.prev = node;
        //第二步,再将前节点的next属性,指向新节点,并维护node的prev指针
        prev.next = node;
        node.prev = prev;

        this.size++;

    }

    /**
     * 向链表的末尾添加一个新的元素e
     * @param e 元素
     */
    public void addLast(E e){
        //如果tail节点为空,则说明链表为空,需要维护头结点
        if(this.tail == null){
            Node node = new Node(e,this.dummyHead,null);
            this.tail = node;
            this.dummyHead.next = node;
        }else {
            //链表不为空,则直接在尾部插入一个节点即可
            Node node = new Node(e);
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
        }
        this.size ++;
    }

    /**
     * 向链表的头添加一个新的元素e
     * @param e 元素
     */
    public void addFirst(E e){
        add(0,e);
    }

    /**
     * 遍历,获取在链表的第index位置的节点
     * 注意,这不是一个常用的操作,只作为练习用
     * @param index 从0开始计数
     * @return 元素
     */
    private Node traverse(int index){

        Node cur;

        //若小于,说明节点是偏前的,因此从head开始一路next下去
        if(index >= this.size / 2){
            //从虚拟头节点开始遍历
            cur = this.dummyHead;
            //需要寻找index节点,所以遍历index次
            for (int i = -1; i < index; i++) {
                cur = cur.next;
            }
        }
        //若大于,说明节点是偏后的,因此从end开始一路prev上去
        else {
            //从尾节点开始遍历
            cur = this.tail;
            for (int i = this.size - 1; i > index ; i--) {
                cur = cur.prev;
            }
        }

        return cur;

    }

    /**
     * 获取在链表的第index位置的元素
     * 注意,这不是一个常用的操作,只作为练习用
     * @param index 从0开始计数
     * @return 第index位置的元素
     */
    public E get(int index){
        //合法性判断
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Index is illegal.Require index >= 0 and index < size.");
        }
        return traverse(index).e;
    }

    /**
     * 获得第一个元素
     * @return 第一个元素
     */
    public E getFirst(){
        return get(0);
    }

    /**
     * 获得最后一个元素
     * @return 最后一个元素
     */
    public E getLast(){
        return get(this.size -1);
    }

    /**
     * 判断链表中是否有元素e
     * @param e 元素e
     * @return true/false
     */
    public boolean contains(E e){

        //从真正的头节点开始遍历,虚拟头节点对用户是屏蔽的,用户是不知道这个虚拟节点的存在的
        Node cur = this.dummyHead.next;
        //另一种遍历方式,cur 只要不为空,则视为有效节点
        while (cur != null){

            if(cur.e.equals(e)){
                //元素相等,返回true
                return true;
            }
            else {
                //元素不相等,向后移动,继续遍历
                cur = cur.next;
            }
        }
        //最后所有的节点都遍历了,还是没有相等的元素,则返回false
        return false;
    }

    /**
     * 修改在链表的第index位置的元素e
     * 注意,这不是一个常用的操作,只作为练习用
     * @param index 从0开始计数
     * @param e 元素
     */
    public void set(int index,E e){
        //合法性判断
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Index is illegal.Require index >= 0 and index < size.");
        }
        //遍历到index位置的节点
        Node cur = traverse(index);
        //修改元素
        cur.e = e;
    }

    /**
     * 删除在链表的第index位置的元素e
     * 注意,这不是一个常用的操作,只作为练习用
     * @param index 从0开始计数
     */
    public E remove(int index){
        //合法性判断
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Remove failed.Require index >= 0 and index < size.");
        }

        //如果是删除尾节点
        if(index == this.size - 1){
            return removeLast();
        }

        //先将prev找到
        Node prev = this.traverse(index - 1);

        Node delNode = prev.next;
        prev.next = delNode.next;
        prev.next.prev = prev;

        delNode.next = null;
        delNode.prev = null;
        this.size --;

        return delNode.e;
    }

    /**
     * 删除第一个元素
     * @return
     */
    public E removeFirst(){
        return remove(0);
    }

    /**
     * 删除最后一个元素
     * @return
     */
    public E removeLast(){
        Node delNode = this.tail;
        this.tail = delNode.prev;
        this.tail.next = null;


        //判空,如果此时tail的上一个节点为空,说明链表空了,需要维护头节点
        if(this.tail.prev == null){
            this.dummyHead.next = null;
        }

        delNode.next = null;
        delNode.prev = null;
        this.size -- ;

        return delNode.e;
    }

    @Override
    public String toString() {
        StringBuilder res=new StringBuilder();

        Node cur = this.dummyHead.next;

        while (cur != null){
            res.append(cur + "<->");
            cur = cur.next;
        }
        res.append(cur);

        return res.toString();
    }
}

可以从代码中看到,其根本的逻辑没什么变化,只是多了一个尾指针和Node中多了一个指向前一个节点的prev

只需要注意在增加和删除元素的时候,需要额外对节点中prev指针进行维护

测试

    public static void main(String[] args) {
        DoubleLinkedList<Integer> linkedList = new DoubleLinkedList<>();
        System.out.println("===================================================");
        System.out.println("Add Head");

        for (int i = 0; i < 5; i++) {
            linkedList.addFirst(i);
            System.out.println(linkedList);
        }

        //在索引为2的位置,增加元素666
        System.out.println("===================================================");
        System.out.println("Add Node 666 to LinkedList where index is 2.");
        linkedList.add(2,666);
        System.out.println(linkedList);
        System.out.println("LinkedList contains node '666' ? " + linkedList.contains(666));
        System.out.println("LinkedList contains node '5' ? " + linkedList.contains(5));
        System.out.println("Index 2 is :" + linkedList.get(2));

        //删除索引为2的元素,即删除666
        System.out.println("===================================================");
        System.out.println("Remove index 2 Node.");
        linkedList.remove(2);
        System.out.println(linkedList);
        //删除头元素
        System.out.println("===================================================");
        System.out.println("Remove head");
        linkedList.removeFirst();
        System.out.println(linkedList);
        System.out.println("Head is dummyHead.next :" + linkedList.getFirst());
        System.out.println("Tail is dummyHead.prev :" + linkedList.getLast());
        System.out.println("===================================================");

        //删除尾元素
        System.out.println("Remove tail");
        linkedList.removeLast();
        System.out.println(linkedList);
        System.out.println("Head is dummyHead.next :" + linkedList.getFirst());
        System.out.println("Tail is dummyHead.prev :" + linkedList.getLast());
        System.out.println("===================================================");

        System.out.println("Remove tail");
        for (int i = 0; i < 3; i++) {
            linkedList.removeLast();
            System.out.println(linkedList);
        }
        System.out.println("===================================================");

        System.out.println("LinkedList is empty? " + linkedList.isEmpty());
        System.out.println("===================================================");
    }
>>
===================================================
Add Head
0<->null
1<->0<->null
2<->1<->0<->null
3<->2<->1<->0<->null
4<->3<->2<->1<->0<->null
===================================================
Add Node 666 to LinkedList where index is 2.
4<->3<->666<->2<->1<->0<->null
LinkedList contains node '666' ? true
LinkedList contains node '5' ? false
Index 2 is :666
===================================================
Remove index 2 Node.
4<->3<->2<->1<->0<->null
===================================================
Remove head
3<->2<->1<->0<->null
Head is dummyHead.next :3
Tail is dummyHead.prev :0
===================================================
Remove tail
3<->2<->1<->null
Head is dummyHead.next :3
Tail is dummyHead.prev :1
===================================================
Remove tail
3<->2<->null
3<->null
null
===================================================
LinkedList is empty? true
===================================================

双向循环链表

4.链表和递归

循环链表就是将链表组成一个环,尾节点不再指向空,而是指向虚拟头节点。这个时候就不需要再声明维护尾节点了,因为尾节点就是dummyHead.prev

循环链表的好处是进一步对链表中的操作进行了统一。我们在双向链表实现的代码中可以看到,加了尾节点之后,我们在增加和判断的时候,是对待增加/删除节点是不是尾节点进行了判断,而在循环链表里面,就不需要这个判断了,所有节点位置的操作都是一样的。

循环链表是非常有用的,Java语言中,LinkedList这个类,就是循环双向链表

实现

/**
 * 循环双向链表
 * @author 肖晟鹏
 * @email 727901974@qq.com
 * @date 2021/4/8
 */
public class CircularLinkedList<E> {

    /**
     * 节点
     * 用户不需要知道节点类,用户只需要使用链表类就行了,所以节点作为内部类
     * 我们需要对用户屏蔽数据结构中的实现细节
     */
    private class Node{

        public E e;

        public Node next;

        public Node prev;

        public Node(E e,Node prev,Node next){
            this.e = e;

            this.prev =prev;

            this.next = next;
        }

        public Node(E e){
            this(e,null,null);
        }

        public Node(){
            this(null,null,null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    /**
     * 虚拟节点,链表中的真正头节点的前一个节点
     * 存在意义:便于编写逻辑
     * 对用户是屏蔽的,用户是不知道这个虚拟节点的存在的
     */
    private Node dummyHead;

    /**
     * 元素个数
     */
    private int size;

    public CircularLinkedList(){
        //初始化的时候,创建虚拟节点,使其指向为空
        this.dummyHead = new Node(null,null,null);
        this.dummyHead.next = this.dummyHead;
        this.dummyHead.prev = this.dummyHead;
        this.size = 0;
    }

    /**
     * 获取链表中的元素个数
     * @return 链表中的元素个数
     */
    public int getSize() {
        return size;
    }

    /**
     * 判断链表是否为空
     * @return true/false
     */
    public boolean isEmpty(){
        return this.size == 0;
    }

    /**
     * 在链表的index位置添加新的元素e
     * 注意,这不是一个常用的操作,只作为练习用
     * @param index 从0开始计数
     */
    public void add(int index, E e) {

        //检查index合法性,-1防止链表为空时,从尾部插入报错
        if (index < -1 || index > size) {
            throw new IllegalArgumentException("Add failed.Require index >= 0 and index <= size.");
        }

        //先将prev找到
        Node prev = this.traverse(index - 1);

        //插入新节点
        Node node = new Node(e);
        //第一步,我们需要将新节点的next属性指向前节点原先的后面一个节点,并维护后一个节点的prev指针
        node.next = prev.next;
        prev.next.prev = node;
        //第二步,再将前节点的next属性,指向新节点,并维护node的prev指针
        prev.next = node;
        node.prev = prev;

        this.size++;

    }

    /**
     * 向链表的末尾添加一个新的元素e
     * @param e 元素
     */
    public void addLast(E e){
        add(this.size - 1,e);
    }

    /**
     * 向链表的头添加一个新的元素e
     * @param e 元素
     */
    public void addFirst(E e){
        add(0,e);
    }

    /**
     * 遍历,获取在链表的第index位置的节点
     * 注意,这不是一个常用的操作,只作为练习用
     * @param index 从0开始计数
     * @return 元素
     */
    private Node traverse(int index){
        Node cur;

        //若小于,说明节点是偏前的,因此从head开始一路next下去
        if(index >= this.size / 2){
            //从虚拟头节点开始遍历
            cur = this.dummyHead;
            //需要寻找index节点,所以遍历index次
            for (int i = -1; i < index; i++) {
                cur = cur.next;
            }
        }
        //若大于,说明节点是偏后的,因此从end开始一路prev上去
        else {
            //从尾节点开始遍历
            cur = this.dummyHead.prev;
            for (int i = this.size - 1; i > index ; i--) {
                cur = cur.prev;
            }
        }

        return cur;

    }

    /**
     * 获取在链表的第index位置的元素
     * 注意,这不是一个常用的操作,只作为练习用
     * @param index 从0开始计数
     * @return 第index位置的元素
     */
    public E get(int index){
        //合法性判断
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Index is illegal.Require index >= 0 and index < size.");
        }
        return traverse(index).e;
    }

    /**
     * 获得第一个元素
     * @return 第一个元素
     */
    public E getFirst(){
        return get(0);
    }

    /**
     * 获得最后一个元素
     * @return 最后一个元素
     */
    public E getLast(){
        return get(this.size -1);
    }

    /**
     * 判断链表中是否有元素e
     * @param e 元素e
     * @return true/false
     */
    public boolean contains(E e){

        Node cur ;
        for (int i = 0; i < this.size; i++) {
            cur = traverse(i);
            if(cur.e == e){
                return true;
            }
        }
        //最后所有的节点都遍历了,还是没有相等的元素,则返回false
        return false;
    }

    /**
     * 修改在链表的第index位置的元素e
     * 注意,这不是一个常用的操作,只作为练习用
     * @param index 从0开始计数
     * @param e 元素
     */
    public void set(int index,E e){
        //合法性判断
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Index is illegal.Require index >= 0 and index < size.");
        }
        //遍历到index位置的节点
        Node cur = traverse(index);
        //修改元素
        cur.e = e;
    }

    /**
     * 删除在链表的第index位置的元素e
     * 注意,这不是一个常用的操作,只作为练习用
     * @param index 从0开始计数
     */
    public E remove(int index){
        if(isEmpty()){
            throw new IllegalArgumentException("Remove failed.LinkedList is empty.");
        }
        //合法性判断
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Remove failed.Require index >= 0 and index < size.");
        }

        //先将prev找到
        Node prev = this.traverse(index - 1);

        Node delNode = prev.next;
        prev.next = delNode.next;
        prev.next.prev = prev;

        delNode.next = null;
        delNode.prev = null;
        this.size --;

        return delNode.e;
    }

    /**
     * 删除第一个元素
     * @return
     */
    public E removeFirst(){
        return remove(0);
    }

    /**
     * 删除最后一个元素
     * @return
     */
    public E removeLast(){
        return remove(this.size - 1);
    }

    @Override
    public String toString() {
        if(isEmpty()){
            return null;
        }

        StringBuilder res=new StringBuilder();

        Node cur = this.dummyHead.next;
        res.append("dummyHead <->" + cur + "<->");
        for (int i = 1; i < this.size; i++) {
            cur = traverse(i);
            res.append(cur + "<->");
        }
        res.append(" dummyHead");
        return res.toString();
    }
}

测试

    public static void main(String[] args) {
        CircularLinkedList<Integer> linkedList = new CircularLinkedList<>();
        System.out.println("===================================================");
        System.out.println("Remove Head");

        for (int i = 0; i < 5; i++) {
            linkedList.addFirst(i);
            System.out.println(linkedList);
        }

        //在索引为2的位置,增加元素666
        System.out.println("===================================================");
        System.out.println("Add Node 666 to LinkedList where index is 2.");
        linkedList.add(2,666);
        System.out.println(linkedList);
        System.out.println("LinkedList contains node '666' ? " + linkedList.contains(666));
        System.out.println("LinkedList contains node '5' ? " + linkedList.contains(5));
        System.out.println("Index 2 is :" + linkedList.get(2));

        //删除索引为2的元素,即删除666
        System.out.println("===================================================");
        System.out.println("Remove index 2 Node.");
        linkedList.remove(2);
        System.out.println(linkedList);
        //删除头元素
        System.out.println("===================================================");
        System.out.println("Remove head");
        linkedList.removeFirst();
        System.out.println(linkedList);
        System.out.println("Head is dummyHead.next :" + linkedList.getFirst());
        System.out.println("Tail is dummyHead.prev :" + linkedList.getLast());
        System.out.println("===================================================");

        //删除尾元素
        System.out.println("Remove tail");
        linkedList.removeLast();
        System.out.println(linkedList);
        System.out.println("Head is dummyHead.next :" + linkedList.getFirst());
        System.out.println("Tail is dummyHead.prev :" + linkedList.getLast());
        System.out.println("===================================================");

        System.out.println("Remove tail");
        for (int i = 0; i < 3; i++) {
            linkedList.removeLast();
            System.out.println(linkedList);
        }
        System.out.println("===================================================");

        System.out.println("LinkedList is empty? " + linkedList.isEmpty());
        System.out.println("===================================================");
    }
>>
===================================================
Remove Head
dummyHead <->0<-> dummyHead
dummyHead <->1<->0<-> dummyHead
dummyHead <->2<->1<->0<-> dummyHead
dummyHead <->3<->2<->1<->0<-> dummyHead
dummyHead <->4<->3<->2<->1<->0<-> dummyHead
===================================================
Add Node 666 to LinkedList where index is 2.
dummyHead <->4<->3<->666<->2<->1<->0<-> dummyHead
LinkedList contains node '666' ? false
LinkedList contains node '5' ? false
Index 2 is :666
===================================================
Remove index 2 Node.
dummyHead <->4<->3<->2<->1<->0<-> dummyHead
===================================================
Remove head
dummyHead <->3<->2<->1<->0<-> dummyHead
Head is dummyHead.next :3
Tail is dummyHead.prev :0
===================================================
Remove tail
dummyHead <->3<->2<->1<-> dummyHead
Head is dummyHead.next :3
Tail is dummyHead.prev :1
===================================================
Remove tail
dummyHead <->3<->2<-> dummyHead
dummyHead <->3<-> dummyHead
null
===================================================
LinkedList is empty? true
===================================================
上一篇:训练模型的剩余时间


下一篇:JDK源码阅读—AtomicInteger