线性表 | 希亚的西红柿のBlog

本篇文章将详细讲述数据结构 线性表 章节的内容，~~没想到距离上次更新已经快两个礼拜了~~。

本教程编程语言采用 JAVA ,文章框架参考自 HUST数据结构PPT ,源码内容参考自 尚硅谷 JAVA 数据结构教程 。

线性表章节部分将简单讲述概念方面的问题，重点将放在具体的代码实现过程中。

线性表的定义

线性表的逻辑结构

线性表：由$n(n≥0)$个数据元素$(a_1,a_2,…, a_n)$构成的有限序列，记作: $L=(a_1,a_2,…,a_n)$，$a_1$称为首元素，$a_n$称为尾元素。
表长：线性表中数据元素的数目。
空表：不含数据元素的线性表。

在线性表$L=(a_1,a_2,…,a_n)$中：

$a_{i-1}$是$a_i$的直接前驱（1<i<=n）
$a_{i+1}$是$a_i$的直接后继（1<=i<n）
$a_1$没有前驱，$a_n$没有后继,$a_i$有且仅有一个前驱和后继（1<i<n）

抽象数据类型线性表的定义

抽象类型的线性表主要定义几个属性和方法

InitList(&L) //构造空表 L。
LengthList(L) //求表 L 的长度
GetElem(L,i,&e) //取元素 ai,由 e 返回 ai
PriorElem(L,ce,&pre_e) //求 ce 的前驱,由 pre_e 返回
InsertElem(&L,i,e) //在元素 ai 之前插入新元素 e
DeleteElem(&L,i) //删除第 i 个元素
EmptyList(L) //判断 L 是否为空表

线性表的顺序表示（顺序存储结构）

顺序分配

