欢迎来到尧图网

客户服务 关于我们

您的位置：首页 > 房产 > 家装 > 数据结构与算法——Java实现 5.链表

数据结构与算法——Java实现 5.链表

2024/10/25 14:34:50 来源：https://blog.csdn.net/m0_73983707/article/details/142070992  浏览:  次   关键词：数据结构与算法——Java实现 5.链表

目录

一、定义

链表的分类

二、性能

随机访问

插入或删除

三、单向链表

链表内部节点类

① 增加（插入）

1.头插法

2.寻找最后一个节点位置

3.尾插法

4.根据索引位置插入

② 删除

1.删除首个结点

2.获取链表的指定索引节点

3.删除链表指定索引元素节点

4.删除链表中最后一个节点

③ 遍历

1.遍历方式1 loop循环

2.遍历方式2 构造迭代器

3.遍历打印

4.递归遍历

④ 查找

1.根据索引位置查找元素

⑤ 测试方法

四、带哨兵的单向链表

内部节点类

① 插入

1.头插法

2.尾插法

3.根据索引获取链表元素

4.根据索引位置插入

② 删除

1.找到最后一个节点

2.删除第一个节点

3.删除链表中最后一个节点

4.删除链表中指定位置的节点

③ 遍历

1.迭代器循环

2.迭代器循环

3.for循环

④ 接口

⑤ 测试方法

五、带哨兵的双向链表

内部节点类

迭代器

① 查找

1.根据索引查找结点

② 删除

1.按索引删除元素

2.删除链表内第一个元素

3.删除链表的最后一个元素

③ 插入

1.根据索引位置插入元素

2.在链表首位添加元素

3.在链表最后添加元素

④ 遍历

⑤ 测试方法

六、带哨兵的环形链表

迭代器

内部节点类

① 插入

1.在链表开始位置添加元素

2.在链表最后位置添加元素

② 查找

1.根据节点的值查找节点

③ 删除

1.删除第一个元素

2.删除最后一个元素

3.根据结点的值删除

④ 遍历

 1.遍历打印链表元素

⑤ 测试方法

上帝，请赐予我平静，去接受我无法改变的；

给予我勇气，去改变我能改变的

赐我智慧，分辨这两者的区别

                                        —— 24.9.17

中秋佳节快乐！

一、链表的定义

在计算机科学中，链表是根据数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续

链表的分类

1.单向链表：每个元素只知道其下一个元素是谁

2.双向链表：每个元素知道其上一个元素和下一个元素

3.循环链表：通常的链表尾节点tail指向的都是null，而循环链表的tail指向的是头结点head

注：链表的头尾节点不存储数据

二、链表的性能

随机访问

根据index索引查找，时间复杂度O(n)

插入或删除

起始位置：O(1)

结束位置：如果已知 tail 尾节点是O(1)，不知道 tail 尾节点是O(n)

中间位置：根据 index 查找时间+O(1)

三、单向链表

链表内部节点类

    // 内部节点类 对外隐藏起来private static class Node {int value;Node next;// 下一个节点指针public Node(int value, Node next) {this.value = value;this.next = next;}}

① 增加（插入）

1.头插法

将元素添加到头结点的位置

    // 1.1 头插法头部添加public void addFirst(int value) {// 1.链表为空的情况// 头结点初始值为null，可以省略一种情况// head = new Node(value, null);// 2.链表非空head = new Node(value,head);}

2.寻找最后一个节点位置

寻找链表最后一个元素位置

    // 1.2 找到最后一个结点private Node findLast() {// 判断是否为空链表if (head == null) {return null;}Node p;for (p = head; p.next != null ; p = p.next) {}return p;}

3.尾插法

将新元素添加到链表最后一个位置

    // 1.3 尾插法尾部添加public void addLast(int value){Node last = findLast();// 判断链表最后一个元素是否为空if (last == null) {addFirst(value);return;}last.next = new Node(value,null);}

