java实现单向循环链表

ゞ浴缸里的玫瑰 2023-06-01 11:24 42阅读 0赞

### 链表图解 ###

带头结点的链表：  
![带头结点的链表][1240]

不带头结点的链表：

![不带头结点的链表][1240 1]

区别

> 带头结点的链表容易代码实现  
> 不带头结点的容易实现循环链表和双向链表

### 代码的实现 (增减 删除) ###

节点实现：

public class node
    {
    
    
        private int no;
        public  node next;
        public node(int no) {
            this.no = no;
        }
    
        public int getNo() {
            return no;
        }
    
        @Override
        public String toString() {
            return "Node [no=" + no + "]";
        }
    }

链表实现：

public class linkedList {
        private node head;//头结点
    
    
        public linkedList() {
        }
    
        public boolean add( node newhero) {//添加节点
            boolean isSuccessful=false;
                if(head==null){//处理空表
                    head=newhero;
                    newhero.next=head;
                    isSuccessful=true;
                }else{//不为空时
                    node node= head;
                    while(true){
                        if (node.next==head){
                            break;
                        }
                        node=node.next;
                    }
                    node.next=newhero;
                    newhero.next=head;
                    isSuccessful=true;
    
                }
            return isSuccessful;
    
        }
    
        public node delete(int index) {//删除制定节点
            node outputNode = null;
            node node= head; //指向第一个节点
            if ((index)==0) {//查到该节点的前一个节点
                outputNode = node;
                head=null;
                head = node.next;//删除语句
                return outputNode;
            }
            int location=0;//计时器
            while (true){  //
                if (isEmpty()) {//如果链表为空中断
                    break;
                }else  if (location==index-1){//查到该节点的前一个节点
                    outputNode=node.next;
                    node.next=node.next.next;//删除语句
    
                    break;
                }
                if (node.next==null){
                    break;
                }
                location++;//计时器加加
                node=node.next;//节点后移
            }
            return outputNode;
    
        }
    
        public boolean isEmpty() {
            return head==null;
    
        }
    
    
        public void display() {//遍历整个链表
    
            node node=head;
            while(node!=null){
                System.out.println(node.toString());
    
                if (node.next.getNo()==head.getNo()){
                    break;
                }
                node=node.next;
    
            }
            //1.对象不为空才能执行---->可避免空指针异常
            //2.循环里的收尾不是断开的
    
        }

### 链表的应用 ：约瑟夫问题的求解 ###

> 问题描述：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏

**输入样例:**

人数：39

**输出样例:**

安全位置是：16 31

**问题分析:**

> 1.实现节点（每个节点代表一个人，包含位置编号）  
> 2.采用循环链表代表围成一个圈  
> 3.每次数三个数，就删除第三个节点，重新计数，直到链表中剩下两个元素，  
> 4.输出这两个节点

**java参考代码:**

@Test
        public void yuecefuTest() {
    
            int input =31;
            LinkedList <Persion> people = new LinkedList <>();
            LinkedList <Persion> people2 = new LinkedList <>();
            for (int i = 0; i < input ;i++) {
                people.add( new Persion(i+1));
            }
            int i = 0;
            for (int j = input*2-2; j >0 ;j--) {
                if (i==2){
                    people2.add(people.remove(i));
                    i=0;
                }
                i++;
            }
            for (Persion p:people
                 ) {
                System.out.println("  "+p.toString());
            }
    
        }

### LinkedList 源码分析 ###

转载于:https://www.cnblogs.com/rainbowbridge/p/11410307.html

[1240]: /images/20230601/ec8713a62e4f45c1858e68dc253f3970.png
[1240 1]: /images/20230601/ba3f299587704c8c8acfde84d8880d7d.png