《算法与数据结构体系课》-liuyubobobo 课程笔记
上一章,我们从底层实现了一个单链表的数据结构。并且根据这个链表,实现了栈和队列两种数据结构。
但是提到链表,我们其实还有一个非常重要的话题:递归。
链表天然地拥有递归的性质,不过链表是线性的,太过简单,我们使用循环的方式也可以对其进行遍历。
但是从链表开始理解递归,对于后面学习树这种数据结构有很大的帮助,能够打好基础。
203. 移除链表元素
给你一个链表的头节点
head
和一个整数val
,请你删除链表中所有满足Node.val == val
的节点,并返回 新的头节点 。示例1:
输入: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
进行解题,其结构已经在模板中通过注释描述出来了。
我们再来回忆一下,我们如果要删除一个节点,那么最重要的操作就是找到待删除节点的前一个节点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; }
可以看到,使用虚拟头结点,我们前面那些头结点的操作都不需要了,直接统一头结点和其他节点的操作
递归本质上,就是将原来的问题,转化为更小的同一个问题
前一个Sum中,要对n和元素进行求和,通过递归,只需要对n-1个数进行求和,这就是转化为更小的同一个问题。
通过不断递归,我们得到一个最基本的问题Sum([])
,将这个问题解决了,再根据之前的逻辑,就能够将原本的问题进行解决。
当然,这里只是一个例子,对于数组求和来说,没有必要用递归,用循环就行,这里只是帮助大家理解一下递归的本质。
接下来我们使用递归来实现一下数组求和问题
/** * 计算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
我们来分析一下这个递归算法。
所有递归算法都可以分为两部分的:
我们在写递归的时候,经常很出现被递归给绕晕,主要体现在一个看到递归函数,比如sum()
,最后会再次调用自己,这个时候,很多人都不理解。
其实我们在写递归函数的时候,需要注意递归函数的宏观语义,不要想着这是一个递归函数,而是要理解这个函数的功能。因为递归函数也是一个函数,为的就是完成一个功能。比如这里的sum()
函数,就是为了求和。在sum()
函数里面调sum()
函数,在本质上和在sum()
函数里面调别的函数是没有区别的,就是为了满足结果而需要某一项功能。
所以不需要特别微观地陷进这个递归调用里,去纠结递归是如何调用的。我们就把这个递归函数看做一个普通函数,调用自己,只是一个子过程,为的是完成一项功能,和调用其他函数没有区别。调用这个子过程,就是为了构建自己的逻辑,来解决这一层的问题。
对于一个链表来说,我们可以将其理解为一个一个的节点连接起来的线性数据结构,也可以理解为是一个节点和一个更短的链表连接起来的结构。
这就是链表天然的递归
现在我们使用递归的思想,来解决上文中LeetCode中的问题
我们的问题是:给你一个链表的头节点 head
和一个整数 val
,请你删除链表中所有满足 Node.val == val
的节点,并返回 新的头节点 。
我们编写递归函数,其宏观语义就是:删除链表中相应的元素
我们在编写递归函数时,其核心问题就是:如何将递归函数得到的解,来构建成原问题的解?
下面看思路:
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; }
我们在写递归函数时,可以不用去微观地纠结其调用的机制。
但是我们在学习递归的时候还是需要去微观地研究其机制,更好地去理解递归。
回忆一下我们在学习栈的时候,有一个例子:程序调用的系统栈
当我们在一个函数中调用子函数时,会将调用该函数的位置压入这个系统栈,当子函数调用完成之后,根据栈顶找到父函数上次调用子函数的位置,然后继续执行父函数。
其实递归调用和这个函数的调用逻辑没有区别,只不过父函数调用的子函数还是这个函数本身而已。
其实这个图也体现了递归调用的代价:函数调用 + 系统栈空间
递归其实也有自己的优点:使用递归使逻辑的书写更为简洁。
这个优点在线性结构上面很难体现出来,但是在树形结构或者其他结构上,就能体现出来了。
下图展现了上文中的两种递归算法的调用机制
之前我们说,带尾指针的单链表,在尾部添加的时候很简单,时间复杂度为O(1),但是删除的时候还是很复杂,得遍历链表。那么双链表在尾部进行删除的时候,时间复杂度也为O(1)。
其原理就是每一个节点都有两个指针,一个直向下一个节点,一个指向上一个节点。
双向带来的优化还有在遍历时,通过判断需要获取的节点序号和链表长度/2比较,如果index小于链表长度/2,说明节点是偏前的,因此从头结点开始一路next下去。如果大于,说明节点是偏后的,因此从尾节点开始一路prev上去。这样进一步优化了遍历的时间复杂度,从O(n) -> O(logN)
双链表带来便利的同时,也会有一些代价,就是在维护next
和prev
指针的时候,更为复杂一些。
/** * 双链表 * @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 ===================================================
循环链表就是将链表组成一个环,尾节点不再指向空,而是指向虚拟头节点。这个时候就不需要再声明维护尾节点了,因为尾节点就是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 ===================================================