4.根据索引位置插入

    // 1.4 根据索引位置插入public void insert(int index, int value){// 直接头插法插入在最前if(index == 0){addFirst(value);return;}Node preNode = findNode(index - 1); // 找到上一个节点// 找不到if(preNode == null){// 抛异常throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));}preNode.next = new Node(value,preNode.next); // 插入节点的位置等于前一个节点的下一个}

② 删除

1.删除首个结点

    // 2.1 删除第一个节点public void removeFirst(){if(head == null){throw new IllegalArgumentException(String.format("链表为空，删除位置不合法"));}// 头结点指向第二个节点，跳过第一个节点head = head.next;}

2.获取链表的指定索引节点

    // 2.2 根据索引获取链表的值private Node findNode(int value) {int i = 0;// for循环的第一个部分只能定义一句，for循环的第三个部分可以定义多个语句for (Node p = head; p != null; p = p.next,i++) {if(i == value){return p;}}return null;}

3.删除链表指定索引元素节点

    // 2.3 删除链表的指定元素节点public void delete(int index){// 根据索引获取链表的值// index-1：最后一个节点的上一个节点Node preNode = findNode(index-1);if(preNode == null){System.out.println("链表中没有数据");return;}// 前一个指针直接指向被删除节点指向的指针，被删除节点直接丢失preNode.next = preNode.next.next;}

4.删除链表中最后一个节点

    // 2.4 删除链表中最后一个节点public void removeLast(){if(head == null){throw new IllegalArgumentException(String.format("链表为空，删除位置不合法"));}Node node = findLast();node.next = null;// 找到倒数第二个节点Node current = head;while (current.next.next != null) {current = current.next;}current.next = null;return;}

③ 遍历

1.遍历方式1 loop循环

    // 3.1 遍历链表方式1 loop 循环// 通过consumer外部传参public void loop1(Consumer<Integer> consumer){// 初始值指向第一个节点headNode p = head;// 判断下一个节点位置上还有没有元素，若有则继续循环while(p != null){consumer.accept(p.value);p = p.next;}}

2.遍历方式2 构造迭代器

    @Override// 没有名字，被称为匿名内部类 ——> 转换为带名字的内部类public Iterator<Integer> iterator() {// 创建一个迭代器return new NodeIterator();}private class NodeIterator implements Iterator<Integer> {Node p = head;@Overridepublic boolean hasNext() { // 是否有下一个元素return p != null;}@Overridepublic Integer next() { // 返回当前值，并指向下一个元素int v = p.value;p = p.next;return v;}}// 3.2 遍历链表方式2 looppublic void loop2(Consumer<Integer> consumer) {for (Node p = head; p != null; p = p.next) {consumer.accept(p.value);}}

