Logo

Menu

一溪风月
一溪风月
Published on 2023-04-26 / 18 Visits
0

链表(Java)

#数据结构

链表介绍

链表是有序链表，在内存中存储方式如下：

链表示意图.png

  • 链表是以节点的方式来存储,是链式存储

  • 每个节点包含data域，next域：指向下一个节点。

  • 如图发现链表的各个节点不一定是连续存储。

  • 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定。

单链表(带头结点)逻辑结构示意图如下：

链表逻辑结构.png

单链表

应用实例，使用单链表实现增删改查操作：

首先创建一个节点类，（注：因为待会的双向链表使用的也是这个节点类，所以此类中写了两个指针，但是单向链表只需要使用一个即可）

package com.athome.linkedlist;

/**
 * Description:
 * Author:江洋大盗
 * Date:2021/1/23 10:21
 */
public class Person {
    String name;//姓名
    int no;//编号
    Person next;//下一个节点
    Person pre;//上一个节点

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

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + ''' +
                ", no=" + no +
                '}';
    }
}

再创建单向链表:

package com.athome.linkedlist;

import java.util.Stack;

/**
 * Description:
 * Author:江洋大盗
 * Date:2021/1/23 10:48
 */
public class SingleLinkedList {
    //定义头节点,不存放任何数据，指向单链表开始的位置
    private final Person head = new Person(null, 0);

    /**
     * 无序添加，即直接加入到链表末尾
     *
     * @param person 待添加的节点
     */
    public void add(Person person) {
        if (person == null) {
            return;
        }
        //定义辅助变量帮助遍历
        Person temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = person;
    }

    /**
     * 有序添加，按从小到大的顺序添加
     *
     * @param person 待添加的节点
     */
    public void addByNo(Person person) {
        if (person == null) {
            return;
        }
        //定义辅助变量帮助遍历
        boolean flag = false;//标识该位置是否存在数据
        Person temp = head;
        while (temp.next != null) {
            if (temp.next.no == person.no) {
                flag = true;
                break;
            }
            if (temp.next.no > person.no) {
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.println("该位置已经存在数据");
        } else {
            person.next = temp.next;
            temp.next = person;
        }
    }

    /**
     * 打印链表
     */
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //定义辅助变量帮助遍历
        Person temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

    /**
     * 修改节点
     *
     * @param person 要修改的数据
     */
    public void update(Person person) {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //定义辅助变量帮助遍历
        Person temp = head.next;
        boolean flag = false;//标识该数据是否存在
        while (temp != null) {
            if (temp.no == person.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            //说明找到了节点
            temp.name = person.name;
        } else {
            System.out.println("没有找到要修改的节点");
        }
    }

    /**
     * 删除节点
     *
     * @param no 待删除的节点编号
     */
    public void delete(int no) {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //定义辅助变量帮助遍历
        Person temp = head;
        boolean flag = false;//标识该数据是否存在
        while (temp.next != null) {
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            //说明找到了要删除的节点
            temp.next = temp.next.next;
        } else {
            System.out.println("没有找到要删除的节点");
        }
    }

    /**
     * @return 返回当前链表的有效节点个数
     */
    public int size() {
        //判断链表是否为空
        if (head.next == null) {
            return 0;
        }
        int count = 0;//计数器
        Person temp = head.next;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        return count;
    }

    /**
     * 查询倒数第k个节点
     *
     * @param k 到处第k个
     * @return 返回查询结果，若查询不到返回null
     */
    public Person findPerson(int k) {
        //判断链表是否为空
        if (head.next == null) {
            return null;
        }
        int curSize = size();
        //判断k值是否符合条件
        if (k < 0 || k > curSize) {
            return null;
        }
        Person temp = head.next;
        for (int i = 0; i < curSize - k; i++) {
            temp = temp.next;
        }
        return temp;
    }

    /**
     * 反转列表
     */
    public void reserve() {
        //如果链表中没有或只有一个元素，不需要反转
        if (head.next == null || head.next.next == null) {
            return;
        }
        //定义临时头节点，注意这个思想很重要
        Person tempHead = new Person(null, 0);
        Person temp = head.next;
        Person next;//帮助temp后移
        while (temp != null) {
            next = temp.next;
            //将头节点前面的元素拼接到临时头节点的末尾,完成反转
            temp.next = tempHead.next;
            tempHead.next = temp;
            //temp后移
            temp = next;
        }
        //反转完成之后使用真正的头节点取代临时头节点
        head.next = tempHead.next;
    }

    /**
     * 将链表反转输出，注意链表本身不受影响
     */
    public void reserveOut() {
        //如果链表中没有或只有一个元素，不需要反转
        if (head.next == null || head.next.next == null) {
            return;
        }
        //利用栈先进后出的特点完成反转输出
        Stack<Person> people = new Stack<>();
        Person temp = head.next;
        while (temp != null) {
            people.push(temp);
            temp = temp.next;
        }
        while (!people.empty()) {
            System.out.println(people.pop());
        }
    }
}

主方法中测试：

package com.athome.linkedlist;

import java.util.Scanner;

/**
 * Description:
 * Author:江洋大盗
 * Date:2021/1/23 10:14
 */
public class LinkedListDemo {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        boolean flag = true;
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        while (flag) {
            System.out.println("--------单向链表测试---------");
            System.out.println("add:添加");
            System.out.println("delete:删除");
            System.out.println("update:更新");
            System.out.println("list:打印链表");
            System.out.println("find:反向查询");
            System.out.println("reverse:反转链表");
            System.out.println("reverseOut:反转输出链表");
            System.out.println("exit:退出程序");
            System.out.print("请输入您的选择:");
            String choice = scanner.next();
            switch (choice) {
                case "add":
                    System.out.print("请输入用户姓名:");
                    String name = scanner.next();
                    System.out.print("请输入用户编号:");
                    int no = scanner.nextInt();
                    singleLinkedList.addByNo(new Person(name, no));
                    break;
                case "delete":
                    System.out.print("请输入待删除用户编号:");
                    no = scanner.nextInt();
                    singleLinkedList.delete(no);
                    break;
                case "update":
                    System.out.print("请输入待修改用户编号:");
                    no = scanner.nextInt();
                    System.out.print("请输入修改后用户姓名:");
                    name = scanner.next();
                    singleLinkedList.update(new Person(name, no));
                    break;
                case "find":
                    System.out.print("请输入要查找倒数第几位用户:");
                    no = scanner.nextInt();
                    Person person = singleLinkedList.findPerson(no);
                    System.out.println(person);
                    break;
                case "list":
                    singleLinkedList.list();
                    break;
                case "reverse":
                    singleLinkedList.reserve();
                    break;
                case "reverseOut":
                    singleLinkedList.reserveOut();
                    break;
                case "exit":
                    flag = false;
                    break;
            }
        }
        System.out.println("程序结束");
    }
}

双向链表

应用实例：使用单向链表完成增删改查操作

创建双向链表（注：此处节点类使用的是 上面创建的Person节点类）

package com.athome.linkedlist;

/**
 * Description:
 * Author:江洋大盗
 * Date:2021/1/23 13:57
 */
public class DoubleLinkedList {
    //头节点
    private final Person head = new Person(null, 0);

    /**
     * 有序添加，从小到大的顺序添加
     *
     * @param person 待插入的节点
     */
    public void addByNo(Person person) {
        if (person == null) {
            return;
        }
        Person temp = head;
        boolean flag = false;
        while (temp.next != null) {
            if (temp.next.no == person.no) {
                flag = true;
                break;
            }
            if (temp.next.no > person.no) {
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.println("该位置已经有值");
        } else {
            if (temp.next != null) {
                temp.next.pre = person;
                person.next = temp.next;
            }
            temp.next = person;
            person.pre = temp;
        }
    }

    /**
     * 删除节点
     *
     * @param no 待删除编号
     */
    public void delete(int no) {
        if (head.next == null) {
            return;
        }
        Person temp = head.next;
        boolean flag = false;
        while (temp != null) {
            if (temp.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.pre.next = temp.next;
            if (temp.next != null)
                temp.next.pre = temp.pre;
        } else {
            System.out.println("找不到要删除的节点");
        }
    }

    /**
     * @param person 封装了待修改的数据
     */
    public void update(Person person) {
        if (head.next == null || person == null) {
            return;
        }
        Person temp = head.next;
        boolean flag = false;
        while (temp != null) {
            if (temp.no == person.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = person.name;
        } else {
            System.out.println("找不到要修改的节点");
        }
    }

    /**
     * 打印双向链表
     */
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
        }
        Person temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

主方法中测试：

package com.athome.linkedlist;

import java.util.Scanner;

/**
 * Description:
 * Author:江洋大盗
 * Date:2021/1/23 14:18
 */
public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        boolean flag = true;
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        while (flag) {
            System.out.println("--------单向链表测试---------");
            System.out.println("add:添加");
            System.out.println("delete:删除");
            System.out.println("update:更新");
            System.out.println("list:打印链表");
            System.out.println("exit:退出程序");
            System.out.print("请输入您的选择:");
            String choice = scanner.next();
            switch (choice) {
                case "add":
                    System.out.print("请输入用户姓名:");
                    String name = scanner.next();
                    System.out.print("请输入用户编号:");
                    int no = scanner.nextInt();
                    doubleLinkedList.addByNo(new Person(name, no));
                    break;
                case "delete":
                    System.out.print("请输入待删除用户编号:");
                    no = scanner.nextInt();
                    doubleLinkedList.delete(no);
                    break;
                case "update":
                    System.out.print("请输入待修改用户编号:");
                    no = scanner.nextInt();
                    System.out.print("请输入修改后用户姓名:");
                    name = scanner.next();
                    doubleLinkedList.update(new Person(name, no));
                    break;
                case "list":
                    doubleLinkedList.list();
                    break;
                case "exit":
                    flag = false;
                    break;
            }
        }
        System.out.println("程序结束");
    }
}

单项环形列表解决Josephu问题

Josephu问题介绍

Josephu问题为：设编号为1，2，...n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

代码实现

节点类

package com.athome.linkedlist;

/**
 * Description:
 * Author:江洋大盗
 * Date:2021/1/23 14:25
 */
public class Boy {
    int id;//男孩编号
    Boy next;

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

    @Override
    public String toString() {
        return "小孩{" +
                "编号:" + id +
                '}';
    }
}

环形列表解决约瑟夫问题：

package com.athome.linkedlist;

/**
 * Description:
 * Author:江洋大盗
 * Date:2021/1/23 14:38
 */
public class CircleLinkedList {
    //头节点
    private Boy head = null;

    /**
     * 添加小孩
     *
     * @param nums 要添加的小孩数量
     */
    public void addBoy(int nums) {
        //如果人数小于1，直接结束方法
        if (nums < 1) {
            return;
        }
        //辅助指针帮助构建环形链表
        Boy temp = null;
        //循环构建环形链表
        for (int i = 1; i <= nums; i++) {
            Boy boy = new Boy(i);
            if (i == 1) {
                head = boy;
                head.next = head;
                temp = head;
            } else {
                temp.next = boy;
                boy.next = head;
                temp = boy;
            }
        }
    }

    /**
     * 打印列表
     */
    public void show() {
        //判断列表是否为空
        if (head == null) {
            System.out.println("当前链表为空");
            return;
        }
        //临时变量
        Boy temp = head;
        while (true) {
            System.out.println(temp);
            if (temp.next == head) {
                break;
            }
            temp = temp.next;
        }
    }

    /**
     * 解决小孩出圈问题
     *
     * @param startNum 开始报数的位置
     * @param countNum 报数的步长
     * @param nums     小孩的个数
     */
    public void outCircle(int startNum, int countNum, int nums) {
        if (startNum < 0 || head == null || startNum > nums) {
            System.out.println("参数有误");
            return;
        }
        //1.定义辅助变量，先将其移动到head节点的前一个位置
        Boy helper = head;
        while (helper.next != head) {
            helper = helper.next;
        }
        //2.小孩报数前先让helper和head前移startNum-1次
        for (int i = 0; i < startNum - 1; i++) {
            helper = helper.next;
            head = head.next;
        }
        //3.小孩报数时，让helper和head同时移动countNum-1次
        //循环出圈，直到圈中只剩下一个节点
        while (helper != head) {
            for (int i = 0; i < countNum - 1; i++) {
                helper = helper.next;
                head = head.next;
            }
            System.out.println("出圈者为：" + head);
            //将head出圈
            head = head.next;
            helper.next = head;
        }
        System.out.println("幸运儿：" + head);
    }

    public static void main(String[] args) {
        CircleLinkedList circleLinkedList = new CircleLinkedList();
        //测试addBoy方法
        circleLinkedList.addBoy(25);
        circleLinkedList.show();
        //测试outCircle方法
        circleLinkedList.outCircle(1, 2, 25);
    }
}

结语

只要能收获甜蜜，荆棘丛中也有蜜蜂忙碌的身影，未来的你一定会感谢现在努力的自己。

常见排序算法的实现与总结(Java)
系统迁移录