定义：将线性表中的数据元素依次存放到计算机存储器中一组地址连续的存储单元中, 这种分配方式称为顺序分配或顺序映像。由此得到的存储结构称为顺序存储结构或向量(一维数组）。
线性表的几个参数
- a:首元素的地址。
- sizeof(a[0]):线性表元素所占的储存空间的大小。
- sizeof(a[n]):线性表的长度。

寻址公式

顺序储存方式的地址查询与数组类似，故不再赘述，感兴趣的读者可以自己查询相关资料。

顺序储存结构的评价

是一种随机存取结构，存取任何元素的时间是一个常数，速度快。
结构简单，逻辑上相邻的元素在物理上也是相邻的。
不使用指针，节省存储空间。

插入和删除元素要移动大量元素，消耗大量时间。
需要一个连续的存储空间。
插入元素可能发生“溢出”。
自由区中的存储空间不能被其它数据占用(共享)。

稀疏数组的实现

书写思路：

二维数组转稀疏数组:
1. 遍历原始二维数组得到，有效数字的个数sum。
2. 创建稀疏数组int[sum+1][3]。
3. 记录chessRow和chessCol以及有效数字count。
4. 遍历数组,为稀疏数组sparseArr赋值。
5. 返回稀疏数组。

稀疏数组转二维数组:

1. 创建原有大小的二维数组。 2. 将稀疏数组中的有效数字返回到原来的二维数组中。 3. 返回原来的二维矩阵。 2. 代码实现:

查看代码实现

编写函数

package DataStructure;

public class SparseArray {
    // 主函数：负责打印原始数组，转换后的稀疏数组，以及在转换回来的二维数组
    public static void main(String[] args) {
        int[][] chessArr = new int[11][11];
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;
        chessArr[5][5] = 5;
        System.out.println("Raw array preview:");
        printChessArray(chessArr);

        int[][] sparseArr = chessToSparse(chessArr);
        System.out.println("chessArray to sparseArray:");
        printChessArray(sparseArr);

        int[][] chessArr2 = sparseToChess(sparseArr);
        System.out.println("sparseArray to chessArray:");
        printChessArray(chessArr2);
    }

    // 二维数组转稀疏数组：
    // 1. 记录有效数字的个数sum
    // 2. 创建稀疏数组int[sum+1][3]
    // 3. 记录chessRow和chessCol以及有效数字count
    // 4. 遍历数组,为稀疏数组sparseArr赋值
    // 5. 返回稀疏数组
    private static int[][] chessToSparse(int[][] chessArr) {
        int sum = 0;
        for (int[] row : chessArr) {
            for (int chess : row) {
                if (chess != 0) {
                    sum++;
                }
            }
        }
        int[][] sparseArr = new int[sum + 1][3];
        int chessRow = chessArr.length;
        int chessCol = 0;
        int count = 0;
        for (int i = 0; i < chessArr.length; i++) {
            int[] rows = chessArr[i];
            if (chessCol == 0) {
                chessCol = rows.length;
            }
            for (int j = 0; j < rows.length; j++) {
                int chess = rows[j];
                if (chess == 0) {
                    continue;
                }
                count++;
                sparseArr[count][0] = i;
                sparseArr[count][1] = j;
                sparseArr[count][2] = chess;
            }
        }
        sparseArr[0][0] = chessRow;
        sparseArr[0][1] = chessCol;
        sparseArr[0][2] = sum;
        return sparseArr;
    }

    /*
     * 1. 创建原有大小的二维数组
     * 2. 将稀疏数组中的有效数字返回到原来的二维数组中
     * 3. 返回原来的二维矩阵
     */
    private static int[][] sparseToChess(int[][] sparseArr) {
        int[][] chessArr = new int[sparseArr[0][0]][sparseArr[0][1]];
        for (int i = 1; i < sparseArr.length; i++) {
            int[] rows = sparseArr[i];
            chessArr[rows[0]][rows[1]] = rows[2];
        }
        return chessArr;
    }

    /*
     * 通过两个for循环每行循环打印输出
     */
    public static void printChessArray(int[][] chessArr) {
        for (int[] row : chessArr) {
            for (int data : row) {
                System.out.printf("%-2d\t", data);
            }
            System.out.println("");
        }
    }
}

输出结果

Raw array preview:
     0       0       0       0       0       0       0       0       0       0
     0       1       0       0       0       0       0       0       0       0
     0       0       2       0       0       0       0       0       0       0
     0       0       0       0       0       0       0       0       0       0
     0       0       0       0       0       0       0       0       0       0
     0       0       0       0       5       0       0       0       0       0
     0       0       0       0       0       0       0       0       0       0
     0       0       0       0       0       0       0       0       0       0
     0       0       0       0       0       0       0       0       0       0
     0       0       0       0       0       0       0       0       0       0
     0       0       0       0       0       0       0       0       0       0
chessArray to sparseArray:
    11      3
     2       1
     3       2
     5       5
sparseArray to chessArray:
     0       0       0       0       0       0       0       0       0       0
     0       1       0       0       0       0       0       0       0       0
     0       0       2       0       0       0       0       0       0       0
     0       0       0       0       0       0       0       0       0       0
     0       0       0       0       0       0       0       0       0       0
     0       0       0       0       5       0       0       0       0       0
     0       0       0       0       0       0       0       0       0       0
     0       0       0       0       0       0       0       0       0       0
     0       0       0       0       0       0       0       0       0       0
     0       0       0       0       0       0       0       0       0       0
     0       0       0       0       0       0       0       0       0       0

线性表的链式存储结构

基本概念

链表是以节点的方式来存储，是 链式存储。
每个节点包含 data 域、next 域，next 域指向下一个节点。
链表还分：带头节点、不带头节点，根据实际需求来确定。
链表的各个节点不一定是连续存储。

单链表

单链表的一般形式

单链表的代码实现(考虑一个这样的场景使用带头单链表实现P5R Phantom Thieves原教程是用的水浒传英雄的管理为啥我换成P5R呢？这是因为vscode Junit单元测试的时候输出中文乱码，我上网搜索了一下也没什么好的解决办法，索性全部用英文算了，正好最近我在打P5R就干脆拿来用了。的成员管理)

查看代码实现

完成对怪盗团成员的增删查改操作。
第一种方法：在添加成员时,直接添加到链表的尾部。
第二种方法：在添加成员时,根据序号将成员添加到指定的位置，如果有这个序号，则添加失败并给出提示。

构造链表节点的类

// 构造链表中的一个节点
class HeroNode {
    // 定义4个基本属性
    public int no; // 序号
    public String name; // 名字
    public String nickName; // 代号
    public HeroNode next; // 指针域

    // 书写构造函数
    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    // 为方便重新打印重写toString函数
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

单链表反转思路

定义一个新的reverseHead节点。

从原链表中依次取出节点，并始终添加到reverseHead的第一个节点。
next = cur.next;
cur.next = reverseHead.next;
reverseHead.next = cur;
cur = next;

将head节点的next指向reverseHead节点的next。

构造链表类

// 单向链表节点的书写
class SingleLinkedList {
    // 创建一个头节点
    private HeroNode head = new HeroNode(0, "", "");

    // 添加节点，将新加入的元素添加至链表的最后

    public void add(HeroNode node) {
        HeroNode temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = node;
    }

    // 打印链表中的数据
    public void list() {
        if (head.next == null) {
            System.out.println("The linked list is empty!");
            return;
        }
        HeroNode temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }

    // 有序插入元素
    public void addByOrder(HeroNode node) {
        // 分为节点为空 大于 相等三种情况来书写函数
        HeroNode temp = head; // 此处temp为辅助变量存放在栈中，指向堆空间的head
        boolean exist = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no > node.no) {
                break;
            }
            if (temp.next.no == node.no) {
                exist = true;
                break;
            }
            temp = temp.next;
        }
        if (exist) {
            System.out.printf("The phantom thief number %d to be inserted already exists and can't be added! \n",
                    node.no);
            return;
        }
        node.next = temp.next;
        temp.next = node;
    }

    // 书写更新链表数据函数
    public void update(HeroNode newNode) {
        // 分为空和相等来区分计算
        if (head.next == null) {
            System.out.println("The linked list is empty!");
            return;
        }
        HeroNode temp = head.next;
        boolean exist = false;
        while (true) {
            if (temp == null) {
                System.out.println("The linked list is empty!");
                return;
            }
            if (temp.no == newNode.no) {
                exist = true;
                break;
            }
            temp = temp.next;
        }
        if (exist) {
            temp.name = newNode.name;
            temp.nickName = newNode.nickName;
        } else {
            System.out.printf("Phantom thief with number %d not found", newNode.no);
        }
    }

    // 删除节点操作
    public void delete(int no) {
        if (head.next == null) {
            System.out.println("The linked list is empty!");
            return;
        }
        HeroNode temp = head;
        boolean exist = false; // 是否找到要删除的节点
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == no) {
                exist = true;
                break;
            }
            temp = temp.next;
        }
        if (!exist) {
            System.out.printf("Phantom thief with number %d not found! \n", no);
            return;
        }
        // 删除操作
        temp.next = temp.next.next;
    }

    // 统计有效节点的个数，即遍历链表
    public int length() {
        HeroNode temp = head.next;
        int num = 0;
        if (head.next == null) {
            return 0;
        }
        while (temp != null) {
            num++;
            temp = temp.next;
        }
        return num;
    }

    // 查找单链表中的倒数第k个节点
    public HeroNode findLastIndexNode(int index) {
        // 通过size与index的大小来判断
        int size = length();
        if (size == 0) {
            return null;
        }
        if (index <= 0 || index > size) {
            return null;
        }
        HeroNode cur = head.next;
        for (int i = 0; i < size - index; i++) {
            cur = cur.next;
        }
        return cur;
    }

    // 单链表的反转
    public void reverse() {
        // 始终添加到第一个节点
        if (head.next == null) {
            return;
        }
        HeroNode cur = head.next;
        HeroNode next = null;
        HeroNode reverseHead = new HeroNode(0, "", "");

        while (cur != null) {
            next = cur.next; // 储存下一个元素的指针
            cur.next = reverseHead.next;
            reverseHead.next = cur;
            cur = next;
        }
        head.next = reverseHead.next;
    }

    public void reversePrint() {
        if (head.next == null) {
            System.out.println("The Linked List is Empty!");
            return;
        }

        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;
        // 遍历原链表，入栈
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        // 打印栈
        while (!stack.empty()) {
            System.out.println(stack.pop());
        }
    }
}