3.遍历打印

    public void test(){int i = 0;// for循环的第一个部分只能定义一句，for循环的第三个部分可以定义多个语句for (Node p = head; p != null; p = p.next,i++) {System.out.println("索引"+i+"的元素是："+p.value);}}

4.递归遍历

    // 4.遍历链表方式3 递归遍历public void loop3(Consumer<Integer> before,Consumer<Integer> after) {// 没有哨兵的单向链表从头指针开始遍历recursion(head,before,after);}// 递归遍历中的递归函数private void recursion(Node curr,Consumer<Integer> before, Consumer<Integer> after){// 针对某个节点要进行的操作if (curr == null){return;}before.accept(curr.value);recursion(curr.next,before,after);after.accept(curr.value);}

④ 查找

1.根据索引位置查找元素

     // 2.2 根据索引获取链表的值private Node findNode(int value) {int i = 0;// for循环的第一个部分只能定义一句，for循环的第三个部分可以定义多个语句for (Node p = head; p != null; p = p.next,i++) {if(i == value){return p;}}return null;}// 4.1 根据索引查找元素public int get(int index) {Node p = findNode(index);if (p == null) {// 抛异常throw new IllegalArgumentException(String.format("index [%d] 不合法%n", index));} else {return p.value;}}

⑤ 测试方法

package Day3SinglyLinkedList;import org.junit.Test;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.DisplayName;import java.util.List;public class test {// test1() 链表的头插法建立和遍历@Testpublic void test1() {SinglyLinkedList list = new SinglyLinkedList();// 头插法list.addFirst(1);list.addFirst(2);list.addFirst(3);list.addFirst(4);list.addFirst(5);list.addFirst(6);list.addFirst(7);list.addFirst(8);list.addFirst(9);// 由循环内实现转移到了操作方实现// 遍历方式1list.loop1(value->{System.out.print(value+" ");});System.out.println();// 遍历方式2list.loop2(value->{System.out.print(value+" ");});System.out.println();// 遍历方式3}// test2() 迭代器遍历@Testpublic void test2(){SinglyLinkedList list = new SinglyLinkedList();list.addFirst(1);list.addFirst(2);list.addFirst(3);list.addFirst(4);for (Integer value : list) {System.out.print(value+" ");}}// test3、链表的尾插法建立和遍历// 根据索引值查找对应位置的元素@Testpublic void test3(){SinglyLinkedList list = new SinglyLinkedList();list.addFirst(4);list.addFirst(3);list.addFirst(2);list.addFirst(1);list.addLast(6);list.addLast(7);list.addLast(8);list.addLast(9);list.test();// 断言Assertions.assertIterableEquals(List.of(1,2,3,4,6,7,8,9), list);int i = list.get(4);System.out.println("根据索引4查找到的元素是："+i);}// test4.根据索引位置插入@Testpublic void test4(){SinglyLinkedList list = new SinglyLinkedList();list.addFirst(1);list.addFirst(2);list.addFirst(3);list.addLast(9);list.addLast(8);list.addLast(7);list.insert(3,4);list.insert(0,0);for (Integer i : list) {System.out.print(i+" ");}}// test5.删除链表第一个元素@Testpublic void test5(){SinglyLinkedList list = new SinglyLinkedList();list.addFirst(4);list.addFirst(3);list.addFirst(2);list.addFirst(1);list.removeFirst();for (Integer i : list) {// 2 3 4System.out.print(i+" ");}System.out.println();list.removeFirst();System.out.println("====================");for (Integer i : list) {// 3 4System.out.print(i+" ");}}// test6.删除链表指定索引的元素@Testpublic void test6(){SinglyLinkedList list = new SinglyLinkedList();list.addFirst(4);list.addFirst(3);list.addFirst(2);list.addFirst(1);list.addLast(5);list.addLast(6);list.addLast(7);list.addLast(8);list.addLast(9);list.delete(5);list.test();}// test7 删除链表中最后一个元素@Testpublic void test7(){SinglyLinkedList list = new SinglyLinkedList();list.addFirst(4);list.addFirst(3);list.addFirst(2);list.addFirst(1);list.addLast(5);list.addLast(6);list.addLast(7);list.addLast(8);list.addLast(9);list.removeLast();list.removeLast();list.test();// 检验空链表的检验// SinglyLinkedList list2 = new SinglyLinkedList();// list2.removeLast();}// test8 用递归对链表进行遍历@Test@DisplayName("递归方式遍历")public void test8(){SinglyLinkedList list = new SinglyLinkedList();list.addFirst(4);list.addFirst(3);list.addFirst(2);list.addFirst(1);list.loop3(value->{System.out.println("before:"+value);}, value->{System.out.println("after:"+value);});}
}

四、带哨兵的单向链表

内部节点类

    // 内部节点类 对外隐藏起来private static class Node {int value;Node next;// 下一个节点指针public Node(int value, Node next) {this.value = value;this.next = next;}}

① 插入

1.头插法

    // 1.1 功能1头插法头部添加public void addFirst(int value) {// 链表不为空insert(0,value);}

2.尾插法

    // 1.2 尾插法尾部添加public void addLast(int value){// 寻找最右一个节点，链表为空最后一个节点是哨兵节点Node last = findLast();// 判断链表最后一个元素是否为空last.next = new Node(value,null);}

3.根据索引获取链表元素

    // 1.3 根据索引获取链表的值private Node findNode(int value) {int i = -1;// for循环的第一个部分只能定义一句，for循环的第三个部分可以定义多个语句for (Node p = head; p != null; p = p.next,i++) {if(i == value){return p;}}return null;}public int get(int index){Node p = findNode(index);if (p == null){// 抛异常throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));}else{return p.value;}}

4.根据索引位置插入

    // 1.4 根据索引位置插入public void insert(int index, int value) throws IllegalArgumentException {Node preNode = findNode(index - 1); // 找到上一个节点if(preNode == null){// 抛异常throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));}preNode.next = new Node(value,preNode.next); // 插入节点的位置等于前一个节点的下一个}

② 删除

1.找到最后一个节点

    // 2.1 找到最后一个结点private Node findLast() {Node p;// 一直遍历直到找到最后一个节点for (p = head; p.next != null ; p = p.next) {}return p;}

2.删除第一个节点

    // 2.2 删除第一个节点public void removeFirst(){delete(0);}

3.删除链表中最后一个节点

    // 2.3 删除链表中最后一个元素public void removeLast(){if(head == null){throw new IllegalArgumentException(String.format("链表为空，删除位置不合法"));}Node node = findLast();node.next = null;// 找到倒数第二个节点Node current = head;while (current.next.next != null) {current = current.next;}current.next = null;return;}

4.删除链表中指定位置的节点

    // 2.4 删除指定链表节点public void delete(int index){// 根据索引获取链表的值// index-1：最后一个节点的上一个节点Node preNode = findNode(index-1);if(preNode == null){System.out.println("链表中没有数据");return;}Node removeNode = preNode.next;if (removeNode == null){throw new IllegalArgumentException();}// 前一个指针直接指向被删除节点指向的指针，被删除节点直接丢失preNode.next = removeNode.next;}

③ 遍历

1.迭代器循环

    // 3.1遍历链表方式1 loop 循环@Override// 没有名字，被称为匿名内部类 ——> 转换为带名字的内部类public Iterator<Integer> iterator() {// 创建一个迭代器return new NodeIterator();}private class NodeIterator implements Iterator<Integer> {Node p = head.next;@Overridepublic boolean hasNext() { // 是否有下一个元素return p != null;}@Overridepublic Integer next() { // 返回当前值，并指向下一个元素int v = p.value;p = p.next;return v;}}// 通过consumer外部传参public void loop1(Consumer<Integer> consumer){// 初始值指向第一个节点headNode p = head.next;// 判断下一个节点位置上还有没有元素，若有则继续循环while(p != null){consumer.accept(p.value);p = p.next;}}

2.迭代器循环

    // 3.2 遍历链表方式2 looppublic void loop2(Consumer<Integer> consumer) {for (Node p = head.next; p != null; p = p.next) {consumer.accept(p.value);}}

3.for循环

    // 3.3 遍历打印public void test(){int i = 0;// for循环的第一个部分只能定义一句，for循环的第三个部分可以定义多个语句for (Node p = head.next; p != null; p = p.next,i++) {System.out.println("索引"+i+"的元素是："+p.value);}}

④ 接口

package Day4GuardSingleList;import java.util.Iterator;public interface NodeIterator {// 没有名字，被称为匿名内部类 ——> 转换为带名字的内部类Iterator<Integer> iterator();
}

⑤ 测试方法

package Day4GuardSingleList;import org.junit.Test;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.DisplayName;import java.util.List;
import java.util.function.Consumer;public class test {@Test@DisplayName("测试 addLast")public void test1() {GuardMethod list = getLinkedList();Assertions.assertIterableEquals(List.of(1,2,3,4,5),list);}@Test@DisplayName("测试，get")public void test2() {GuardMethod list = getLinkedList();Assertions.assertIterableEquals(List.of(1,2,3,4,5),list);Assertions.assertEquals(3,list.get(2));Assertions.assertThrows(IllegalArgumentException.class,() -> list.get(10));}@Test@DisplayName("测试 insert")public void test3() {GuardMethod list = getLinkedList();list.insert(2,5);list.test();System.out.println("————————————————————");GuardMethod list2 = getLinkedList();list2.addFirst(1);list2.test();System.out.println("————————————————————");list2.addFirst(5);list2.test();}@Test@DisplayName("测试 删除")public void test4() {GuardMethod list = getLinkedList();list.test();System.out.println("————————————————————");list.removeLast();list.test();System.out.println("————————————————————");list.delete(3);list.test();System.out.println("————————————————————");list.delete(1);list.test();}// 9.测试创建类对象private GuardMethod getLinkedList(){GuardMethod gm = new GuardMethod();gm.addLast(1);gm.addLast(2);gm.addLast(3);gm.addLast(4);gm.addLast(5);return gm;}
}

五、带哨兵的双向链表

内部节点类

    static class Node{Node prev; // 上一个节点指针int val; // 节点值Node next; // 下一个节点指针public Node(int val, Node prev, Node next) {this.val = val;this.prev = prev;this.next = next;}}private Node head; // 头部哨兵private Node tail; // 尾部哨兵public DoubleGuardMethod(){head = new Node(11,null,null);tail = new Node(04,null,null);head.next = tail;tail.prev = head;}

迭代器

    @Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node p = head.next;@Overridepublic boolean hasNext() {return p != tail;}@Overridepublic Integer next() {int value = p.val;p = p.next;return value;}};}@Overridepublic void forEach(Consumer<? super Integer> action) {Iterable.super.forEach(action);}@Overridepublic Spliterator<Integer> spliterator() {return Iterable.super.spliterator();}

