二、列表(java)

目录

一、单项列表

二、双向列表

三、约瑟夫问题(单项列表)

一、单项列表

 

链表的优点：

由于链表上的元素在空间存储上内存地址不连续。

所以随机增删元素的时候不会有大量元素位移，因此随机增删效率较高。

在以后的开发中，如果遇到随机增删集合中元素的业务比较多时，建议

使用LinkedList。

链表的缺点：

不能通过数学表达式计算被查找元素的内存地址，每一次查找都是从头

节点开始遍。

注意:

public class ListNode{
    int val;
    ListNode next;        //链表指向的下一个值的指针
    ListNode(int x){val = x;}   //这个方式赋值
}

 

通过xx.next = new ListNode(4);来赋值，注意此时是赋值给下一个指针指向的位置,此时此链表一个值，值为4。

单项列表例子

package Linked;

public class GoodsNode {
    public  int id;
    public  String name;
    public  Double price;

    @Override
    public String toString() {
        return "GoodsNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", price=" + price +
                '}';
    }

    public  GoodsNode next;
    public  GoodsNode(int id, String name, Double price) {
        this.id = id;
        this.name = name;
        this.price = price;
    }
}

package Linked;

public class DLLinkedList {
    GoodsNode node = new GoodsNode(0, "", 0.0);

    //往链表中插入数据(在最后插入)

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

    //添加节点(按照顺序)
    //按照商品id进行排序，从小到达按顺序添加

    public void addOrder(GoodsNode goodsNode) {
        GoodsNode temp = node;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.id > goodsNode.id) {
                break;
            } else if (temp.next.id == goodsNode.id) {
                flag = true;
                break;
            }

            temp = temp.next;
        }
        if (flag) {
            System.out.println("该商品已存在");
        } else {
            goodsNode.next = temp.next;
            temp.next = goodsNode;
        }
    }

            //修改节点
            //1、直到链表中的最后—个节点未找到，则结束循环
            //2、找到了节点，结束循环

    public void updateNode(GoodsNode goodsNode){
        //如果链表为空
        if(node.next==null){
            System.out.println("链表为空");
            return;
        }
        GoodsNode temp =node.next;
        boolean flag =false;
        while (true){
            if(temp==null){
                break;
            }
            if(temp.id==goodsNode.id){
                flag=true;
                break;
            }
            temp=temp.next;

        }
        if(flag){
            //真正的修改节点
            temp.name=goodsNode.name;
            temp.price=goodsNode.price;
        }else {
            System.out.println("在整个链表中未找到链表节点");
        }
    }

    //删除节点
    //条件：根据节点的编号删除
    public void  delNode(int id) {
        GoodsNode temp = node;
        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;
        }else {
            System.out.println("未找到删除的节点");
        }
    }

    //查询列表
    public void list(){
    if(node.next==null){
        System.out.println("空链表");
        return;
    }
    GoodsNode temp =node.next;
    while (true){
        if(temp==null){
            break;
        }
        System.out.println(temp);
        temp=temp.next;
        }
    }
}

public class LinkedTest {
    public static void main(String[] args) {
        DLLinkedList linkedList = new DLLinkedList();


        GoodsNode goodsNode1 = new GoodsNode(1,"耐克运动鞋",599.00);
        GoodsNode goodsNode2 = new GoodsNode(2,"耐克上衣",399.00);
        GoodsNode goodsNode3 = new GoodsNode(3,"阿迪达斯运动鞋",699.00);
        GoodsNode goodsNode4 = new GoodsNode(4,"李宁运动鞋",499.00);


        linkedList.addOrder(goodsNode3);
        linkedList.addOrder(goodsNode1);
        linkedList.addOrder(goodsNode2);
        linkedList.addOrder(goodsNode4);

        linkedList.list();
        System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
        linkedList.updateNode(new GoodsNode(1,"新科技鞋子",1999.9));

        linkedList.list();

        System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");

        linkedList.delNode(1);

       linkedList.list();

    }
}

二、双向列表

双向列表例子 

public class BookNode {
    public int id;
    public String name;
    public double price;
    public BookNode next;
    public  BookNode pre;

    public BookNode(int id, String name, double price) {
        this.id = id;
        this.name = name;
        this.price = price;
    }
    @Override
    public String toString() {
        return "DualLinkedList{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", price=" + price +
                '}';
    }

}

 

public class DualLinkedList {
    BookNode head = new BookNode(0, "", 0);