测试函数

public static void main(String[] args) {
    SingleLinkedListDemo singleLinkedListDemo = new SingleLinkedListDemo();
    singleLinkedListDemo.test1();
    singleLinkedListDemo.test2();
}

public void test1() {
    HeroNode hero1 = new HeroNode(1, "Amamiya Ren", "Joker");
    HeroNode hero2 = new HeroNode(2, "Ryuji Sakamoto", "Skull");
    HeroNode hero3 = new HeroNode(3, "Anne Takamaki", "Panther");
    HeroNode hero4 = new HeroNode(4, "Yusuke Kitagawa", "Fox");
    SingleLinkedList singleLinkedList = new SingleLinkedList();
    singleLinkedList.add(hero1);
    singleLinkedList.add(hero2);
    singleLinkedList.add(hero3);
    singleLinkedList.add(hero4);
    singleLinkedList.list();
}

public void test2() {
    HeroNode hero1 = new HeroNode(1, "Amamiya Ren", "Joker");
    HeroNode hero2 = new HeroNode(2, "Ryuji Sakamoto", "Skull");
    HeroNode hero3 = new HeroNode(3, "Anne Takamaki", "Panther");
    HeroNode hero4 = new HeroNode(4, "Yusuke Kitagawa", "Fox");

    SingleLinkedList singleLinkedList = new SingleLinkedList();

    singleLinkedList.addByOrder(hero4); // 添加顺序提前
    singleLinkedList.addByOrder(hero2);
    singleLinkedList.addByOrder(hero1);
    singleLinkedList.addByOrder(hero3);
    singleLinkedList.addByOrder(hero3);
    singleLinkedList.list();
}