① 查找

1.根据索引查找结点

    // 1.根据索引查找结点 val：索引private Node findNode(int val){int i = -1;// 遍历到尾哨兵时结束for (Node p = head; p != tail ; p=p.next,i++) {// 索引找到时if (i == val)return p;}return null;}

② 删除

1.按索引删除元素

    // 2.1 按索引删除元素public void remove(int val){Node pre = findNode(val-1);if (pre == null){System.out.println("Node not found");return;}Node node = pre.next;if (node == tail){System.out.println("Node not found");}pre.next = node.next;pre.next.prev = pre;}

2.删除链表内第一个元素

    // 2.2 删除链表内第一个元素public void removeFirst(){remove(0);}

3.删除链表的最后一个元素

    // 2.3 删除最后一个元素public void removeLast(){// 删除最后一个节点位置在尾节点的前一个节点Node removed = tail.prev;if (removed == head){System.out.println("您想要删除的链表中没有元素");return;}// 删除的节点之前的节点Node prev = removed.prev;prev.next = tail;tail.prev = prev;}

③ 插入

1.根据索引位置插入元素

    // 3.1 根据索引位置插入元素public void insert(int index, int value){// pre 新节点的上一个节点Node pre = findNode(index-1);if (pre == null){System.out.println("您输入的index不合法");return;}Node next = pre.next;Node node = new Node(value, pre, next);pre.next = node;next.prev = node;}

