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

news/2024/9/18 21:24:18 标签: java, 链表, 开发语言

目录

一、定义

链表的分类

二、性能

随机访问

插入或删除

三、单向链表

链表内部节点类

① 增加（插入）

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)

三、单向链表

链表内部节点类

java">    // 内部节点类 对外隐藏起来
    private static class Node {
        int value;
        Node next;// 下一个节点指针

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

① 增加（插入）

1.头插法

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

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

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

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

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

3.尾插法

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

java">    // 1.3 尾插法尾部添加
    public void addLast(int value){
        Node last = findLast();

        // 判断链表最后一个元素是否为空
        if (last == null) {
            addFirst(value);
            return;
        }
        last.next = new Node(value,null);
    }

4.根据索引位置插入

java">    // 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.删除首个结点

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

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

java">    // 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.删除链表指定索引元素节点

java">    // 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.删除链表中最后一个节点

java">    // 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循环

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

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

java">    @Override
    // 没有名字，被称为匿名内部类 ——> 转换为带名字的内部类
    public Iterator<Integer> iterator() {
        // 创建一个迭代器
        return new NodeIterator();
    }

    private class NodeIterator implements Iterator<Integer> {
        Node p = head;

        @Override
        public boolean hasNext() { // 是否有下一个元素
            return p != null;
        }

        @Override
        public Integer next() { // 返回当前值，并指向下一个元素
            int v = p.value;
            p = p.next;
            return v;
        }
    }

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

3.遍历打印

java">    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.递归遍历

java">    // 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.根据索引位置查找元素

java">     // 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;
        }
    }

⑤ 测试方法

java">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() 链表的头插法建立和遍历
    @Test
    public 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);

        // 由循环内实现转移到了操作方实现
        // 遍历方式1
        list.loop1(value->{
            System.out.print(value+" ");
        });

        System.out.println();

        // 遍历方式2
        list.loop2(value->{
            System.out.print(value+" ");
        });

        System.out.println();

        // 遍历方式3

    }

    // test2() 迭代器遍历
    @Test
    public 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、链表的尾插法建立和遍历
    // 根据索引值查找对应位置的元素
    @Test
    public 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.根据索引位置插入
    @Test
    public 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.删除链表第一个元素
    @Test
    public 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 4
            System.out.print(i+" ");
        }
        System.out.println();
        list.removeFirst();
        System.out.println("====================");
        for (Integer i : list) {
            // 3 4
            System.out.print(i+" ");
        }
    }

    // test6.删除链表指定索引的元素
    @Test
    public 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 删除链表中最后一个元素
    @Test
    public 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);
        });
    }
}

四、带哨兵的单向链表

内部节点类

java">    // 内部节点类 对外隐藏起来
    private static class Node {
        int value;
        Node next;// 下一个节点指针

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

① 插入

1.头插法

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

2.尾插法

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

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

java">    // 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.根据索引位置插入

java">    // 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.找到最后一个节点

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

        }
        return p;
    }

2.删除第一个节点

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

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

java">    // 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.删除链表中指定位置的节点

java">    // 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.迭代器循环

java">    // 3.1遍历链表方式1 loop 循环
    @Override
    // 没有名字，被称为匿名内部类 ——> 转换为带名字的内部类
    public Iterator<Integer> iterator() {
        // 创建一个迭代器
        return new NodeIterator();
    }

    private class NodeIterator implements Iterator<Integer> {
        Node p = head.next;

        @Override
        public boolean hasNext() { // 是否有下一个元素
            return p != null;
        }

        @Override
        public Integer next() { // 返回当前值，并指向下一个元素
            int v = p.value;
            p = p.next;
            return v;
        }
    }
    
    // 通过consumer外部传参
    public void loop1(Consumer<Integer> consumer){
        // 初始值指向第一个节点head
        Node p = head.next;
        // 判断下一个节点位置上还有没有元素，若有则继续循环
        while(p != null){
            consumer.accept(p.value);
            p = p.next;
        }
    }

2.迭代器循环

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

3.for循环

java">    // 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);
        }
    }

④ 接口

java">package Day4GuardSingleList;

import java.util.Iterator;

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

⑤ 测试方法

java">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;
    }
}

五、带哨兵的双向链表

内部节点类

java">    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;
    }

迭代器

java">    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = head.next;
            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public Integer next() {
                int value = p.val;
                p = p.next;
                return value;
            }
        };
    }

    @Override
    public void forEach(Consumer<? super Integer> action) {
        Iterable.super.forEach(action);
    }

    @Override
    public Spliterator<Integer> spliterator() {
        return Iterable.super.spliterator();
    }

① 查找

1.根据索引查找结点

java">    // 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.按索引删除元素

java">    // 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.删除链表内第一个元素

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

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

java">    // 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.根据索引位置插入元素

java">    // 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.在链表首位添加元素

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

3.在链表最后添加元素

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

