《算法与数据结构体系课》-liuyubobobo 课程笔记
链表和递归
上一章，我们从底层实现了一个单链表的数据结构。并且根据这个链表，实现了栈和队列两种数据结构。
但是提到链表，我们其实还有一个非常重要的话题：递归。
链表天然地拥有递归的性质，不过链表是线性的，太过简单，我们使用循环的方式也可以对其进行遍历。
但是从链表开始理解递归，对于后面学习树这种数据结构有很大的帮助，能够打好基础。
LeetCode中的链表问题
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进行解题，其结构已经在模板中通过注释描述出来了。
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;
}
可以看到，使用虚拟头结点，我们前面那些头结点的操作都不需要了，直接统一头结点和其他节点的操作
递归
递归本质上，就是将原来的问题，转化为更小的同一个问题
前一个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
我们来分析一下这个递归算法。
所有递归算法都可以分为两部分的：
- 求解最基本的问题：最基本的问题是不能分解的，需要我们自己编写逻辑
- 递归算法最核心的部分--把原问题转化为更小的问题：我们需要将更小的问题的答案，构建出原问题的答案。
我们在写递归的时候，经常很出现被递归给绕晕，主要体现在一个看到递归函数，比如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
===================================================