2.在链表首位添加元素

    // 3.2 在链表首位添加元素public void addFirst(int value){insert(0,value);}

3.在链表最后添加元素

    // 3.3 在链表最后一个位置添加元素public void addLast(int value){Node last = tail.prev;Node newNode = new Node(value,last,tail);last.next = newNode;tail.prev = newNode;}

④ 遍历

    // 4.遍历打印public void test(){int i = 0;// for循环的第一个部分只能定义一句，for循环的第三个部分可以定义多个语句for (Node p = head.next; p != tail; p = p.next,i++) {System.out.println("索引"+i+"的元素是："+p.val);}}

⑤ 测试方法

package Day5GuardDoubleList;import org.junit.Test;public class test {@Testpublic void test1() {DoubleGuardMethod list = getList();System.out.println("[1,2,3,4,5]");list.test();System.out.println("————————————————————————————————");list.addLast(3);System.out.println("[1,2,3,4,5,3]");list.test();System.out.println("————————————————————————————————");System.out.println("[1,2,3,4,5,3,10]");list.addLast(10);list.test();System.out.println("————————————————————————————————");list.insert(1,15);System.out.println("[1,15,2,3,4,5,3,10]");list.test();System.out.println("————————————————————————————————");list.addFirst(0);System.out.println("[0,1,15,2,3,4,5,3,10]");list.test();System.out.println("————————————————————————————————");list.removeFirst();System.out.println("[1,15,2,3,4,5,3,10]");System.out.println("");list.test();System.out.println("————————————————————————————————");list.removeLast();System.out.println("[1,15,2,3,4,5,3]");list.test();System.out.println("————————————————————————————————");System.out.println("[1,15,3,4,5,3,10]");list.remove(2);list.test();}private DoubleGuardMethod getList(){DoubleGuardMethod list = new DoubleGuardMethod();list.addLast(1);list.addLast(2);list.addLast(3);list.addLast(4);list.addLast(5);return list;}}