private SingleLinkedList singleLinkedList;

@Before
public void before() {
    HeroNode hero1 = new HeroNode(1, "Amamiya Ren", "Joker");
    HeroNode hero2 = new HeroNode(2, "Ryuji Sakamoto", "Skull");
    HeroNode hero3 = new HeroNode(3, "Anne Takamaki", "Panther");
    HeroNode hero4 = new HeroNode(4, "Yusuke Kitagawa", "Fox");

    singleLinkedList = new SingleLinkedList();

    singleLinkedList.addByOrder(hero4); // 添加顺序提前
    singleLinkedList.addByOrder(hero2);
    singleLinkedList.addByOrder(hero1);
    singleLinkedList.addByOrder(hero3);
}

@Test
public void updateTest() {
    // 测试修改
    System.out.println("Before update:");
    singleLinkedList.list();
    HeroNode hero4New = new HeroNode(4, "Yusuke Kitagawa-Test", "Fox-Test");
    singleLinkedList.update(hero4New);

    System.out.println("After update:");
    singleLinkedList.list();
}

@Test
public void deleteTest() {
    System.out.println("Before deletion:");
    singleLinkedList.list();
    singleLinkedList.delete(1);
    singleLinkedList.delete(4);
    System.out.println("After deletion:");
    singleLinkedList.list();
}

@Test
public void lengthTest() {
    System.out.println(singleLinkedList.length());
    singleLinkedList.delete(1);
    System.out.println(singleLinkedList.length());
}

