链表 Linked List (Josephus 问题)

链表 Linked List

一、介绍

链表是一种物理存储单元上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。

特点：

1. 链表是以结点形式存储的，是链式存储
2. 每个结点包含data区域和next区域
3. 如上图各个结点并不是连续存储的
4. 链表分带头结点链表和没有带头结点链表，根据实际的需求来确定

• 带头结点链表逻辑结构

二、单链表

1.需求：

根据带有头部的单链表，实现商品增删改查，并且也可以针对商品已编号进行排序，完成排行榜

Node节点：

package com.example.linklist.single.basic;/*** 链表的节点：用来构成链表*/
public class GoodNode {
    //节点需要有节点自己的信息int id;int price;String name;//节点需要有指向下一个节点的指针（引用）GoodNode next;public GoodNode(int id, int price, String name) {
    this.id = id;this.price = price;this.name = name;}
}

SingleLinkedList:

package com.example.linklist.single.basic;/*** 自定义 链表*/
public class MySingleLinkedList {
    //定义空的 头节点GoodNode head = new GoodNode(0,0,"");/*** 增加方法；在队尾直接添加*/public void add(GoodNode goodNode){
    GoodNode temp = head;while (true){
    if (temp.next == null){
    break;}temp = temp.next;}temp.next = goodNode;}/*** 按id顺序添加*/public void addById(GoodNode goodNode){
    GoodNode temp = head;while (true){
    if (temp.next == null){
    temp.next = goodNode;return;}//找到插入位置：先将后面的节点挂在 待插入节点后面，（如果先去挂载到前面）不然就丢了。if (temp.next.id > goodNode.id){
    goodNode.next = temp.next;temp.next = goodNode;return;}else if (temp.next.id == goodNode.id){
    System.out.println("存在相同id,不能插入");return;}temp = temp.next;}}/*** 修改：*/public void update(GoodNode goodNode){
    //用来遍历 链表GoodNode temp = head.next;while (true){
    if (temp == null){
    return;}//找到id相同的 节点了if (temp.id == goodNode.id ){
    // 修改temp.id = goodNode.id;temp.name = goodNode.name;temp.price = goodNode.price;return;}//向后遍历temp = temp.next;}}/*** 删除：根据节点编号删除*/public void delete(int id){
    //定义前一个节点 用于删除GoodNode tempBefore = head;//定义 节点 用于寻找 该id的节点。GoodNode temp = head.next;//是否找打的标识boolean flag = false;while (true) {
    //链表结束了if (temp == null){
    break;}//找到了if (temp.id == id){
    flag = true;break;}//继续向后遍历temp = temp.next;tempBefore = tempBefore.next;}if (flag){
    //使 temp前一个节点 直接连接后一个节点。（跳过temp节点）tempBefore.next = temp.next;}else {
    System.out.println("没找到该id的节点");}}/*** 查看 链表所有元素*/public  void  list(){
    if (head.next == null){
    System.out.println("为空");}GoodNode temp = head.next;while (true){
    if (temp ==null){
    break;}System.out.printf("node id:%d,name:%s,price:%d \n",temp.id,temp.name,temp.price);temp = temp.next;}}}

Test:

package com.example.linklist.single.basic;public class SingleLinkedListTest {
    public static void main(String[] args) {
    GoodNode goodNode1 = new GoodNode(1,10,"上衣");GoodNode goodNode2 = new GoodNode(2,1,"鞋");GoodNode goodNode4 = new GoodNode(4,5,"帽子");MySingleLinkedList mySingleLinkedList = new MySingleLinkedList();mySingleLinkedList.add(goodNode1);mySingleLinkedList.add(goodNode2);mySingleLinkedList.add(goodNode4);mySingleLinkedList.list();mySingleLinkedList.update(new GoodNode(1,100,"上衣"));mySingleLinkedList.list();GoodNode goodNode3 = new GoodNode(3,8,"裤子");mySingleLinkedList.addById(goodNode3);mySingleLinkedList.delete(2);mySingleLinkedList.list();//结果：//node id:1,name:上衣,price:10//node id:2,name:鞋,price:1//node id:4,name:帽子,price:5//node id:1,name:上衣,price:100//node id:2,name:鞋,price:1//node id:4,name:帽子,price:5//node id:1,name:上衣,price:100//node id:3,name:裤子,price:8//node id:4,name:帽子,price:5}
}

二、双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

BookNode:

package com.example.linklist.doublelist.basic;/*** 双向链表的节点* 有指向前驱节点的 pre ,有指向后继节点的 next*/
public class BookNode {
    int id;String name;int price;//指向前驱BookNode pre;//指向后继BookNode next;public BookNode(int id, String name, int price) {
    this.id = id;this.name = name;this.price = price;}
}