六、带哨兵的环形链表

迭代器

    @Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {// 从哨兵节点的next节点开始遍历Node p = sentinel.next;@Overridepublic boolean hasNext() {return p != sentinel;}@Overridepublic Integer next() {int val = p.value;p = p.next;return val;}};}

内部节点类

    private static class Node{Node prev;Node next;int value;public Node(Node prev,Node next,int value){this.prev = prev;this.next = next;this.value = value;}}public AnnualListMethod(){sentinel.prev = sentinel;sentinel.next = sentinel;}// 创建哨兵节点private Node sentinel = new Node(null,null,-1);

① 插入

1.在链表开始位置添加元素

    // 1.1 在链表开始位置添加元素// 双向链表考虑四个指针public void addFirst(int value){Node a = sentinel;Node b = sentinel.next;Node added = new Node(sentinel, sentinel.next, value);a.next = added;b.prev = added;}

2.在链表最后位置添加元素

    // 1.2 在链表最后位置添加元素// 双向链表考虑四个指针public void addLast(int value){Node a = sentinel.prev;Node b = sentinel;Node node = new Node(a,b,value);a.next = node;node.next = b;b.prev = node;}

② 查找

1.根据节点的值查找节点

    // 2.1 根据节点的值查找节点private Node findByValue(int value){Node p = sentinel.next;while (p != sentinel){if (p.value == value){return p;}p = p.next;}return null;}

③ 删除

1.删除第一个元素

    // 3.1.删除第一个元素public void removeFirst(){Node node = sentinel.next;if (node == sentinel){System.out.println("链表为空");return;}Node a = sentinel;Node b = node.next;a.next = b;b.prev = a;}

2.删除最后一个元素

    // 3.2 删除最后一个元素public void removeLast(){Node node = sentinel.prev;if (node == sentinel){System.out.println("删除位置不合法");return;}Node a = node.prev;Node b = sentinel;a.next = b;b.prev = a;}

3.根据结点的值删除

    // 3.3 根据结点的值删除public void removeByValue(int value){Node node = findByValue(value);if (node == null){System.out.println("链表中不含这个值");return;}Node a = node.prev;Node b = node.next;a.next = b;b.prev = a;}

④ 遍历

 1.遍历打印链表元素

    // 4.1 遍历打印链表元素public void print(){Node node = new Node(sentinel,sentinel.next,sentinel.next.value);if (node == sentinel){System.out.println("链表为空");return;}while (node.next != sentinel){node = node.next;System.out.print(node.value+" ");}System.out.println();}

⑤ 测试方法

package Day6AnnularList;import org.junit.Test;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.DisplayName;import java.util.List;public class test {@Test@DisplayName("在头部添加元素")public void addFirst(){AnnualListMethod list = new AnnualListMethod();list.addFirst(1);list.addFirst(2);list.addFirst(3);list.addFirst(4);list.addFirst(5);// 断言，比较链表是否相等Assertions.assertIterableEquals(List.of(5,4,3,2,1), list);}@Test@DisplayName("在尾部添加元素")public void addLast(){AnnualListMethod list = new AnnualListMethod();list.addLast(1);list.addLast(2);list.addLast(3);list.addLast(4);list.addLast(5);// 断言，比较链表是否相等Assertions.assertIterableEquals(List.of(1,2,3,4,5), list);}@Test@DisplayName("删除第一个元素")public void removeFirst(){AnnualListMethod list = new AnnualListMethod();list.addLast(1);list.addLast(2);list.addLast(3);list.addLast(4);list.addLast(5);Assertions.assertIterableEquals(List.of(1,2,3,4,5), list);list.removeFirst();Assertions.assertIterableEquals(List.of(2,3,4,5), list);list.removeFirst();Assertions.assertIterableEquals(List.of(3,4,5), list);list.removeFirst();Assertions.assertIterableEquals(List.of(4,5), list);list.removeFirst();Assertions.assertIterableEquals(List.of(5), list);list.removeFirst();Assertions.assertIterableEquals(List.of(),list);list.removeFirst();}@Test@DisplayName("删除最后一个元素")public void removeLast(){AnnualListMethod list = new AnnualListMethod();list.addLast(1);list.addLast(2);list.addLast(3);list.addLast(4);list.addLast(5);Assertions.assertIterableEquals(List.of(1,2,3,4,5), list);list.removeLast();Assertions.assertIterableEquals(List.of(1,2,3,4), list);list.removeLast();Assertions.assertIterableEquals(List.of(1,2,3),list);list.removeLast();Assertions.assertIterableEquals(List.of(1,2),list);list.removeLast();Assertions.assertIterableEquals(List.of(1),list);list.removeLast();Assertions.assertIterableEquals(List.of(),list);list.removeLast();}@Test@DisplayName("通过节点的值删除链表中的节点")public void removeByValue(){AnnualListMethod list = new AnnualListMethod();list.addLast(1);list.print();list.addLast(2);list.print();list.addLast(3);list.print();list.addLast(4);list.print();list.addLast(5);list.print();Assertions.assertIterableEquals(List.of(1,2,3,4,5), list);list.addLast(3);list.print();Assertions.assertIterableEquals(List.of(1,2,3,4,5,3), list);list.addLast(2);list.print();Assertions.assertIterableEquals(List.of(1,2,3,4,5,3,2), list);list.addLast(5);list.print();Assertions.assertIterableEquals(List.of(1,2,3,4,5,3,2,5), list);list.removeByValue(2);list.print();Assertions.assertIterableEquals(List.of(1,3,4,5,3,2,5), list);list.removeByValue(7);list.print();}
}

七、链表——递归遍历

    // 遍历链表方式3 递归遍历 定义两个泛型public void loop3(Consumer<Integer> before,Consumer<Integer> after) {// 没有哨兵的单向链表从头指针开始遍历recursion(head,before,after);}// 递归遍历中的递归函数private void recursion(Node curr,Consumer<Integer> before, Consumer<Integer> after){// 针对某个节点要进行的操作if (curr == null){return;}before.accept(curr.value);recursion(curr.next,before,after);after.accept(curr.value);}
    // test8 用递归对链表进行遍历@Test@DisplayName("递归方式遍历")public void test8(){SinglyLinkedList list = new SinglyLinkedList();list.addFirst(4);list.addFirst(3);list.addFirst(2);list.addFirst(1);list.loop3(value->{System.out.println("before:"+value);}, value->{System.out.println("after:"+value);});}

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

相关资讯

热文排行

最新新闻

推荐新闻

热搜词

Windows系统配置yarn全局变量 快排算法对结构体数组进行二次排序 强推！分享5款AI论文写作一键自动生成器网站 HbuilderX 连接 Genymotion 模拟器 网络安全——防火墙技术 OpenText Fortify 静态代码分析器，静态应用程序安全性测试