@Test
public void findLastIndexNodeTest() {
    singleLinkedList.list();
    System.out.println("Search Test");
    HeroNode lastIndexNode = singleLinkedList.findLastIndexNode(1);
    System.out.println("Find the 1st last " + lastIndexNode);
    lastIndexNode = singleLinkedList.findLastIndexNode(4);
    System.out.println("Find the 4th last " + lastIndexNode);
    lastIndexNode = singleLinkedList.findLastIndexNode(2);
    System.out.println("Find the 2nd last " + lastIndexNode);
    lastIndexNode = singleLinkedList.findLastIndexNode(5);
    System.out.println("Find the 5th last " + lastIndexNode);
}

@Test
public void reverseTest() {
    System.out.println("Before reversal:");
    singleLinkedList.list();

    singleLinkedList.reverse();

    System.out.println("After reversal:");
    singleLinkedList.list();
}

@Test
public void reversePrintTest() {
    System.out.println("The data of the linked list:");
    singleLinkedList.list();
    System.out.println("Print in reverse order:");
    singleLinkedList.reversePrint();
}

输出结果

Test1:
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}

Test2:
The phantom thief number 3 to be inserted already exists and can't be added!
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}

updateTest:
Before update:
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
After update:
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
HeroNode{no=4, name='Yusuke Kitagawa-Test', nickName='Fox-Test'}

deleteTest:
Before deletion:
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
After deletion:
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}

lengthTest:
4
3

findLastIndexNodeTest:
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
Search Test
Find the 1st last HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
Find the 4th last HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
Find the 2nd last HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
Find the 5th last null

reverseTest:
Before reversal:
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
After reversal:
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}

reversePrintTest:
The data of the linked list:
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
Print in reverse order:
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}

双向链表

双向链表节点定义与单向链表大致相同，只不过多了一个指向前一个节点的指针域。

双向链表相关函数的实现思路

基本实现思路与单向链表相同，可在前者的基础上作出修改

双向链表的代码实现

查看代码实现

函数编写

package DataStructure.DoubleLinkedListPackage;

class HeroNode {
    // 基本的元素与构造元素与单链表基本相同，主要多了一个pre域
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;
    public HeroNode pre;

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    // 重写函数也基本一致
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

// 对双向链表类进行编写
public class DoubleLinkedList {
    // 同样的，初始化一个最初的节点
    private HeroNode head = new HeroNode(0, "", "");

    // 将节点添加到链表的尾部
    public void add(HeroNode node) {
        HeroNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
        node.pre = temp;
    }

    // 修改值的函数，与单向链表基本相同
    public void update(HeroNode newNode) {
        if (head.next == null) {
            System.out.println("The linked list is empty!");
            return;
        }

        HeroNode temp = head;
        boolean exist = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.no == newNode.no) {
                exist = true;
                break;
            }
            temp = temp.next;
        }
        if (exist) {
            temp.name = newNode.name;
            temp.nickName = newNode.nickName;
        } else {
            System.out.printf("no element found with number: %d !", newNode.no);
        }
    }

    // 删除函数与单向链表的思路基本相同，需要注意删除的操作以及最后一位元素的删除处理
    public void delete(int no) {
        if (head.next == null) {
            System.out.println("The linked list is empty!");
            return;
        }

        HeroNode temp = head.next;
        boolean exist = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.no == no) {
                exist = true;
                break;
            }
            temp = temp.next;
        }
        if (!exist) {
            System.out.printf("no element found with number: %d !", no);
            return;
        }
        if (temp.next != null) {
            temp.next.pre = temp.pre;
        }
        temp.pre.next = temp.next;
    }

    // 打印链表
    public void print() {
        if (head.next == null) {
            System.out.println("The linked list is empty!");
            return;
        }
        HeroNode cur = head.next;
        while (cur != null) {
            System.out.println(cur);
            cur = cur.next;
        }
    }

    // 按序添加
    public void addByOrder(HeroNode node) {
        HeroNode temp = head;
        boolean exist = false; // 添加的节点是否已经在链表中存在

        while (true) {
            // 已到列表尾部
            if (temp.next == null) {
                break;
            }
            // 已找到
            if (temp.next.no > node.no) {
                break;
            }

            // 已存在该编号
            if (temp.next.no == node.no) {
                exist = true;
                break;
            }
            temp = temp.next;
        }
        if (exist) {
            System.out.printf("The phantom thief number %d to be inserted already exists and can't be added! \n", node.no);
            return;
        }

        // 把节点插入到 temp 和 temp.next 之间
        // temp -> node -> temp.next
        node.next = temp.next;
        temp.next = node;
        node.pre = temp.next.pre;
        temp.next.pre = node;
    }
}