DaulLinkedList:

package com.example.linklist.doublelist.basic;import javax.xml.stream.FactoryConfigurationError;
import java.util.jar.JarEntry;/*** 双向链表*/
public class DualLinkedList {
    //头节点BookNode head = new BookNode(0, "", 0);/*** 在结尾添加节点*/public void addLast(BookNode bookNode) {
    BookNode temp = head;while (true) {
    //到达 末尾if (temp.next == null) {
    break;}temp = temp.next;}//新节点加到 原链表 末尾。 新节点 前驱指向 原链表 末尾节点temp.next = bookNode;bookNode.pre = temp;}/*** 根据id插入：需要找到 比当前id大的 或者到末尾*/public void addById(BookNode bookNode){
    //是否找到了 比当前大的boolean flag = false;BookNode temp = head;while (true){
    if (temp.next == null){
    break;}if (temp.next.id  > bookNode.id){
    flag = true;break;}else if (temp.next.id == bookNode.id){
    System.out.println("已存在，不能添加");return;}temp = temp.next;}if (flag){
    //新节点与后面节点 连接temp.next.pre = bookNode;bookNode.next = temp.next;//新节点 前面节点连接temp.next = bookNode;bookNode.pre = temp;}else {
    //没找到直接加到末尾temp.next = bookNode;bookNode.pre = temp;}}/*** 修改节点*/public void update(BookNode bookNode) {
    BookNode temp = head.next;boolean flag = false;while (true) {
    if (temp == null) {
    break;}if (temp.id == bookNode.id) {
    flag = true;break;}temp = temp.next;}if (flag) {
    temp.name = bookNode.name;temp.price = bookNode.price;} else {
    System.out.println("未找到对应id 的节点。");}}/*** 双向链表删除*/public void delete(int id) {
    BookNode temp = head;boolean flag = false;while (true) {
    if (temp.next == null) {
    break;}if (temp.next.id == id) {
    flag = true;break;}temp = temp.next;}if (flag) {
    //从前往后指temp.next = temp.next.next;//注意可能未num的情况。if (temp.next.next != null) {
    temp.next.next.pre = temp;}} else {
    System.out.println("没找到该id");}}public void list(){
    if (head.next == null){
    System.out.println("为空");}BookNode temp = head.next;while (true){
    if (temp == null){
    break;}System.out.printf("id:%d,name:%s,price:%d \n",temp.id,temp.name,temp.price);temp = temp.next;}}}

Test:

package com.example.linklist.doublelist.basic;public class DualTest {
    public static void main(String[] args) {
    DualLinkedList dualLinkedList = new DualLinkedList();BookNode bookNode1= new BookNode(1,"红楼梦",300);BookNode bookNode2= new BookNode(2,"水浒传",300);BookNode bookNode3= new BookNode(3,"西游记",300);BookNode bookNode4= new BookNode(4,"三国演义",300);dualLinkedList.addLast(bookNode1);dualLinkedList.addLast(bookNode2);dualLinkedList.addLast(bookNode3);dualLinkedList.addLast(bookNode4);dualLinkedList.list();BookNode bookNode= new BookNode(3,"西游记",400);dualLinkedList.update(bookNode);dualLinkedList.list();dualLinkedList.delete(2);dualLinkedList.list();dualLinkedList.addById(bookNode2);dualLinkedList.list();//结果：//id:1,name:红楼梦,price:300//id:2,name:水浒传,price:300//id:3,name:西游记,price:300//id:4,name:三国演义,price:300//id:1,name:红楼梦,price:300//id:2,name:水浒传,price:300//id:3,name:西游记,price:400//id:4,name:三国演义,price:300//id:1,name:红楼梦,price:300//id:3,name:西游记,price:400//id:4,name:三国演义,price:300//id:1,name:红楼梦,price:300//id:2,name:水浒传,price:300//id:3,name:西游记,price:400//id:4,name:三国演义,price:300}
}

三、环形链表解决约瑟夫问题：

1.问题描述

约瑟夫问题（约瑟夫环）

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

2.使用构建单向链表实现

BoyNode:

package com.learn.linklist.josephus;/*** 用于 构建单项环形链表*/
public class BoyNode {
    private int  no;private BoyNode next;public BoyNode(int no) {
    this.no = no;}public int getNo() {
    return no;}public void setNo(int no) {
    this.no = no;}public BoyNode getNext() {
    return next;}public void setNext(BoyNode next) {
    this.next = next;}
}

CircleSingleLinkedList:

package com.learn.linklist.josephus;import java.util.ArrayList;/*** 单向环形 链表** 设编号为1,2…，n的n个人围坐一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人出列，* 它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。*/
public class CircleSingleLinkedList {
    //外部的旁观节点，指向第一个节点。BoyNode head = new BoyNode(-1);public CircleSingleLinkedList(int n){
    if(n<1){
    System.out.println("不能");}BoyNode temp = head;for (int i = 1; i <= n; i++) {
    BoyNode boyNode = new BoyNode(i);temp.setNext(boyNode);temp = temp.getNext();}temp.setNext(head.getNext());}/*** list*/public void showBoy(){
    if (head == null){
    System.out.println("链表为空");return;}BoyNode first = head.getNext();BoyNode temp = head.getNext();while (true){
    System.out.printf("no:%d \n",temp.getNo());temp = temp.getNext();if (temp == first ){
    break;}}}//约瑟夫问题：设编号为1,2…，n的n个人围坐一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人出列，// 它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。public static ArrayList josephusCount(int n, int k, int m){
    ArrayList<Integer> result = new ArrayList<>();//创建一个环形队列CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList(n);//初始化计数int count = 0;//单向链表 删除，最好使用两个指针，因为需要操作三个节点。 前一个、当前节点、后一个节点BoyNode temp = circleSingleLinkedList.head.getNext();BoyNode tempBefore = temp;while (true){
    if (tempBefore.getNext() == temp){
    break;}tempBefore = tempBefore.getNext();}//找到第k个人，开始计数 即移动 k-1次for (int i = 0; i < k-1; i++) {
    temp = temp.getNext();tempBefore = tempBefore.getNext();}//模拟出列while (true){
    //当temp 和 tempBefore 指向同一节点，则说明 当前环形队列仅剩一个节点 直接出列结束if (temp == tempBefore){
    result.add(temp.getNo());break;}//开始数数count++;//判断 是否到达 mif (count == m){
    //出列result.add(temp.getNo());//删除该节点。tempBefore.setNext(temp.getNext());temp = tempBefore.getNext();//计数归0，从0开始数数count = 0;continue;}else {
    temp = temp.getNext();tempBefore = tempBefore.getNext();}}return result;}}

3.使用LinkedList 实现 并测试：

package com.learn.linklist.josephus;import java.util.ArrayList;
import java.util.LinkedList;public class JosephusTest {
    public static void main(String[] args) {
    CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList(5);circleSingleLinkedList.showBoy();ArrayList arrayList = CircleSingleLinkedList.josephusCount(5, 2, 3);System.out.println(arrayList);//结果：//no:1//no:2//no:3//no:4//no:5//[4, 2, 1, 3, 5]ArrayList arrayList2 = josephusLinkedList(5, 2, 3);System.out.println(arrayList2);//[4, 2, 1, 3, 5]}//直接使用 LinkedList 实现。private static ArrayList josephusLinkedList(int n, int k, int m) {
    ArrayList<Integer> result = new ArrayList();LinkedList<Integer> linkedList = new LinkedList<>();//向集合中加入n个元素：for (int i = 1; i <= n ; i++) {
    linkedList.add(i);}//操作下标出列。int count = 0;int index = k-1;// 第k个人，下标为k-1//直接找到 数m的那个人；while (true){
    //剩最后一个人结束if (linkedList.size() == 1){
    break;}//直接找到下个出列人 下标。index = (index + m-1)%linkedList.size();Integer no = linkedList.get(index);result.add(no);linkedList.remove(index);//重新定义现在的 index（可能为最后一个元素，删完就变成 从第一个开始了）index = index% linkedList.size();}Integer no = linkedList.get(0);result.add(no);return  result;}
}