④ 遍历

java">    // 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);
        }
    }

⑤ 测试方法

java">package Day5GuardDoubleList;

import org.junit.Test;

public class test {
    @Test
    public 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;
    }

}

六、带哨兵的环形链表

迭代器

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

            @Override
            public Integer next() {
                int val = p.value;
                p = p.next;
                return val;
            }
        };
    }

内部节点类

java">    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.在链表开始位置添加元素

java">    // 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.在链表最后位置添加元素

java">    // 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.根据节点的值查找节点

java">    // 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.删除第一个元素

java">    // 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.删除最后一个元素

java">    // 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.根据结点的值删除

java">    // 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.遍历打印链表元素

java">    // 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();
    }

⑤ 测试方法

java">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();
    }
}

七、链表——递归遍历

java">    // 遍历链表方式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);
    }
java">    // 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);
        });
    }


http://www.niftyadmin.cn/n/5664546.html

相关文章

代码随想录算法训练营第五十八天 | 拓扑排序精讲-软件构建

代码随想录算法训练营第五十八天 | 拓扑排序精讲-软件构建

目录 软件构建 思路 拓扑排序的背景 拓扑排序的思路 模拟过程 判断有环 写代码 方法一&#xff1a; 拓扑排序 软件构建 题目链接&#xff1a;卡码网&#xff1a;117. 软件构建 文章讲解&#xff1a;代码随想录 某个大型软件项目的构建系统拥有 N 个文件&#xff0c;文…
阅读更多...
高中数学：立体几何-平面的定义与公理

高中数学：立体几何-平面的定义与公理

文章目录 一、平面定义及画法1、定义2、表示方法 二、公理1、公理12、公理23、公理3 一、平面定义及画法 1、定义 平面是向四周无限延展的。 2、表示方法 我们常用矩形的直观图&#xff0c;即平行四边形表示平面&#xff0e; 我们常用希腊字母α&#xff0c;β&#xff0c…
阅读更多...
windows远程桌面连接ubuntu

windows远程桌面连接ubuntu

通过 Windows 远程连接到 Ubuntu 的桌面环境&#xff0c;可以使用 远程桌面协议&#xff08;RDP&#xff09; 来实现远程登录。 准备工作 一台安装了 Ubuntu 的服务器或计算机。一台 Windows 电脑&#xff08;安装远程桌面客户端&#xff09;。两台机器必须在同一网络中&…
阅读更多...
将硬盘的GPT 转化为MBR格式

将硬盘的GPT 转化为MBR格式

遇到的问题 在重新安装系统时&#xff0c;磁盘遇到无法空间分配给系统。 解决方式 使用Windows10镜像 U盘安装&#xff0c;选择磁盘时&#xff0c;转换磁盘格式为MBR。然后退出安装程序。 Shift F10# 输入 diskpart# 查看磁盘信息 list disk# 选择需要转换的磁盘&#xff0…
阅读更多...
TESSY创建以及设计一个测试用例

TESSY创建以及设计一个测试用例

我们以tessy5.1 IDE为例&#xff0c;给大家展示编写一个测试用例的过程。 还不会创建工程的&#xff0c;可以参考以下这篇文章&#xff1a; TESSY创建单元测试或集成测试工程_tessy 集成测试-CSDN博客 接下来我们以这个作为开始状态进行介绍 1、添加源文件 2、添加头文件路径…
阅读更多...
鸿蒙开发之ArkUI 界面篇 九 QQ音乐登录界面揭秘

鸿蒙开发之ArkUI 界面篇 九 QQ音乐登录界面揭秘

我们需要实现的效果如下图&#xff1a; : 分析&#xff0c;垂直方向&#xff0c;四个按钮&#xff0c;从上往下第一个是Image&#xff0c;第二个是Text、第三个是是Button、第四个是Button&#xff0c;垂直布局用Column&#xff0c;代码实现如下&#xff1a; Entry Component…
阅读更多...
Flask-JWT-Extended登录验证

Flask-JWT-Extended登录验证

1. 介绍 """安装:pip install Flask-JWT-Extended创建对象 初始化与app绑定jwt JWTManager(app) # 初始化JWTManager设置 Cookie 的选项:除了设置 cookie 的名称和值之外&#xff0c;你还可以指定其他的选项&#xff0c;例如&#xff1a;过期时间 (max_age)&…
阅读更多...
2024最新软件测试面试题【1000道题含答案】

2024最新软件测试面试题【1000道题含答案】

1、自动化代码中,用到了哪些设计模式? 单例设计模式 工厂模式PO设计模式数据驱动模式面向接口编程设计模式 2、什么是断言( Assert) ? 断言Assert用于在代码中验证实际结果是不是符合预期结果&#xff0c;如果测试用例执行失败会抛出异常并提供断言日志 3、什么是web自动化…
阅读更多...
最新文章

Copyright @ 2022~2023