测试用例

package DataStructure.DoubleLinkedListPackage;

import org.junit.Before;
import org.junit.Test;

/**
 * 双向链表测试
 */
public class DoubleLinkedListTest {
    DoubleLinkedList doubleLinkedList;

    @Before
    public void before() {
        HeroNode hero1 = new HeroNode(1, "Amamiya Ren", "Joker");
        HeroNode hero2 = new HeroNode(2, "Ryuji Sakamoto", "Skull");
        HeroNode hero3 = new HeroNode(3, "Anne Takamaki", "Panther");
        HeroNode hero4 = new HeroNode(4, "Yusuke Kitagawa", "Fox");

        // 测试新增
        doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.add(hero1);
        doubleLinkedList.add(hero4);
        doubleLinkedList.add(hero2);
        doubleLinkedList.add(hero3);
    }

    @Test
    public void addTest() {
        // before 中已测试
    }

    /**
     * 更新测试
     */
    @Test
    public void updateTest() {
        System.out.println("Before update:");
        doubleLinkedList.print();
        HeroNode hero4New = new HeroNode(4, "Yusuke Kitagawa-Test", "Fox-Test");
        doubleLinkedList.update(hero4New);
        System.out.println("After update:");
        doubleLinkedList.print();
    }

    /**
     * 删除测试
     */
    @Test
    public void deleteTest() {
        System.out.println("Before deletion:");
        doubleLinkedList.print();
        doubleLinkedList.delete(1);
        doubleLinkedList.delete(4);
        doubleLinkedList.delete(3);
        System.out.println("After deletion:");
        doubleLinkedList.print();
    }
    @Test
    public void addByOrderTest() {
        HeroNode hero1 = new HeroNode(1, "Amamiya Ren", "Joker");
        HeroNode hero2 = new HeroNode(2, "Ryuji Sakamoto", "Skull");
        HeroNode hero3 = new HeroNode(3, "Anne Takamaki", "Panther");
        HeroNode hero4 = new HeroNode(4, "Yusuke Kitagawa", "Fox");

        // 测试新增
        doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.addByOrder(hero1);
        doubleLinkedList.addByOrder(hero4);
        doubleLinkedList.addByOrder(hero2);
        doubleLinkedList.addByOrder(hero3);
        doubleLinkedList.addByOrder(hero3);
        doubleLinkedList.print();

    }
}

输出结果

Before update:
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
After update:
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
HeroNode{no=4, name='Yusuke Kitagawa-Test', nickName='Fox-Test'}
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}


Before deletion:
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
no element found with number: 3 !After deletion:
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}


The phantom thief number 3 to be inserted already exists and can't be added!
HeroNode{no=1, name='Amamiya Ren', nickName='Joker'}
HeroNode{no=2, name='Ryuji Sakamoto', nickName='Skull'}
HeroNode{no=3, name='Anne Takamaki', nickName='Panther'}
HeroNode{no=4, name='Yusuke Kitagawa', nickName='Fox'}

循环链表

循环链表的讲解将与约瑟夫问题结合实现