    //添加结尾新的节点
    public void addLast(BookNode newNode) {
        BookNode temp = head;
        while (true) {
            //如果第一次进入，表示双向链表是空数据
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = newNode;
        newNode.pre = temp;
    }

    //根据顺序添加新的列表
    public void addOrder(BookNode newNode) {
        BookNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.id>newNode.id) {
                break;
            } else if (temp.id == newNode.id) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.println("该书已存在");
        } else {

          if(temp.next!=null){
              newNode.next=temp.next;
              temp.next.pre=newNode;
              temp.next=newNode;
              newNode.pre=temp;
          }else {
              temp.next=newNode;
              newNode.pre=temp;
          }
        }
    }
    //修改节点

    public void updateNode(BookNode node) {
        if (head.next == null) {
            System.out.println("空链表");
            return;
        }
        BookNode temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.id == node.id) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = node.name;
            temp.price = node.price;
        } else {
            System.out.println("未找到修改的节点");
        }

    }

    //删除节点

    public void delNode(BookNode node) {
        if (head.next == null) {
            System.out.println("双向链表为空");
            return;
        }
        BookNode temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.id == node.id) {
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            temp.pre.next = temp.next;
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }
        }
    }

    public void list() {
        if (head.next == null) {
            System.out.println("空链表");
            return;
        }
          BookNode temp = head.next;
        while (true){
            if(temp==null){
                break;
            }
            System.out.println(temp);
            temp=temp.next;
        }

    }
}

 

public class Test {
    public static void main(String[] args) {

        DualLinkedList dualLinkedList = new DualLinkedList();

        BookNode bookNode1= new BookNode(1,"红楼梦",66.0);
        BookNode bookNode2= new BookNode(2,"西游记",66.0);
        BookNode bookNode3= new BookNode(3,"水浒传",66.0);
        BookNode bookNode4= new BookNode(4,"三国演义",66.0);

        dualLinkedList.addOrder(bookNode3);
        dualLinkedList.addOrder(bookNode1);
        dualLinkedList.addOrder(bookNode2);
        dualLinkedList.addOrder(bookNode4);

        dualLinkedList.list();
    }
}

三、约瑟夫问题(单项列表)

约瑟夫问题的示意

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

n = 5 , 即有5个人

k = 1, 从第一个人开始报数

m = 2, 数2下

构建环形链表

约瑟夫问题代码展示


   //节点的对象
public class Boy {

    //结点编号
    private int no;

    //指向下一个节点
    private  Boy next;

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

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}

public class CircleSingleLinkedLList {

    private Boy first = new Boy(-1);
    //构建环形链表

    public void addBoy(int nums){
        if(nums<1){
            System.out.println("数据不正确");
            return;
        }
        Boy temp =null;

        for(int i = 1;i<=nums;i++){
            Boy boy = new Boy(i);
            //判断是否是第一个小孩
            if(i==1){
                first= boy;
                first.setNext(first);
                temp=first;
            }else{
                temp.setNext(boy);
                boy.setNext(first);
                temp=boy;
            }
        }
    }

    //查看环形链表中的节点
    public void showBoy(){
        if(first==null){
            System.out.println("链表为空");
            return;
        }
        Boy  boy =first;
        while (true){
            System.out.printf("小孩的编号%d\n",boy.getNo());
            if(boy.getNext()==first){
                break;
            }
          boy = boy.getNext();
        }
    }
//当调用该方法输入第几个小孩子数数，数几次，环形链表中一共几个小孩
    public void countBoy(int startNo,int countNum,int nums ){
        if(first==null||startNo<1||startNo>nums){
            System.out.println("参数输入有错");
            return;
        }


        //定义辅助指点，指向的是环形单链表中的最后一个节点
        Boy helper = first;
        while (true){
            if(helper.getNext()==first){
                break;
            }
            helper=helper.getNext();
        }

        //寻找起始位置，把first定义为起始位置

        for(int j =0;j<startNo-1;j++){
            first=first.getNext();
            helper=helper.getNext();
        }

        //当小孩进行报数时，数到m的小孩进行出列，让first和helper移动m-1次即可。
        //找到了出列小孩
       while (true){
           if(helper==first){
               break;
           }
           for(int j =0;j<countNum-1;j++){
               first=first.getNext();
               helper=helper.getNext();
           }
           System.out.printf("小孩子%d 出列\n",first.getNo());
           first=first.getNext();
           helper.setNext(first);



       }
        System.out.printf("最后出圈的小孩子编号%d\n",first.getNo());

    }
    
}
public class TestBoy {
    public static void main(String[] args) {
        CircleSingleLinkedLList circleSingleLinkedLList = new CircleSingleLinkedLList();
        circleSingleLinkedLList.addBoy(5);
        circleSingleLinkedLList.showBoy();

        circleSingleLinkedLList.countBoy(1,2,5);
    }
}

版权声明：本文为m0_62786471原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。