实现基本思路
1. 先构成一个有n个节点的单循环链表。
2. 然后由k节点起从1开始计数。
3. 计数到m时，对应节点从链表中删除，然后从下一个节点又从1开始计数

代码实现

查看代码实现

函数编写

package DataStructure;

// 构造孩子节点
class Boy {
    int no;
    Boy next;

    public Boy(int no) {
        this.no = no;
    }
}

public class CircleSingleLinkedList {
    Boy first = null;

    /*
     * 添加节点
     * 1. 检查num的输入是否在1及以上
     * 2. 通过cur指针循环前移，创建环形单链表
     * 3. 第一个节点为空的时候需要特殊考虑
     * 4. 添加节点的顺序为：cur指向boy,boy指向first,cur指针指向boy
     */
    public void add(int num) {
        if (num < 1) {
            System.out.println("Please input a number greater than 1! ");
            return;
        }
        Boy cur = null;
        for (int i = 1; i <= num; i++) {
            Boy boy = new Boy(i);
            if (first == null) {
                first = boy;
                boy.next = first;
                cur = first;
                continue;
            }
            cur.next = boy;
            boy.next = first;
            cur = boy;
        }
    }

    /**
     * 打印队列
     */
    public void print() {
        if (first == null) {
            System.out.println("Queue empty!");
            return;
        }
        Boy cur = first;
        while (true) {
            System.out.printf("Child number %d \n", cur.no);
            cur = cur.next;
            // 如果和 first 一致，则标识已经走了一圈了
            if (cur == first) {
                return;
            }
        }
    }

    public void countBoy(int startNo, int countNum, int nums) {
        // 进行一个数据校验
        if (first == null || // 环形队列没有构建
                countNum < 1 || // 每次至少数 1 下
                startNo > nums // 开始小孩不能大于参与游戏的人数
        ) {
            System.out.println("The parameter is incorrect.Please re-enter it!");
        }
        // 1. 初始化辅助变量到 first 的后面
        Boy helper = first;
        // 当 helper.next = first 时，就说明已经定位了
        while (helper.next != first) {
            helper = helper.next;
        }

        // 2. 定位 first 和 helper 在 startNo 位置
        // first 初始在最开始，移动到 startNo 位置
        for (int i = 0; i < startNo - 1; i++) {
            helper = first;
            first = first.next;
        }

        // 为了测试方便，这里添加一个日志输出
        System.out.printf("Localize: %d \n", startNo);
        print();

        // 3. 开始报数 和 出圈
        while (true) {
            // 当队列中只剩下一个人的时候，跳出循环，因为最后一个必然是他自己出队列
            if (helper == first) {
                break;
            }
            // 报数：每次报数 m-1
            for (int i = 0; i < countNum - 1; i++) {
                // 因为 helper 永远在 first 后面，只要在 first 移动时，指向 first 原来所在的位置即可
                helper = first;
                first = first.next;
            }
            // 出圈
            System.out.printf("The number of the child out of the circle %d \n", first.no);
            first = first.next; // first 重置为下一次报数的小孩节点上
            helper.next = first; // helper 重置为下一次报数的小孩节点上
        }
        System.out.printf("The number of the last child left %d \n", first.no);
    }
}

测试用例

package DataStructure;

import org.junit.Test;

public class JosepfuTest {
    @Test
    public void addTest() {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.add(5);
        circleSingleLinkedList.print();
    }

    @Test
    public void countBoy() {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.add(5);
        System.out.println("Build Circle Queue:");
        circleSingleLinkedList.print();

        // 开始玩游戏
        // 正确的输出顺序为：2、4、1、5、3
        circleSingleLinkedList.countBoy(1, 2, 5);
    }
}

输出结果

Child number 1
Child number 2
Child number 3
Child number 4
Child number 5

Build Circle Queue:
Child number 1
Child number 2
Child number 3
Child number 4
Child number 5
Localize: 1
Child number 1
Child number 2
Child number 3
Child number 4
Child number 5